About

Hi, I’m David. I am a postdoctoral researcher at IST Austria working with Monika Henzinger. I was a PhD student in Computer Science at the University of Illinois at Urbana-Champaign (UIUC) where I was fortunate enough to be advised by Timothy M. Chan. I completed a BSc in Combined Honours Computer Science and Mathematics and a MSc in Computer Science at the University of British Columbia (UBC) with Will Evans.

You can see a list of my papers here and my CV here, or if you prefer Google Scholar or DBLP. For recent personal updates, see here.

Research

My interests lie in theoretical computer science, predominantly in algorithms and data structures pertaining to geometry or graphs.

I enjoyed some early success with geometric optimization challenges (CG:SHOP 2020, CG:SHOP 2021, CG:SHOP 2022). Since then, I’ve worked on geometric data structures, (Hopcroft’s problem, cuttings, simplex semi-algebraic range searching, Voronoi diagrams), and data structures for combinatorial optimization (matchings, submodular optimization). Lately I’ve been thinking about problems in geometric graphs (UDGs, matchings), planar graphs (MPC, steiner trees), and minor-free graphs (diameter and distance oracles).

Service. I’ve been a subreviewer for the conferences: SODA 2026, SOSA 2026, ESA 2025, SoCG 2025 (Outstanding Reviewer Award), SODA 2025, SOSA 2025, ALENEX 2025, ESA 2024, ICALP 2024, STACS 2024, SoCG 2024, APPROX 2023, ESA 2023, ICALP 2023, SODA 2023, ESA 2022, and SoCG 2022.

I’ve also reviewed for the journals CGTA, JCST, JEA, and Operation Research Letters.

Publications

2025

Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension
(FOCS 2025) Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng
```
@inproceedings{ChanCGKLZ25,
  author = {Chan, Timothy M. and Chang, Hsien-Chih and Gao, Jie and Kisfaludi-Bak, Sándor and Le, Hung and Zheng, Da Wei},
  title = {Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension},
  booktitle = {66th Annual Symposium on Foundations of Computer Science, {FOCS} 2025,
                    Sydney, Australia, December 14-17, 2025},
  conference = {FOCS 2025},
  year = {2025},
  url = {}
}
```
Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
(ICML 2025 [Oral presentation]) Gramoz Goranci, Peter Kiss, Neel Patel, Martin Seybold, Eva Szilagyi, and Da Wei Zheng
```
@inproceedings{GoranciKPSSZ24,
  author = {Goranci, Gramoz and Kiss, Peter and Patel, Neel and Seybold, Martin and Szilagyi, Eva and Zheng, Da Wei},
  title = {Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time},
  booktitle = {Forty-second International Conference on Machine Learning, {ICML} 2025,
                    Vancouver, Canada, July 13-19, 2025},
  publisher = {OpenReview.net},
  year = {2025},
  conference = {ICML 2025 [Oral presentation]},
  url = {https://icml.cc/virtual/2025/poster/43715},
  arxiv = {https://icml.cc/virtual/2025/poster/43715},
  note = {Oral Presentation}
}
```
Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search
(ICML 2025 VecDB Workshop) Jack Spalding-Jamieson, Eliot W. Robson, and Da Wei Zheng
```
@article{SpaldingJamiesonRZ24,
  author = {Spalding-Jamieson, Jack and Robson, Eliot W. and Zheng, Da Wei},
  title = {Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search},
  year = {2025},
  conference = {ICML 2025 VecDB Workshop},
  url = {https://openreview.net/forum?id=rFurXwjJfW},
  arxiv = {https://doi.org/10.48550/arXiv.2502.06163}
}
```

Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decrementai reachability, and more
(SODA 2025) Adam Karczmarz and Da Wei Zheng

