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.

Most of my recent works involve designing and analyzing algorithms for learning causal and probabilistic models, as well as learning-augmented algorithms. I am happy to discuss any of them in detail :)

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
Links

Publications

Title Authors Venue Year Links
Learnability of Parameter-Bounded Bayes Nets Arnab Bhattacharyya, Davin Choo, Sutanu Gayen, Dimitrios Myrisiotis Workshop on Structured Probabilistic Inference & Generative Modeling (ICML Workshop) 2024 arXiv
Online bipartite matching with imperfect advice Davin Choo, Themistoklis Gouleakis, Chun Kai Ling, Arnab Bhattacharyya International Conference on Machine Learning (ICML) 2024 Conference link, ICML, Code, arXiv
Envy-free house allocation with minimum subsidy Davin Choo, Yan Hao Ling, Warut Suksompong, Nicholas Teh, Jian Zhang Operations Research Letters (ORL) 2024 ORL, arXiv
Causal discovery under off-target interventions Davin Choo, Kirankumar Shiragur, Caroline Uhler International Conference on Artificial Intelligence and Statistics (AISTATS) 2024 AISTATS, Code, arXiv
Learning bounded degree polytrees with samples Davin Choo, Joy Qiping Yang, Arnab Bhattacharyya, Clément L. Canonne International Conference on Algorithmic Learning Theory (ALT) 2024 ALT, arXiv
The Sharp Power Law of Local Search on Expanders Simina Brânzei, Davin Choo, Nicholas Recker Symposium on Discrete Algorithms (SODA) 2024 SODA, arXiv
Learning and Testing Latent-Tree Ising Models Efficiently Yuval Dagan, Constantinos Daskalakis, Anthimos-Vardis Kandiros, Davin Choo Conference on Learning Theory (COLT) 2023 Conference link, COLT, arXiv
Adaptivity Complexity for Causal Graph Discovery Davin Choo, Kirankumar Shiragur Conference on Uncertainty in Artificial Intelligence (UAI) 2023 UAI, Code, arXiv, Video
New metrics and search algorithms for weighted causal DAGs Davin Choo, Kirankumar Shiragur International Conference on Machine Learning (ICML) 2023 Conference link, ICML, Code, arXiv
Active causal structure learning with advice Davin Choo, Themistoklis Gouleakis, Arnab Bhattacharyya International Conference on Machine Learning (ICML) 2023 Conference link, ICML, Code, arXiv
Subset verification and search algorithms for causal DAGs Davin Choo, Kirankumar Shiragur International Conference on Artificial Intelligence and Statistics (AISTATS) 2023 AISTATS, Code, arXiv, Video
Verification and search algorithms for causal DAGs Davin Choo, Kirankumar Shiragur, Arnab Bhattacharyya Conference on Neural Information Processing Systems (NeurIPS) 2022 Conference link, NeurIPS, Code, arXiv, Slides, Longer slides
Learning Sparse Fixed-Structure Gaussian Bayesian Networks Arnab Bhattacharyya, Davin Choo, Rishikesh Gajjala, Sutanu Gayen, Yuhao Wang International Conference on Artificial Intelligence and Statistics (AISTATS) 2022 AISTATS, Code, arXiv
The Complexity of Sparse Tensor PCA Davin Choo, Tommaso d'Orsi Conference on Neural Information Processing Systems (NeurIPS) 2021 Conference link, NeurIPS, arXiv, Video, Slides
Massively Parallel Correlation Clustering in Bounded Arboricity Graphs Mélanie Cambus, Davin Choo, Havu Miikonen, Jara Uitto International Symposium on Distributed Computing (DISC) 2021 DISC, arXiv, Video
k-means++: few more steps yield constant approximation Davin Choo, Christoph Grunau, Julian Portmann, Václav Rozhoň International Conference on Machine Learning (ICML) 2020 Conference link, ICML, arXiv, Video, Slides
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 DATE, Paper, arXiv, Code, Kuldeep's website link
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 often standard practice to list authors by alphabetical ordering of last names.

