Di Wang

Publications

• Deterministic Near-Linear Time Minimum Cut in Weighted Graphs.
  Monika Henzinger, Jason Li, Satish Rao, Di Wang
  SODA 2024 (best paper award).

• Prior-Independent Auctions for Heterogeneous Bidders.
  Guru Guruganesh, Aranyak Mehta, Di Wang, Kangning Wang
  SODA 2024. [arXiv]

• Robust Budget Pacing with a Single Sample.
  Santiago Balseiro, Rachitesh Kumar, Vahab Mirrokni, Balasubramanian Sivan, Di Wang
  ICML 2023 (oral presentation).

• Online Bidding Algorithms for Return-on-Spend Constrained Advertisers.
  Zhe Feng, Swati Padmanabhan, Di Wang
  The Web Conference (WWW) 2023. [arXiv]

• Targeted pandemic containment through identifying local contact network bottlenecks.
  Shenghao Yang, Priyabrata Senapati, Di Wang, Chris T Bauch, Kimon Fountoulakis
  PLoS computational biology, Volume 17, Issue 8, August 2021. . [link]

• Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training.
  Goran Zuzic, Di Wang, Aranyak Mehta, D Sivakumar
  ICLR 2022 Workshop on Gamification and Multiagent Solutions. [arXiv]

• Minimum cost flows, MDPs, and ℓ1-regression in nearly linear time for dense instances.
  Jan Van Den Brand, Yin Tat Lee, Yang P Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
  STOC 2021. [arXiv]

• 2-norm Flow Diffusion in Near-Linear Time.
  Li Chen, Richard Peng, Di Wang
  FOCS 2021. [arXiv]

• Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs.
  Jan van den Brand, Yin-Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
  FOCS 2020. [arXiv]

• p-Norm Flow Diffusion for Local Graph Clustering.
  Kimon Fountoulakis, Di Wang, Shenghao Yang
  In ICML 2020. [arXiv]

• Greedy: An Iterative Peeling Algorithm for Dense Subgraph Discovery.
  Digvijay Boob, Yu Gao, Richard Peng, Saurabh Sawlani, Charalampos E. Tsourakakis, Di Wang, Junxing Wang
  In TheWebConf (WWW) 2020. [arXiv]

• Packing LPs are Hard to Solve Accurately, Assuming Linear Equations are Hard.
  Rasmus Kyng, Di Wang, Peng Zhang
  In SODA 2020.

• Faster Width-dependent Algorithm for Mixed Packing and Covering LPs.
  Digvijay Boob, Saurabh Sawlani, Di Wang
  In Neurips 2019 (accepted for oral presentation). [arXiv]

• Flows in Almost Linear Time via Adaptive Preconditioning.
  Rasmus Kyng, Richard Peng, Sushant Sachdeva, Di Wang
  In STOC 2019. [arXiv]

• Expander Decomposition and Pruning: Faster, Stronger, and Simpler.
  Thatchaphol Saranurak, Di Wang
  In SODA 2019. [arXiv]

• Fast Approximation Algorithms for Positive Linear Programs.
  Di Wang
  My PhD Dissertation. [link]

• Capacity Releasing Diffusion for Speed and Locality.
  Di Wang, Kimon Fountoulakis, Monika Henzinger, Michael W Mahoney, Satish Rao
  In ICML 2017. [arXiv][talk]
  Implemented in Local Graph Clustering codebase.

• Local Flow Partitioning for Faster Edge Connectivity.
  Monika Henzinger, Satish Rao, Di Wang
  SIAM Journal on Computing, Volume 49, Issue 1, Page 1-36, January 2020.
  Preliminary version in SODA 2017. [arXiv]

• Approximating the Solution to Mixed Packing and Covering LPs in Parallel Time.
  Michael W Mahoney, Satish Rao, Di Wang, Peng Zhang
  In ICALP 2016. [pdf]

• Unified Acceleration Method for Packing and Covering Problems via Diameter Reduction.
  Di Wang, Satish Rao, Michael W Mahoney
  In ICALP 2016. [arXiv]

• Faster Parallel Solver for Positive Linear Programs via Dynamically-bucketed Selective Coordinate Descent.
  Di Wang, Michael Mahoney, Nishanth Mohan, Satish Rao
  Technical Report, Preprint: arXiv:1511.06468 (2015). [arXiv]

• On the security of trustee-based social authentications.
  Neil Zhenqiang Gong, Di Wang
  In IEEE Trans. on Information Forensics and Security, Vol.9, No.8, August 2014.

• Analyzing Quadratic Unconstrained Binary Optimization Problems Via Multicommodity Flows.
  Di Wang, Robert Kleinberg
  Discrete Applied Mathematics 157 (18) (2009) 3746-3753.