Davin Choo

I am currently actively exploring opportunities to apply principled algorithmic techniques to solve real-world problems and create a positive social impact. During my PhD, my works primarily focused on designing and analyzing algorithms for learning causal and probabilistic models, as well as learning-augmented algorithms.

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
davinchoo [at] seas.harvard.edu
Links

Publications

Title Authors Venue Year Links
Learning multivariate Gaussians with imperfect advice Arnab Bhattacharyya, Davin Choo, Philips George John, Themis Gouleakis International Conference on Machine Learning (ICML) 2025 Conference link, arXiv
Probably approximately correct high-dimensional causal effect estimation given a valid adjustment set Davin Choo, Chandler Squires, Arnab Bhattacharyya, David Sontag Conference on Causal Learning and Reasoning (CLeaR) 2025 Conference link, arXiv
Learnability of Parameter-Bounded Bayes Nets Arnab Bhattacharyya, Davin Choo, Sutanu Gayen, Dimitrios Myrisiotis AAAI Conference on Artificial Intelligence (AAAI) 2025 AAAI, 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
Adaptive Frontier Exploration on Graphs with Applications to Network-Based Disease Testing Joint work with Yuqi Pan, Tonghan Wang, Milind Tambe, Alastair van Heerden, and Cheryl Johnson arXiv
Learning-Augmented Online Bipartite Fractional Matching Joint work with Billy Jin and Yongho Shin arXiv
Product Distribution Learning with Imperfect Advice Joint work with Arnab Bhattacharyya, Philips George John, and Themis Gouleakis arXiv link coming soon
Learning Probabilistic and Causal Models with(out) Imperfect Advice My PhD thesis! PhD Thesis
A partition cover approach to tokenization Joint work with Jia Peng Lim, Shawn Tan, and Hady W. Lauw arXiv
A short note about the learning-augmented secretary problem Joint work with Chun Kai Ling arXiv
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
PhD Defence 13.01.2025 Learning Probabilistic and Causal Models with(out) Imperfect Advice Zoom Slides
DSO
technical sharing		 03.10.2024 Algorithms for Learning Probabilistic and Causal Models with Possible Imperfect Advice DSO Playground Slides
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), 2025
  • Reviewer for Transactions on Machine Learning Research (TMLR), 2025
  • Reviewer for International Conference on Machine Learning (ICML), 2025
  • Reviewer for International Joint Conference on Artificial Intelligence (IJCAI), 2025
  • Reviewer for Conference on Neural Information Processing Systems (NeurIPS), 2024; Top reviewer
  • 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 postdoctoral fellow at Teamcore at Harvard SEAS, under Milind Tambe. I did my PhD under the (co-)supervision of Arnab Bhattacharyya and Seth Gilbert in the School of Computing (SoC) of National University of Singapore (NUS), 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.

PhD
Computer Science
PhD Thesis


National University of Singapore (NUS)
PhD advisor: Arnab BHATTACHARYYA
PhD co-advisor: Seth GILBERT

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

Undergraduate
Computer Science
First Class Honours

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

Undergraduate
Mathematics
First Class Honours
National University of Singapore (NUS)
Thesis advisor: 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: May 2025).