@inproceedings{KarczmarzZ24,
  author = {Karczmarz, Adam and Zheng, Da Wei},
  editor = {Azar, Yossi and Panigrahi, Debmalya},
  title = {Subquadratic algorithms in minor-free digraphs: (weighted) distance
                    oracles, decrementai reachability, and more},
  booktitle = {Proceedings of the 2025 Annual {ACM-SIAM} Symposium on Discrete Algorithms,
                    {SODA} 2025, New Orleans, LA, USA, January 12-15, 2025},
  pages = {4338--4351},
  publisher = {{SIAM}},
  year = {2025},
  url = {https://doi.org/10.1137/1.9781611978322.147},
  conference = {SODA 2025},
  slides = {assets/soda25_vc.pdf},
  arxiv = {https://doi.org/10.48550/arXiv.2410.12003}
}

Polynomial-Time Algorithms for Contiguous Art Gallery and Related Problems
(SoCG 2025) Ahmad Biniaz, Anil Maheshwari, Magnus Christian Ring Merrild, Joseph S. B. Mitchell, Saeed Odak, Valentin Polishchuk, Eliot W. Robson, Casper Moldrup Rysgaard, Jens Kristian Refsgaard Schou, Thomas C. Shermer, Jack Spalding-Jamieson, Rolf Svenning, and Da Wei Zheng

@inproceedings{BiniazMMMOPRRSS25,
  author = {Biniaz, Ahmad and Maheshwari, Anil and Merrild, Magnus Christian Ring and Mitchell, Joseph S. B. and Odak, Saeed and Polishchuk, Valentin and Robson, Eliot W. and Rysgaard, Casper Moldrup and Schou, Jens Kristian Refsgaard and Shermer, Thomas C. and Spalding{-}Jamieson, Jack and Svenning, Rolf and Zheng, Da Wei},
  editor = {Aichholzer, Oswin and Wang, Haitao},
  title = {Polynomial-Time Algorithms for Contiguous Art Gallery and Related
                    Problems},
  booktitle = {41st International Symposium on Computational Geometry, SoCG 2025,
                    June 23-27, 2025, Kanazawa, Japan},
  series = {LIPIcs},
  volume = {332},
  pages = {20:1--20:21},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2025},
  conference = {SoCG 2025},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2025.20},
  doi = {10.4230/LIPICS.SOCG.2025.20},
  arxiv = {https://arxiv.org/abs/2412.15567},
  note = {Merger of 3 papers}
}

2024

Shortest Path Separators in Unit Disk Graphs
(ESA 2024) Elfarouk Harb, Zhengcheng Huang, and Da Wei Zheng

@inproceedings{HarbHZ24,
  author = {Harb, Elfarouk and Huang, Zhengcheng and Zheng, Da Wei},
  title = {{Shortest Path Separators in Unit Disk Graphs}},
  booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages = {66:1--66:14},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  isbn = {978-3-95977-338-6},
  issn = {1868-8969},
  year = {2024},
  volume = {308},
  editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.66},
  urn = {urn:nbn:de:0030-drops-211375},
  doi = {10.4230/LIPIcs.ESA.2024.66},
  conference = {ESA 2024},
  arxiv = {https://doi.org/10.48550/arXiv.2407.15980}
}

From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs
(ESA 2024) Chandra Chekuri, Rhea Jain, Shubhang Kulkarni, Da Wei Zheng, and Weihao Zhu

@inproceedings{ChekuriJKZZ24,
  author = {Chekuri, Chandra and Jain, Rhea and Kulkarni, Shubhang and Zheng, Da Wei and Zhu, Weihao},
  title = {{From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs}},
  booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages = {42:1--42:19},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  isbn = {978-3-95977-338-6},
  issn = {1868-8969},
  year = {2024},
  volume = {308},
  editor = {Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.42},
  urn = {urn:nbn:de:0030-drops-211134},
  doi = {10.4230/LIPIcs.ESA.2024.42},
  conference = {ESA 2024},
  arxiv = {https://doi.org/10.48550/arXiv.2407.01904}
}

Carving Polytopes with Saws in 3D
(CCCG 2024) Eliot W. Robson, Jack Spalding-Jamieson, and Da Wei Zheng

@inproceedings{RobsonSZ24,
  author = {Robson, Eliot W. and Spalding-Jamieson, Jack and Zheng, Da Wei},
  title = {Carving Polytopes with Saws in {3D}},
  booktitle = {Proceedings of the 36th Canadian Conference on Computational Geometry,
                    {CCCG} 2024, Brock University, St. Catherines, Ontario, Canada, July
                    17 - July 19, 2024},
  pages = {145--151},
  year = {2024},
  conference = {CCCG 2024},
  url = {https://cosc.brocku.ca/~rnishat/CCCG_2024_proceedings.pdf},
  arxiv = {https://doi.org/10.48550/arXiv.2407.15981}
}

Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane
(SoCG 2024) Timothy M. Chan, Pingan Cheng, and Da Wei Zheng

@inproceedings{ChanCZb24,
  author = {Chan, Timothy M. and Cheng, Pingan and Zheng, Da Wei},
  editor = {Mulzer, Wolfgang and Phillips, Jeff M.},
  title = {Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting
                    in the Plane},
  booktitle = {40th International Symposium on Computational Geometry, SoCG 2024,
                    June 11-14, 2024, Athens, Greece},
  series = {LIPIcs},
  volume = {293},
  pages = {33:1--33:15},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2024},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2024.33},
  doi = {10.4230/LIPICS.SOCG.2024.33},
  biburl = {https://dblp.org/rec/conf/compgeom/ChanCZ24.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SoCG 2024},
  arxiv = {https://doi.org/10.48550/arXiv.2403.12303}
}

Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs
(SODA 2024) Yi-Jun Chang and Da Wei Zheng

@inproceedings{ChangZ24,
  author = {Chang, Yi{-}Jun and Zheng, Da Wei},
  editor = {Woodruff, David P.},
  title = {Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs},
  booktitle = {Proceedings of the 2024 {ACM-SIAM} Symposium on Discrete Algorithms,
                    {SODA} 2024, Alexandria, VA, USA, January 7-10, 2024},
  pages = {4410--4450},
  publisher = {{SIAM}},
  year = {2024},
  url = {https://doi.org/10.1137/1.9781611977912.155},
  doi = {10.1137/1.9781611977912.155},
  biburl = {https://dblp.org/rec/conf/soda/ChangZ24.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SODA 2024},
  arxiv = {https://arxiv.org/abs/2304.07441},
  slides = {assets/soda24_mpc.pdf}
}

An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane: The Usefulness of Nondeterminism
(SODA 2024) Timothy M. Chan, Pingan Cheng, and Da Wei Zheng

@inproceedings{ChanCZ24,
  author = {Chan, Timothy M. and Cheng, Pingan and Zheng, Da Wei},
  editor = {Woodruff, David P.},
  title = {An Optimal Algorithm for Higher-Order Voronoi Diagrams in the Plane:
                    The Usefulness of Nondeterminism},
  booktitle = {Proceedings of the 2024 {ACM-SIAM} Symposium on Discrete Algorithms,
                    {SODA} 2024, Alexandria, VA, USA, January 7-10, 2024},
  pages = {4451--4463},
  publisher = {{SIAM}},
  year = {2024},
  url = {https://doi.org/10.1137/1.9781611977912.156},
  doi = {10.1137/1.9781611977912.156},
  biburl = {https://dblp.org/rec/conf/soda/ChanCZ24.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SODA 2024},
  arxiv = {https://arxiv.org/abs/2310.15363},
  slides = {assets/soda24_voronoi_slides.pdf}
}

Hopcroft’s Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision Trees
(TALG 2022) Timothy M. Chan and Da Wei Zheng

@article{ChanZ24,
  author = {Chan, Timothy M. and Zheng, Da Wei},
  title = {Hopcroft's Problem, Log* Shaving, Two-dimensional Fractional
                    Cascading, and Decision Trees},
  journal = {{ACM} Trans. Algorithms},
  volume = {20},
  number = {3},
  pages = {24},
  year = {2024},
  url = {https://doi.org/10.1145/3591357},
  doi = {10.1145/3591357},
  biburl = {https://dblp.org/rec/journals/talg/ChanZ24.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {TALG 2022},
  arxiv = {https://arxiv.org/abs/2111.03744},
  slides = {assets/SODA22_Hopcroft_Slides.pdf}
}

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
(Math. Prog. Series B) Da Wei Zheng and Monika Henzinger
```
@article{ZhengH24,
  author = {Zheng, Da Wei and Henzinger, Monika},
  title = {Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching},
  journal = {Math. Prog. Series B},
  volume = {20},
  number = {3},
  pages = {24},
  year = {2024},
  url = {https://doi.org/10.1007/s10107-024-02066-3},
  doi = {10.1007/s10107-024-02066-3},
  conference = {Math. Prog. Series B},
  arxiv = {https://arxiv.org/abs/2301.09217},
  slides = {assets/matching_auction_slides.pdf}
}
```

2023

Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
(IPCO 2023) Da Wei Zheng and Monika Henzinger

@inproceedings{ZhengH23,
  author = {Zheng, Da Wei and Henzinger, Monika},
  editor = {Pia, Alberto Del and Kaibel, Volker},
  title = {Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite
                    Matching},
  booktitle = {Integer Programming and Combinatorial Optimization - 24th International
                    Conference, {IPCO} 2023, Madison, WI, USA, June 21-23, 2023, Proceedings},
  series = {Lecture Notes in Computer Science},
  volume = {13904},
  pages = {453--465},
  publisher = {Springer},
  year = {2023},
  url = {https://doi.org/10.1007/978-3-031-32726-1\_32},
  doi = {10.1007/978-3-031-32726-1\_32},
  biburl = {https://dblp.org/rec/conf/ipco/ZhengH23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {IPCO 2023},
  arxiv = {https://arxiv.org/abs/2301.09217},
  slides = {assets/matching_auction_slides.pdf}
}

Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring
(JEA 2023) Loïc Crombez, Guilherme Dias da Fonseca, Florian Fontan, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso, Benjamin Momège, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng

@article{CrombezFFGGLLMSZZ23,
  author = {Crombez, Lo{\"{i}}c and da Fonseca, Guilherme Dias and Fontan, Florian and Gerard, Yan and Gonzalez{-}Lorenzo, Aldo and Lafourcade, Pascal and Libralesso, Luc and Mom{\`{e}}ge, Benjamin and Spalding{-}Jamieson, Jack and Zhang, Brandon and Zheng, Da Wei},
  title = {Conflict Optimization for Binary {CSP} Applied to Minimum Partition
                    into Plane Subgraphs and Graph Coloring},
  journal = {{ACM} J. Exp. Algorithmics},
  volume = {28},
  pages = {1.2:1--1.2:13},
  year = {2023},
  url = {https://doi.org/10.1145/3588869},
  doi = {10.1145/3588869},
  biburl = {https://dblp.org/rec/journals/jea/CrombezFFGGLLMSZZ23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {JEA 2023},
  arxiv = {https://arxiv.org/abs/2303.09632}
}

Faster Submodular Maximization for Several Classes of Matroids
(ICALP 2023) Monika Henzinger, Paul Liu, Jan Vondrák, and Da Wei Zheng

@inproceedings{HenzingerLVZ23,
  author = {Henzinger, Monika and Liu, Paul and Vondr{\'{a}}k, Jan and Zheng, Da Wei},
  editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
  title = {Faster Submodular Maximization for Several Classes of Matroids},
  booktitle = {50th International Colloquium on Automata, Languages, and Programming,
                    {ICALP} 2023, July 10-14, 2023, Paderborn, Germany},
  series = {LIPIcs},
  volume = {261},
  pages = {74:1--74:18},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2023},
  url = {https://doi.org/10.4230/LIPIcs.ICALP.2023.74},
  doi = {10.4230/LIPIcs.ICALP.2023.74},
  biburl = {https://dblp.org/rec/conf/icalp/HenzingerLVZ23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {ICALP 2023},
  arxiv = {https://arxiv.org/abs/2305.00122},
  slides = {assets/icalp2023_submod.pdf}
}

Halving by a Thousand Cuts or Punctures
(SODA 2023) Sariel Har-Peled and Da Wei Zheng

@inproceedings{HarPeledZ23,
  author = {Har{-}Peled, Sariel and Zheng, Da Wei},
  editor = {Bansal, Nikhil and Nagarajan, Viswanath},
  title = {Halving by a Thousand Cuts or Punctures},
  booktitle = {Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms,
                 {SODA} 2023, Florence, Italy, January 22-25, 2023},
  pages = {1385--1397},
  publisher = {{SIAM}},
  year = {2023},
  url = {https://doi.org/10.1137/1.9781611977554.ch49},
  doi = {10.1137/1.9781611977554.ch49},
  biburl = {https://dblp.org/rec/conf/soda/Har-PeledZ23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SODA 2023},
  arxiv = {https://arxiv.org/abs/2208.11275},
  slides = {assets/SODA23_Cuts_Punctures.pdf}
}

Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures
(SODA 2023) Timothy M. Chan and Da Wei Zheng

@inproceedings{ChanZ23,
  author = {Chan, Timothy M. and Zheng, Da Wei},
  editor = {Bansal, Nikhil and Nagarajan, Viswanath},
  title = {Simplex Range Searching Revisited: How to Shave Logs in Multi-Level
                 Data Structures},
  booktitle = {Proceedings of the 2023 {ACM-SIAM} Symposium on Discrete Algorithms,
                 {SODA} 2023, Florence, Italy, January 22-25, 2023},
  pages = {1493--1511},
  publisher = {{SIAM}},
  year = {2023},
  url = {https://doi.org/10.1137/1.9781611977554.ch54},
  doi = {10.1137/1.9781611977554.ch54},
  biburl = {https://dblp.org/rec/conf/soda/ChanZ23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SODA 2023},
  arxiv = {https://arxiv.org/abs/2210.10172},
  slides = {assets/SODA23_Multilevel_slides.pdf}
}

@article{CrombezFFGGLLMSZZ24,
  author = {Crombez, Lo{\"{i}}c and da Fonseca, Guilherme Dias and Fontan, Florian and Gerard, Yan and Gonzalez{-}Lorenzo, Aldo and Lafourcade, Pascal and Libralesso, Luc and Mom{\`{e}}ge, Benjamin and Spalding{-}Jamieson, Jack and Zhang, Brandon and Zheng, Da Wei},
  title = {Conflict Optimization for Binary {CSP} Applied to Minimum Partition
                    into Plane Subgraphs and Graph Coloring},
  journal = {{ACM} J. Exp. Algorithmics},
  volume = {28},
  pages = {1.2:1--1.2:13},
  year = {2023},
  url = {https://doi.org/10.1145/3588869},
  doi = {10.1145/3588869},
  biburl = {https://dblp.org/rec/journals/jea/CrombezFFGGLLMSZZ23.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {JEA 2023},
  arxiv = {https://arxiv.org/abs/2303.09632}
}

2022

Conflict-Based Local Search for Minimum Partition into Plane Subgraphs
(SoCG 2022) Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng

@inproceedings{SpaldingJamiesonZZ22,
  author = {Spalding-Jamieson, Jack and Zhang, Brandon and Zheng, Da Wei},
  title = {{Conflict-Based Local Search for Minimum Partition into Plane Subgraphs}},
  booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
  pages = {72:1--72:6},
  series = {Leibniz International Proceedings in Informatics (LIPIcs)},
  isbn = {978-3-95977-227-3},
  issn = {1868-8969},
  year = {2022},
  volume = {224},
  editor = {Goaoc, Xavier and Kerber, Michael},
  publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address = {Dagstuhl, Germany},
  url = {https://drops.dagstuhl.de/opus/volltexte/2022/16080},
  urn = {urn:nbn:de:0030-drops-160807},
  doi = {10.4230/LIPIcs.SoCG.2022.72},
  conference = {SoCG 2022},
  annote = {Keywords: local search, planar graph, graph colouring, geometric graph, conflict optimizer}
}

Hopcroft’s Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees
(SODA 2022) Timothy M. Chan and Da Wei Zheng

@inproceedings{ChanZ22,
  author = {Chan, Timothy M. and Zheng, Da Wei},
  editor = {Naor, Joseph (Seffi) and Buchbinder, Niv},
  title = {Hopcroft's Problem, Log-Star Shaving, 2D Fractional Cascading, and
                 Decision Trees},
  booktitle = {Proceedings of the 2022 {ACM-SIAM} Symposium on Discrete Algorithms,
                 {SODA} 2022, Virtual Conference / Alexandria, VA, USA, January 9 -
                 12, 2022},
  pages = {190--210},
  publisher = {{SIAM}},
  year = {2022},
  url = {https://doi.org/10.1137/1.9781611977073.10},
  doi = {10.1137/1.9781611977073.10},
  biburl = {https://dblp.org/rec/conf/soda/ChanZ22.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SODA 2022},
  arxiv = {https://arxiv.org/abs/2111.03744},
  slides = {assets/SODA22_Hopcroft_Slides.pdf}
}

Coordinated Motion Planning Through Randomized k-Opt
(JEA 2022) Paul Liu, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng

@article{LiuSZZ22,
  author = {Liu, Paul and Spalding{-}Jamieson, Jack and Zhang, Brandon and Zheng, Da Wei},
  title = {Coordinated Motion Planning Through Randomized \emph{k}-Opt},
  journal = {{ACM} J. Exp. Algorithmics},
  volume = {27},
  pages = {3.4:1--3.4:9},
  year = {2022},
  url = {https://doi.org/10.1145/3524134},
  doi = {10.1145/3524134},
  biburl = {https://dblp.org/rec/journals/jea/LiuSZZ22.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {JEA 2022},
  arxiv = {https://arxiv.org/abs/2103.15062}
}

2021

Coordinated Motion Planning Through Randomized k-Opt (CG Challenge)
(SoCG 2021) Paul Liu, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng

@inproceedings{LiuSZZ21,
  author = {Liu, Paul and Spalding{-}Jamieson, Jack and Zhang, Brandon and Zheng, Da Wei},
  editor = {Buchin, Kevin and {\'{E}}ric Colin de Verdi{\`{e}}re},
  title = {Coordinated Motion Planning Through Randomized k-Opt {(CG} Challenge)},
  booktitle = {37th International Symposium on Computational Geometry, SoCG 2021,
                 June 7-11, 2021, Buffalo, NY, {USA} (Virtual Conference)},
  series = {LIPIcs},
  volume = {189},
  pages = {64:1--64:8},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2021},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2021.64},
  doi = {10.4230/LIPIcs.SoCG.2021.64},
  biburl = {https://dblp.org/rec/conf/compgeom/LiuSZZ21.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  conference = {SoCG 2021},
  arxiv = {https://arxiv.org/abs/2103.15062}
}

2020

Scheduling queries to moving entities to certify many are distant from a region
(Master’s Thesis) Da Wei Zheng
```
@mastersthesis{ZhengMasters,
  series = {Electronic Theses and Dissertations (ETDs) 2008+},
  title = {Scheduling queries to moving entities to certify many are distant from a region},
  url = {https://open.library.ubc.ca/collections/ubctheses/24/items/1.0392883},
  doi = {http://dx.doi.org/10.14288/1.0392883},
  school = {University of British Columbia},
  author = {Zheng, Da Wei},
  year = {2020},
  collection = {Electronic Theses and Dissertations (ETDs) 2008+},
  conference = {Master's Thesis}
}
```

Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized Local Search and Constraint Programming (CG Challenge)
(SoCG 2020) Da Wei Zheng, Jack Spalding-Jamieson, and Brandon Zhang

@inproceedings{ZhengSZ20,
  author = {Zheng, Da Wei and Spalding{-}Jamieson, Jack and Zhang, Brandon},
  editor = {Cabello, Sergio and Chen, Danny Z.},
  title = {Computing Low-Cost Convex Partitions for Planar Point Sets with Randomized
                 Local Search and Constraint Programming {(CG} Challenge)},
  booktitle = {36th International Symposium on Computational Geometry, SoCG 2020,
                 June 23-26, 2020, Z{\"{u}}rich, Switzerland},
  series = {LIPIcs},
  volume = {164},
  pages = {83:1--83:7},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year = {2020},
  url = {https://doi.org/10.4230/LIPIcs.SoCG.2020.83},
  doi = {10.4230/LIPIcs.SoCG.2020.83},
  biburl = {https://dblp.org/rec/conf/compgeom/ZhengSZ20.bib},
  conference = {SoCG 2020},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

News

Inspired by others, I’ve started updating my website with news.

[Aug 2025] I recieved the CCCG 2025 PhD Dissertation Award!

[July 2025] “Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension” coauthored with Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, and Hung Le gave the first subquadratic algorithm for diameter in unit-disk graphs was accepted to FOCS 2025.

[May 2025] I graduated! Thanks David Eppstein for serving as my external examiner and mentioning me in his blog.

[May 2025] UIUC ICPC team Ippatsu got first place at the North American Championships! Congrats to Dilhan Salgado, Yuuki Sawanoi, and Zhikun Wang.

[Mar 2025] I recieved an Outstanding Reviewer Award for SoCG 2025.

[Jan 2025] “Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time” coauthored with Gramoz Goranci, Peter Kiss, Neel Patel, Martin Seybold, and Eva Szilagyi recieved an oral presentation slot (given to ~1% of accepted papers) at ICML 2025 where it was presented by Eva.

[Oct 2024] “Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more” coauthored with Adam Karczmarz got accepted to SODA25! The paper is about subquadratic algorithms in minor-free graphs.

[Aug 2024] Coached UIUC team at ICPC WF 2024 in Kazakhstan where the team got 51st place.

[Jul 2024] Started news section.

Other Activities

I was involved in competitive programming at UBC. I went to ICPC World Finals 2018 and 2019, and was the coach of UBC teams 2019-2021. I coached UIUC teams 2022-2025.

I started playing in some Capture the Flag (CTF) events for fun in 2021-2022. You can see some of my writeups here.