Other writings

Title Remarks Links
Template for NUS SoC Thesis (and Thesis Proposal) - Overleaf (Read-only)
Uncovering Causal Relationships Using Adaptive Interventions General audience research article AISG ConnectAI article
Template for NUS SoC QE talk slides - Overleaf (Read-only)
Template for NUS SoC QE report - Overleaf (Read-only)
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 / Talk title Location / Remarks Links
Doctoral Seminar 09.09.2024 Algorithms for Learning Probabilistic and Causal Models with Possible Imperfect Advice SR12, COM3 01-21 Slides
Workshop on Learning-Augmented Algorithms 19.08.2024 Online bipartite matching with imperfect advice (Lightning talk) TTIC, Chicago, IL Paper, Slides
NUS AlgoTheory Seminar 10.06.2024 Online bipartite matching with imperfect advice MR-20 @ COM3 (COM3-02-59) Paper, Slides
NUS AlgoTheory Seminar 08.04.2024 Envy-free house allocation with minimum subsidy MR-20 @ COM3 (COM3-02-59) Paper, Slides
Guest presentation at CS6235 03.04.2024 Envy-free house allocation with minimum subsidy SR@LT19 Paper, Slides
Divesh's research group weekly seminar 15.03.2024 Online bipartite matching with imperfect advice COM3-02-70. Whiteboard talk -
MPI EI Tea talks 10.08.2023 Recovering causal graphs with adaptive interventions N 4.022 Slides
NUS AlgoTheory Seminar 17.04.2023 Learning causal DAGs using adaptive interventions Seminar Room @ LT19 (BIZ 2) Slides
NUS SoC AlgoTheory Group Meeting 24.03.2023 Solving problems using imperfect advice COM3-02-59 Slides
CS6235 Paper Presentation 08.03.2023 Partitioning Friends Fairly LT19 Seminar Room Paper, Slides
Computing Research Week - Open House 2023 24.02.2023 Learning Causal DAGs using Adaptive Interventions Multipurpose Hall 1 (COM3-01-26) Slides
CS6220 Paper Presentation 02.02.2022 Triad Constraints for Learning Causal Structure of Latent Variables Zoom talk and discussion. Paper, Slides
CS6101 Paper Presentation 03.09.2021 Online Algorithms with Advice: A Survey Zoom talk and discussion. Paper, 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 / Outreach

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

Service

  • Reviewer for Conference on Neural Information Processing Systems (NeurIPS), 2024
  • Reviewer for International Conference on Machine Learning (ICML), 2024
  • Reviewer for International Joint Conference on Artificial Intelligence (IJCAI), 2024
  • Reviewer for International Conference on Artificial Intelligence and Statistics (AISTATS), 2024
  • Subreviewer for Innovations in Theoretical Computer Science (ITCS), 2024
  • Reviewer for Conference on Neural Information Processing Systems (NeurIPS), 2023; Top reviewer
  • Subreviewer for Symposium on Theory of Computing (STOC), 2023
  • Subreviewer for International Colloquium on Automata, Languages, and Programming (ICALP), 2023
  • Reviewer for International Conference on Artificial Intelligence and Statistics (AISTATS), 2023
  • Subreviewer for Conference on Learning Theory (COLT), 2022
  • Subreviewer for Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2022
  • Subreviewer for European Symposium on Algorithms (ESA), 2020

For fun

Remarks Links
Recommendations for visiting singapore I have had given recommendations to various people on multiple occasions so I thought it would be nice to collate it somewhere so that I can just point to a link in the future :) Internal link
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

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

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
Awards (that I am grateful for receiving)
  • NUS School of Computing Research Achievement Award (Awarded in 2023)
  • AISG PhD Fellowship (Awarded in 2021)
  • President's Honour Roll, USP Scholar (Awarded in 2016)
  • DSTA-DSO Undergraduate Scholarship (Awarded in 2011)
Visits / Experiences / Opportunities (which I was fortunate to have)
Here is my resume (Last updated: July 2024).