
About
Hi, I’m David. I’m a postdoctoral researcher in Monika Henzinger’s group at the Institute of Science and Technology Austria (ISTA). I work in theoretical computer science with a focus on graph algorithms and computational geometry.
I received my PhD in computer science from the University of Illinois Urbana-Champaign in 2025, advised by Timothy M. Chan. My dissertation received the 2025 CCCG Best PhD Dissertation Award. Before that, I completed an MSc in computer science, advised by Will Evans, and a BSc in combined honours computer science and mathematics at the University of British Columbia.
I am currently on the academic job market.
Email: dzheng at institutename.ac.at · CV (Last updated Nov 2026) · Google Scholar · DBLP
Research
A recurring theme in my research is using geometric structure to design faster algorithms.
Graph algorithms using geometry. I study distances and related problems in planar, minor-free, and geometric intersection graphs, including diameter algorithms, distance oracles, and planar emulators.
Computational and discrete geometry. My work focuses primarily on geometric range searching. I have also looked at incidence problems and weak ε-nets.
Combinatorial optimization. I have also worked on approximation algorithms and data structures for matching, submodular optimization, and TSP.
Service
I serve on the program committees of ESA 2026 and SoCG 2027. I received an Outstanding Reviewer Award for SoCG 2025.
I also review for conferences and journals in theoretical computer science. A detailed service record is available in my CV.
Publications
2026
-
Faster Planar Diameter using Pseudoline Envelopes
(Preprint) Da Wei Zheng and Daniel Prigan
@misc{ZhengP26, author = {Zheng, Da Wei and Prigan, Daniel}, title = {Faster Planar Diameter using Pseudoline Envelopes}, year = {2026}, conference = {Preprint}, url = {https://arxiv.org/abs/2611.05019}, arxiv = {https://arxiv.org/abs/2611.05019} } -
Strong Lower Bounds for Weak Epsilon-Nets
(Preprint) Sujoy Bhore, Reilly Browne, and Da Wei Zheng
@misc{BhoreBZ26, author = {Bhore, Sujoy and Browne, Reilly and Zheng, Da Wei}, title = {Strong Lower Bounds for Weak Epsilon-Nets}, year = {2026}, conference = {Preprint}, url = {https://arxiv.org/abs/2610.40982}, arxiv = {https://arxiv.org/abs/2610.40982} } -
Can LLMs be Used to Simplify Algorithms? Simpler Algorithms
for Vertex Coloring and Edge Connectivity
(Preprint) Antoine El-Hayek, Monika Henzinger, and Da Wei Zheng
@misc{ElHayekHZ26, author = {El-Hayek, Antoine and Henzinger, Monika and Zheng, Da Wei}, title = {Can {LLMs} be Used to Simplify Algorithms? Simpler Algorithms for Vertex Coloring and Edge Connectivity}, year = {2026}, conference = {Preprint}, url = {https://arxiv.org/abs/2608.10753}, arxiv = {https://arxiv.org/abs/2608.10753} } -
Improved Approximation and Hardness Bounds for β-TSP
(Preprint) Paul Liu, Jack Spalding-Jamieson, and Da Wei Zheng
@misc{LiuSZ26, author = {Liu, Paul and Spalding{-}Jamieson, Jack and Zheng, Da Wei}, title = {Improved Approximation and Hardness Bounds for {$\beta$}-{TSP}}, year = {2026}, conference = {Preprint}, url = {https://arxiv.org/abs/2611.09421}, arxiv = {https://arxiv.org/abs/2611.09421} } -
Real-Weighted Diameter and Eccentricities of Minor-Free and Bounded
VC-Dimension Graphs in Truly Subquadratic Time
(ESA 2026) Da Wei Zheng
@inproceedings{Zheng26, author = {Zheng, Da Wei}, editor = {Bille, Philip and Pettie, Seth and Storandt, Sabine}, title = {Real-Weighted Diameter and Eccentricities of Minor-Free and Bounded VC-Dimension Graphs in Truly Subquadratic Time}, booktitle = {34th Annual European Symposium on Algorithms, {ESA} 2026, L'Aquila, Italy, August 31 - September 4, 2026}, series = {LIPIcs}, volume = {388}, pages = {61:1--61:12}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2026}, conference = {ESA 2026}, url = {https://doi.org/10.4230/LIPIcs.ESA.2026.61}, doi = {10.4230/LIPICS.ESA.2026.61}, arxiv = {https://arxiv.org/abs/2607.01926} } -
DAG Covers for Structured Graphs: The Steiner Point Effect
(ESA 2026) Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy, Arnold Filtser, Eunjin Oh, Nicole Wein, and Da Wei Zheng
@inproceedings{BhoreCCFOWZ26, author = {Bhore, Sujoy and Chang, Hsien{-}Chih and Conroy, Jonathan and Filtser, Arnold and Oh, Eunjin and Wein, Nicole and Zheng, Da Wei}, editor = {Bille, Philip and Pettie, Seth and Storandt, Sabine}, title = {{DAG} Covers for Structured Graphs: The Steiner Point Effect}, booktitle = {34th Annual European Symposium on Algorithms, {ESA} 2026, L'Aquila, Italy, August 31 - September 4, 2026}, series = {LIPIcs}, volume = {388}, pages = {94:1--94:18}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2026}, conference = {ESA 2026}, url = {https://doi.org/10.4230/LIPIcs.ESA.2026.94}, doi = {10.4230/LIPICS.ESA.2026.94}, arxiv = {https://arxiv.org/abs/2604.04186} } -
Charting the Landscape of Diameter Computation on Geometric Intersection
Graphs in the Plane
(ICALP 2026) Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng
@inproceedings{ChanCGKLZ26-2, author = {Chan, Timothy M. and Chang, Hsien{-}Chih and Gao, Jie and Kisfaludi{-}Bak, S{\'{a}}ndor and Le, Hung and Zheng, Da Wei}, editor = {Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele}, title = {Charting the Landscape of Diameter Computation on Geometric Intersection Graphs in the Plane}, booktitle = {53rd International Colloquium on Automata, Languages, and Programming, {ICALP} 2026, Royal Holloway, University of London, Egham, United Kingdom, July 7-10, 2026}, series = {LIPIcs}, volume = {374}, pages = {54:1--54:22}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2026}, conference = {ICALP 2026}, url = {https://doi.org/10.4230/LIPIcs.ICALP.2026.54}, doi = {10.4230/LIPICS.ICALP.2026.54}, arxiv = {https://arxiv.org/abs/2605.10692} } -
Charting the Diameter Computation Landscape of Intersection Graphs
in 3D and Above
(SoCG 2026) Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, Hung Le, and Da Wei Zheng
@inproceedings{ChanCGKLZ26-3, author = {Chan, Timothy M. and Chang, Hsien{-}Chih and Gao, Jie and Kisfaludi{-}Bak, S{\'{a}}ndor and Le, Hung and Zheng, Da Wei}, editor = {Ahn, Hee{-}Kap and Hoffmann, Michael and Nayyeri, Amir}, title = {Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above}, booktitle = {42nd International Symposium on Computational Geometry, SoCG 2026, New Brunswick, NJ, USA, June 2-5, 2026}, series = {LIPIcs}, volume = {367}, pages = {29:1--29:15}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, year = {2026}, conference = {SoCG 2026}, url = {https://doi.org/10.4230/LIPIcs.SoCG.2026.29}, doi = {10.4230/LIPICS.SOCG.2026.29}, arxiv = {https://arxiv.org/abs/2603.21790} } -
Cutting Planarians: Planar Emulators for String Graphs
(STOC 2026) Hsien-Chih Chang, Jonathan Conroy, Zihan Tan, and Da Wei Zheng
@inproceedings{ChangCTZ26, author = {Chang, Hsien{-}Chih and Conroy, Jonathan and Tan, Zihan and Zheng, Da Wei}, editor = {Bhaskara, Aditya and Czumaj, Artur}, title = {Cutting Planarians: Planar Emulators for String Graphs}, booktitle = {Proceedings of the 58th Annual {ACM} Symposium on Theory of Computing, {STOC} 2026, Salt Lake City, UT, USA, June 22-26, 2026}, pages = {2140--2151}, publisher = {{ACM}}, year = {2026}, conference = {STOC 2026}, url = {https://doi.org/10.1145/3798129.3800917}, doi = {10.1145/3798129.3800917}, timestamp = {Thu, 25 Jun 2026 10:35:08 +0200}, arxiv = {https://arxiv.org/abs/2510.21700} }
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 = {https://arxiv.org/abs/2510.16346}, arxiv = {https://arxiv.org/abs/2510.16346} } -
Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
(ICML 2025) 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}, url = {https://icml.cc/virtual/2025/poster/43715}, arxiv = {https://arxiv.org/abs/2505.09010}, 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}, booktitle = {Proceedings of the 1st Workshop on Vector Databases at the International Conference on Machine Learning, {ICML} 2025}, 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, decremental 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, decremental 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} } -
Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
(Math. Prog. Series B 2025) 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 = {210}, number = {1-2}, pages = {881--894}, year = {2025}, url = {https://doi.org/10.1007/s10107-024-02066-3}, doi = {10.1007/s10107-024-02066-3}, conference = {Math. Prog. Series B 2025}, arxiv = {https://arxiv.org/abs/2301.09217}, slides = {assets/matching_auction_slides.pdf} } -
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 2024) 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:1--24:27}, 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 2024}, arxiv = {https://arxiv.org/abs/2111.03744}, slides = {assets/SODA22_Hopcroft_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} }
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
[Nov 2026] New preprint: Faster Planar Diameter using Pseudoline Envelopes, with Daniel Prigan.
[Oct 2026] New preprint: Strong Lower Bounds for Weak Epsilon-Nets, with Sujoy Bhore and Reilly Browne.
[Aug 2026] New preprint: Can LLMs be Used to Simplify Algorithms? Simpler Algorithms for Vertex Coloring and Edge Connectivity, with Antoine El-Hayek and Monika Henzinger.
[Feb 2026] Our paper Cutting Planarians: Planar Emulators for String Graphs, with Hsien-Chih Chang, Jonathan Conroy, and Zihan Tan, was accepted to STOC 2026!
[Feb 2026] Our paper Charting the Diameter Computation Landscape of Intersection Graphs in 3D and Above, with Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, and Hung Le, was accepted to SoCG 2026.
[Oct 2025] I joined ISTA as a postdoctoral researcher working with Monika Henzinger!
[Sep 2025] Congratulations to UIUC team Ippatsu on placing 20th at the ICPC World Finals in Baku! I also received an award recognizing five years of coaching teams to the World Finals.
[Aug 2025] I received the Best PhD Dissertation Award at CCCG 2025!
[Jul 2025] Our paper Truly Subquadratic Time Algorithms for Diameter and Related Problems in Graphs of Bounded VC-dimension, with Timothy M. Chan, Hsien-Chih Chang, Jie Gao, Sándor Kisfaludi-Bak, and Hung Le, was accepted to FOCS 2025.
[Jul 2025] Our paper Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time, with Gramoz Goranci, Peter Kiss, Neel Patel, Martin Seybold, and Eva Szilagyi, was presented by Eva as an oral presentation at ICML 2025.
[May 2025] I graduated with my PhD from UIUC! Thanks to David Eppstein for serving as my external examiner and for the kind mention on his blog.
[May 2025] UIUC team Ippatsu won the ICPC North America Championship! Congratulations to Dilhan Salgado, Yuuki Sawanoi, and Zhikun Wang.
[Mar 2025] I received an Outstanding Reviewer Award for SoCG 2025.
[Oct 2024] Our paper Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more, with Adam Karczmarz, was accepted to SODA 2025!
[Sep 2024] I coached the UIUC team at the ICPC World Finals in Astana, Kazakhstan, where they finished joint 51st.
[Jul 2024] Started this news section.
Mentoring and other interests
I have been involved in competitive programming as a participant, coach, and contest organizer. I competed at the ICPC World Finals in 2018 and 2019 and have coached teams at UBC and UIUC.
I have also participated in Capture the Flag competitions in the past. Some of my writeups are available on my blog.