Davin Choo

I am broadly interested in designing practical algorithms with theoretical guarantees, and analyzing existing heuristics by providing guarantees for them under real-world assumptions. I like learning new things and skills.

If you think you are working on a problem that I might find interesting, do not hesitate to reach out to me to chat about it!

Email
davin [at] u.nus.edu

Publications

Title Authors Place Year Links
Learning Sparse Fixed-Structure Gaussian Bayesian Networks Arnab Bhattacharyya, Davin Choo, Rishikesh Gajjala, Sutanu Gayen, Yuhao Wang Preprint 2021 arXiv
The Complexity of Sparse Tensor PCA Davin Choo, Tommaso d'Orsi Conference on Neural Information Processing Systems (NeurIPS) 2021 arXiv
Massively Parallel Correlation Clustering in Bounded Arboricity Graphs Mélanie Cambus, Davin Choo, Havu Miikonen, Jara Uitto International Symposium on Distributed Computing (DISC) 2021 arXiv
k-means++: few more steps yield constant approximation Davin Choo, Christoph Grunau, Julian Portmann, Václav Rozhoň International Conference on Machine Learning (ICML) 2020 Video, ICML, arXiv
BOSPHORUS: Bridging ANF and CNF Solvers Davin Choo, Mate Soos, Kian Ming A. Chai, Kuldeep S. Meel Proceedings of Design, Automation, and Test in Europe (DATE) 2019 Paper, Code
Chemical Structure Elucidation from Mass Spectrometry by Matching Substructures Jing Lim, Joshua Wong, Minn Xuan Wong, Lee Han Eric Tan, Hai Leong Chieu, Davin Choo, Neng Kai Nigel Neo Machine Learning for Molecules and Materials (NeurIPS Workshop) 2018 arXiv
Remark: Author names are in alphabetical ordering (unless they are not). For theory work/venues, it is standard practice to list authors by alphabetical ordering of last names.

Other writings

Title Remarks Links
Scribe notes for entire course Massively Parallel Algorithms (Spring 2019)
Lecturer: Mohsen GHAFFARI
Course webpage, Notes
Scribe notes for entire course Advanced Algorithms (Fall 2018)
Lecturer: Mohsen GHAFFARI
Course webpage, Notes

Talks

Event Date (DD.MM.YYYY) Topic Remarks Links
CS6101 Research Talk 03.09.2021 Online Algorithms with Advice: A Survey Zoom talk and discussion. Link to paper, Link to slides
Aalto CS Theory Seminar 29.07.2020 k-means++: few more steps yield constant approximation Zoom talk. arXiv
MADZ Group Meeting talk 04.05.2020 k-means++: few more steps yield constant approximation Zoom talk. arXiv
Reading Group on Discrete and Distributed Algorithms 23.05.2019 Dynamic Algorithms for the Massively Parallel Computation Model Whiteboard talk. Attached are some pictures.

The paper talks about maintaining an approximate MST but I think an exact MST should be doable. See write-up for a sketch.
Update: There's a SPAA 2020 paper related to this!
arXiv, pic1, pic2, pic3, pic4, pic5
DSO
technical sharing
02.02.2017 2^{To be, or not to be?}: A look at boolean satisfiability State-of-the-art methods building upon DPLL and CDCL are covered. An alternative solving method (Stalmarck's method) is also discussed.

Animations and some slides removed.
Slides
DSO
technical sharing
10.11.2016 A gentle introduction to community detection Common methods such as graph partitioning and spectral clustering are discussed. Talk is mainly based off a survey by Santo Fortuno.

Animations and some slides removed.
Slides

Teaching

Place Course Year Links
National University of Singapore (NUS) GET1031 / GEI1000 (Cross listed): Computational Thinking
Lecturers: LEONG Hon Wai and LEOW Wee Kheng
AY 2021/2022 Sem 1 NUSMODS
National University of Singapore (NUS) CS3230: Design and Analysis of Algorithms
Lecturer: LEE Wee Sun
AY 2015/2016 Sem 1 NUSMODS
National University of Singapore (NUS) GET1031: Computational Thinking
Lecturers: LEONG Hon Wai and LEOW Wee Kheng
AY 2015/2016 Sem 2 NUSMODS
National University of Singapore (NUS) CS2020: Data Structures and Algorithms (Accelerated)
Lecturer: Seth GILBERT
AY 2014/2015 Sem 2,
AY 2015/2016 Sem 2
NUSMODS
National University of Singapore (NUS) CS1101S: Programming Methodology
Lecturers: Martin HENZ and LOW Kok-Lim
AY 2014/2015 Sem 1 NUSMODS
National University of Singapore (NUS) CS1231: Discrete Structures
Lecturers: Stéphane BRESSAN and Bryan Kian Hsiang LOW
AY 2014/2015 Sem 1 NUSMODS
Temasek Junior College (TJC) Initialized and conducted a 12-week student outreach course on Computer Science Jan 2014 - May 2014 Some old, partial
teaching material

For fun

Name Remarks Links
IBM Ponder This puzzles Solutions to some IBM's monthly Ponder This puzzles that I attempted. Github
Neopets Shapeshifter solver Used this game as a practice while learning about constraint solvers.
Wrote a JavaScript to extract the puzzle from Neopets, which can be solved by either of my 2 solvers --- One using Google's ortools, one using the MiniZinc constraint solver.
Directory
Telegram Chess Bot Learnt about the existence of Telegram bots worked. Hacked up a chess bot for fun.
Note: It requires server hosting to work.
Github
Threshold Secret Sharing Schemes Explored and implemented 3 secret sharing schemes. Github
Cryptopals Solutions to some of the Cryptopals challenges that I attempted. Github
Cipher encodings A collection of cipher encodings. Github

About me

Masters
Computer Science
Eidgenössische Technische Hochschule Zürich (ETH Zürich)
Thesis supervisor: David STEURER

Undergraduate
Computer Science
First Class Honours

National University of Singapore (NUS)
Thesis supervisor: Seth GILBERT
UROP supervisor: LEE Wee Sun

Undergraduate
Mathematics
First Class Honours
National University of Singapore (NUS)
Thesis supervisor: Frank STEPHAN

I am currently a PhD student in the School of Computing (SoC) of National University of Singapore, under the AISG PhD Fellowship Programme. Between my undergraduate and Masters studies, I worked for a while as an applied defence scientist at DSO National Laboratories on projects that lie in the intersection of A.I. and security.

Here is my 1-page resume (Last updated: September 2021).