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
  • Strong Lower Bounds for Weak Epsilon-Nets
    (Preprint) Sujoy Bhore, Reilly Browne, and Da Wei Zheng
  • 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
  • Improved Approximation and Hardness Bounds for β-TSP
    (Preprint) Paul Liu, Jack Spalding-Jamieson, and Da Wei Zheng
  • Real-Weighted Diameter and Eccentricities of Minor-Free and Bounded VC-Dimension Graphs in Truly Subquadratic Time
    (ESA 2026) Da Wei Zheng
  • 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
  • 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
  • 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
  • Cutting Planarians: Planar Emulators for String Graphs
    (STOC 2026) Hsien-Chih Chang, Jonathan Conroy, Zihan Tan, and Da Wei Zheng

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
  • 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
  • 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
  • Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
    (SODA 2025) Adam Karczmarz and Da Wei Zheng
  • Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
    (Math. Prog. Series B 2025) Da Wei Zheng and Monika Henzinger
  • 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

2024

  • Shortest Path Separators in Unit Disk Graphs
    (ESA 2024) Elfarouk Harb, Zhengcheng Huang, and Da Wei Zheng
  • 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
  • Carving Polytopes with Saws in 3D
    (CCCG 2024) Eliot W. Robson, Jack Spalding-Jamieson, and Da Wei Zheng
  • Semialgebraic Range Stabbing, Ray Shooting, and Intersection Counting in the Plane
    (SoCG 2024) Timothy M. Chan, Pingan Cheng, and Da Wei Zheng
  • Fully Scalable Massively Parallel Algorithms for Embedded Planar Graphs
    (SODA 2024) Yi-Jun Chang and Da Wei Zheng
  • 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
  • Hopcroft’s Problem, Log* Shaving, Two-dimensional Fractional Cascading, and Decision Trees
    (TALG 2024) Timothy M. Chan and Da Wei Zheng

2023

  • Multiplicative Auction Algorithm for Approximate Maximum Weight Bipartite Matching
    (IPCO 2023) Da Wei Zheng and Monika Henzinger
  • 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
  • Faster Submodular Maximization for Several Classes of Matroids
    (ICALP 2023) Monika Henzinger, Paul Liu, Jan Vondrák, and Da Wei Zheng
  • Halving by a Thousand Cuts or Punctures
    (SODA 2023) Sariel Har-Peled and Da Wei Zheng
  • Simplex Range Searching Revisited: How to Shave Logs in Multi-Level Data Structures
    (SODA 2023) Timothy M. Chan and Da Wei Zheng

2022

  • Conflict-Based Local Search for Minimum Partition into Plane Subgraphs
    (SoCG 2022) Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng
  • Hopcroft’s Problem, Log-Star Shaving, 2D Fractional Cascading, and Decision Trees
    (SODA 2022) Timothy M. Chan and Da Wei Zheng
  • Coordinated Motion Planning Through Randomized k-Opt
    (JEA 2022) Paul Liu, Jack Spalding-Jamieson, Brandon Zhang, and Da Wei Zheng

2021

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

2020

  • Scheduling queries to moving entities to certify many are distant from a region
    (Master’s Thesis) Da Wei Zheng
  • 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

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.