Publications
Remarks:
Color codes: Conferences, Journals, Others
Papers order: Papers are ordered by years their conference versions appeared. Journal names are below the conference names for papers that later appeared in journals.
Order of authors: Unless stated otherwise, author names are in alphabetical order.
Other sources: dblp, google scholar, arXiv, arnetminer, acm, microsoft, semanticscholar.
Papers by team members: see this page.
Contact: Please send an email to da..pon@gmail.com if you find any broken or outdated link.
For non-TCS audience: In theoretical computer science, the most important venues of publications are conferences and not journals. STOC and FOCS are widely recognized as the most prestigious conferences in the field worldwide, followed by SODA. Additionally, PODC is a top conference in theory of distributed algorithms. For other conferences see, e.g. the ranking by CORE and conferenceranks.com. (Aforementioned conferences are all ranked A* by CORE as of 2017.)
2023
76. Fast Algorithms via Dynamic-Oracle Matroids
with Joakim Blikstad, Ta-Wei Tu, Sagnik Mukhopadhyay
STOC 2023: 55th ACM Symposium on Theory of Computing [wiki]
Links: 📄arXiv, 🎬1h video by J.B.@ETHZ
75. Near-Linear Time Approximations for Cut Problems via Fair Cuts
with Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
SODA 2023: Annual ACM-SIAM Symposium on Discrete Algorithms
74. Fully Dynamic Exact Edge Connectivity in Sublinear Time
with Gramoz Goranci, Monika Henzinger, Thatchaphol Saranurak, Mikkel Thorup, Christian Wulff-Nilsen
SODA 2023: Annual ACM-SIAM Symposium on Discrete Algorithms
2022
73. Negative-Weight Single-Source Shortest Paths in Near-linear Time
with Aaron Bernstein, Christian Wulff-Nilsen
FOCS 2022 (Best Paper Award): 63rd Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
ICBS Frontiers of Science Award
CACM Research Highlight (Nominated by ACM SIGACT)
Links (papers/talks): 📄arXiv, 💬 slides, 🎬1h video by me@UT, 🎬1.05h video by me@Bangalore, 🎬1h video by A.B.@ETH,
Lecture notes, code, etc: 📚 lecture notes for LDD by me, 💬slides including basic SSSP algorithms by me, 📚 UCBerkeley Lecture by Nelson (2023), 📚 CMU Lecture notes by Gupta (2023) + Video, 📚 ETH Zurich Lecture by Kyng-Probst (Chapter 19), code from Yale Senior Project (2022)
Press: 📰 CACM news, 📰 Quanta Magazine, 📰 Quanta Magazine's 2023 In Review, 📰 news at Rutgers, 📰 news at DIKU & ACM TechNews
Last update: September 22, 2023
72. Nearly Optimal Communication and Query Complexity of Bipartite Matching
with Joakim Blikstad, Jan van den Brand, Yuval Efron, Sagnik Mukhopadhyay
FOCS 2022: 63rd Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Links: 📄arXiv, 🎬1h video by J.B.@TCS+, 🎬1h video by Y.E.@AIS(Princeton)
Last update: September 27, 2022
71. Cut Query Algorithms with Star Contraction
with Simon Apers, Yuval Efron, Paweł Gawrychowski, Troy Lee, Sagnik Mukhopadhyay
FOCS 2022: 63rd Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Links: 📄arXiv
Last update: July 5, 2022
70. Approximating k-Edge-Connected Spanning Subgraphs via a Near-Linear Time LP Solver
with Parinya Chalermsook, Chien-Chung Huang, Thatchaphol Saranurak, Pattara Sukprasert, Sorrachai Yingchareonthawornchai
ICALP 2022: The 49th EATCS International Colloquium on Automata, Languages, and Programming [link]
Links: 📄 arXiv
Last update: June 1, 2022
69. Fully-Dynamic Graph Sparsifiers Against an Adaptive Adversary
with Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Thatchaphol Saranurak, Aaron Sidford, He Sun
ICALP 2022: The 49th EATCS International Colloquium on Automata, Languages, and Programming [link]
Links: 📄arXiv
Last update: April 11, 2022
68. Faster Connectivity in Low-rank Hypergraphs via Expander Decomposition
with Calvin Beideman, Karthekeyan Chandrasekaran, Sagnik Mukhopadhyay
IPCO 2022: The 23rd Conference on Integer Programming and Combinatorial Optimization [link]
Last update: May 30, 2022
2021
67. Minimum Cuts in Directed Graphs via Partial Sparsification
with Ruoxu Cen, Jason Li, Debmalya Panigrahi, Kent Quanrud, Thatchaphol Saranurak
FOCS 2021: 62nd Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Links: 📄arXiv
Last update: Nov 18, 2021
66. Work-Optimal Parallel Minimum Cuts for Non-Sparse Graphs
with Andrés López-Martínez, Sagnik Mukhopadhyay
SPAA 2021: The 33th ACM Symposium on Parallelism in Algorithms and Architectures [wiki,link]
Links: 📄arXiv, 🎬Video@SPAA by A.L-M.
Last update: June 28, 2021
65. Vertex Connectivity in Poly-logarithmic Max-flows
with Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
STOC 2021 (invited to special issue): 53rd ACM Symposium on Theory of Computing [wiki,link]
Links: 📄arXiv, 🎬Video@STOC by S.Y.
Last update: June 28, 2021
64. Breaking the Quadratic Barrier for Matroid Intersection
with Joakim Blikstad, Jan van den Brand, Sagnik Mukhopadhyay
STOC 2021: 53rd ACM Symposium on Theory of Computing [wiki,link]
Links: 📄arXiv, 🎬Video@STOC by J.B., 🔗blog (in Korean)
Last update: October 5, 2023
63. Distributed Weighted Min-Cut in Nearly-Optimal Time
with Michal Dory, Yuval Efron, Sagnik Mukhopadhyay
STOC 2021: 53rd ACM Symposium on Theory of Computing [wiki,link]
Links: 📄arXiv, 🎬Video@STOC by Y.E.
Last update: June 28, 2021
62. Dynamic Set Cover: Improved Amortized and Worst-Case Update Time
with Sayan Bhattacharya, Monika Henzinger, Xiaowei Wu
SODA 2021: 32nd Annual ACM-SIAM Symposium on Discrete Algorithms [link]
SICOMP 2021: SIAM Journal on Computing [link] (the journal version combines FOCS 2019 and SODA 2021 results.)
Links: 📄arXiv
Last update: September 30, 2020
2020
61. Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
with Jan van den Brand, Yin-Tat Lee, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, Di Wang
FOCS 2020 (invited to special issue): 61st Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Links: 📄arXiv
Last update: September 4, 2020
60. A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond
with Julia Chuzhoy, Yu Gao, Jason Li, Richard Peng, Thatchaphol Saranurak
FOCS 2020: 61st Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Links: 📄arXiv
Mentioned in CMU course
Last update: July 11, 2020
59. Weighted Min-Cut: Sequential, Cut-Query and Streaming Algorithms
with Sagnik Mukhopadhyay
STOC 2020: 52nd ACM Symposium on Theory of Computing [wiki,link]
Links: 📄arXiv (Also see an independent work at arXiv:1911.01145), 🎬Video@STOC by S.M.
Last update: Feb 6, 2020
58. Computing and Testing Small Connectivity in Near-Linear Time and Queries via Fast Local Cut Algorithms
with Sebastian Forster, Thatchaphol Saranurak, Liu Yang, Sorrachai Yingchareonthawornchai
SODA 2020: 31st Annual ACM-SIAM Symposium on Discrete Algorithms [link]
Links: 📄arXiv (Older versions: [1], [2]),
Misc: 🧪Experimental result by Franck and S.Y.
Last update: Nov 4, 2019
57. Coarse-Grained Complexity for Dynamic Algorithms
with Sayan Bhattacharya, Thatchaphol Saranurak
SODA 2020: 31st Annual ACM-SIAM Symposium on Discrete Algorithms [link]
Links: 📄arXiv, 🎬video by S.B.@HALG2020
Misc: Invited talk at Highlights of Algorithms 2020
Last update: Sep 24, 2019
2019
56. Equivalence Classes and Conditional Hardness in Massively Parallel Computations
with Michele Scquizzato
OPODIS 2019: 23rd International Conference on Principles of Distributed Systems [link]
DIST 2022: Distributed Computing [link]
Links: 📄arXiv, 📄Springer(open access)
Mentioned at UIC course
Last update: Jan 11, 2020
55. A New Deterministic Algorithm for Dynamic Set Cover
with Sayan Bhattacharya, Monika Henzinger
FOCS 2019: 60th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
SICOMP 2021: SIAM Journal on Computing [link] (the journal version combines FOCS 2019 and SODA 2021 results.)
Links: 📄arXiv, 🎬video@FOCS by S.B
Last update: June 24, 2019
54. Dynamic Approximate Shortest Paths and Beyond: Subquadratic and Worst-Case Update Time
with Jan van den Brand
FOCS 2019: 60th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Links: 📄arXiv, 🎬video@FOCS by J.vdB
Last update: June 24, 2019
53. Dynamic Matrix Inverse: Improved Algorithms and Matching Conditional Lower Bounds
with Jan van den Brand, Thatchaphol Saranurak
FOCS 2019: 60th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Links: 📄arXiv, $cash prize (see last slide), 🎬video@FOCS by J.vdB
Last update: June 24, 2019
52. Breaking Quadratic Time for Small Vertex Connectivity and an Approximation Scheme
with Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
STOC 2019 (invited to special issue): 51st ACM Symposium on Theory of Computing [wiki,link]
Links: 📄arXiv,🎬video (1h) by T.S., 💬Slides by S.Y.
Misc: ⭐Oded's choice (1), (2), 🧪Experimental result by Franck and S.Y.
Last update: Sep 7, 2019
We canceled our special issue submission due to personal constraints.
51. Distributed Exact Weighted All-Pairs Shortest Paths in Near-Linear Time
with Aaron Bernstein
STOC 2019 (invited to special issue): 51st ACM Symposium on Theory of Computing [wiki,link]
SICOMP 2021: SIAM Journal on Computing [wiki]
The SICOMP version contains additional language corrections by profestionals.
Last update: Nov 15, 2021
52. Distributed Edge Connectivity in Sublinear Time
with Mohit Daga, Monika Henzinger, Thatchaphol Saranurak
STOC 2019: 51st ACM Symposium on Theory of Computing [wiki,link]
Links: 📄arXiv
Misc: Covered in Oded's choice.
Last update: Sep 7, 2019
2018
48. New Tools and Connections for Exponential-time Approximation
with Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Jesper Nederlof
Algorithmica 2019 - Special Issue: Parameterized and Exact Computation [wiki, link]
Links: 📄pdf
Last update: August 11, 2018
47. A Faster Distributed Single-Source Shortest Paths Algorithm
with Sebastian Forster
FOCS 2018: 59th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Links: 📄arXiv, 💬slides@FOCS by S.F,🎬video@FOCS by S.F.
Last update: July 1, 2018
46. Dynamic Algorithms for Graph Coloring
with Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger
SODA 2018: 29th Annual ACM-SIAM Symposium on Discrete Algorithms [link]
Links: 📄arXiv
Last update: Sep 29, 2017
2017
45. Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time
with Thatchaphol Saranurak, Christian Wulff-Nilsen
Last update: Aug 15, 2017
44. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More
with Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Luca Trevisan
Last update: Aug 15, 2017
43. Distributed Exact Weighted All-Pairs Shortest Paths in $\tilde O(n^{5/4})$ Rounds
with Chien-Chung Huang, Thatchaphol Saranurak
Last update: Aug 15, 2017
42. Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n^{1/2−ε})-Time
with Thatchaphol Saranurak
Last update: June 20, 2020
41.Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log^3 n) Worst Case Update Time.
with Sayan Bhattacharya, Monika Henzinger
Last update: Oct 7, 2016
2016
40. Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization (survey)
with Monika Henzinger and Sebastian Krinninger
Encyclopedia of Algorithms.
Last update: Mar 30, 2017
39. Some Challenges on Distributed Shortest Paths Problems, A Survey
SIROCCO 2016 (invited talk): Structural Information and Communication Complexity
Last update: Nov 7, 2016
38. New Deterministic Approximation Algorithms for Fully Dynamic Matching
with Sayan Bhattacharya, Monika Henzinger
Last update: Feb 1, 2016
37. A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths
with Monika Henzinger, Sebastian Krinninger
Last update: June 21, 2018
2015
36. Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
with Monika Henzinger, Sebastian Krinninger
The full version combines ICALP'15 and STOC'14 papers.
Last update: Dec 10, 2018
35. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams
with Sayan Bhattacharya, Monika Henzinger, Charalampos E. Tsourakakis
Last update: Apr 14, 2015
34. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
with Monika Henzinger, Sebastian Krinninger, Thatchaphol Saranurak
Last update: Apr 14, 2015
33. Social Network Monetization via Sponsored Viral Marketing
with Parinya Chalermsook, Atish Das Sarma, Ashwin Lall
Last update: Feb 8, 2015
32. The Distributed Complexity of Large-scale Graph Processing
with Hartmut Klauck, Gopal Pandurangan, Peter Robinson
Last update: Sep 14, 2014
2014
31. Distributed Symmetry Breaking in Hypergraphs
with Shay Kutten, Gopal Pandurangan, Peter Robinson
Last update: August 6, 2014
30. Almost-Tight Distributed Minimum Cut Algorithms
with Hsin-Hao Su
Last update: August 6, 2014
29. Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
with Monika Henzinger, Sebastian Krinninger
Last update: Apr 22, 2020
28. Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs
with Parinya Chalermsook, Bundit Laekhanukit
Last update: August 6, 2014
27. Can Quantum Communication Speed Up Distributed Computation?
with Michael Elkin, Hartmut Klauck, Gopal Pandurangan
Last update: Apr 20, 2014
26. Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs
with Monika Henzinger, Sebastian Krinninger
The full version combines STOC'14 and ICALP'15 papers. For the previous full version of the STOC'14 paper, see here
Last update: Dec 10, 2018
25. Distributed Approximation Algorithms for Weighted Shortest Paths
Links: 📄arXiv, 💬slides, 🎬video@stoc14, 📚MIT Lecture (2022,2014), 📚ETHZ Lecture (2014), 📚Weizmann Lecture (2021)
Last update: Sep 1, 2019
24. A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths
with Monika Henzinger, Sebastian Krinninger
Last update: October 13, 2013
23. Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation
with Parinya Chalermsook, Bundit Laekhanukit
Last update: April 11, 2014
2013
22. Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization
with Monika Henzinger, Sebastian Krinninger
FOCS2013 (invited to special issue): 54th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
SICOMP 2016 special issue: SIAM Journal on Computing (Special issue for papers invited from FOCS 2013) [wiki,link]
Links: 📄full version@arXiv, 📄survey, poster by S.K, 🎬video@FOCS by S.K.
Misc: Covered at: Bar-Ilan Course
Last update: September May 28, 2015
21. Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses
with Parinya Chalermsook, Bundit Laekhanukit
FOCS 2013: 54th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Links: abstract, 📄full version@arXiv, 🎬video@FOCS by P.C. and B.L.
Last update: August 13, 2013
20. Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More
with Parinya Chalermsook, Bundit Laekhanukit
SODA 2013: 24th Annual ACM-SIAM Symposium on Discrete Algorithms [link]
Last update: Jan 15, 2013
19. Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks
with Monika Henzinger, Sebastian Krinninger
ICALP 2013: 40th International Colloquium on Automata, Languages and Programming [wiki,link]
TALG 2017: ACM Transactions on Algorithms [link]
Links: 📄arXiv
The preprint of the TALG version is on arXiv.
Last update: Aug 6, 2019
18. Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs
with Parinya Chalermsook, Shiva Kintali, Richard J. Lipton
CJTCS 2013: Chicago Journal of Theoretical Computer Science [link]
Links: 📄arXiv, 📄journal version
Last update: November 12, 2013
17. Simple FPTAS for the Subset-Sums Ratio Problem
IPL 2013: Information Processing Letters [wiki,link]
Links: 📄pdf(preprint), 📄pdf(Elsevier)
Last update: July 28, 2013
16. An Approximate Restatement of the Four Color Theorem
with Atish Das Sarma, Amita Gajewar, Richard J. Lipton
JGAA 2013: Journal of Graph Algorithms and Applications [wiki,link]
Links: detail, 📄pdf(preprint), 📄pdf(JGAA), 🔗blog by R.J.L + 🔗related
Last update: June 29, 2013
2012
15. Interactive Regret Minimization
Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Kazuhisa Makino
SIGMOD 2012: the ACM SIGMOD International Conference on Management of Data [wiki]
Links: 🔗detail, 📄pdf, 📄@ACM(free), 💬slides
Author names are NOT in alphabetical order.
Last update: Mar 14, 2012
14. Dense Subgraphs on Dynamic Networks
with Atish Das Sarma, Ashwin Lall, Amitabh Trehan
DISC 2012: 26th International Symposium on Distributed Computing [wiki]
PODC 2012 (Brief Announcement): 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing [wiki]
Links: 📄arXiv, 🔗conference spoiler by A.T.
Presented at Umass Course
Last update: Jan 13, 2013
13. Polynomial-time Algorithms for Energy Games with Special Weight Structures
with Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger
ESA 2012 (invited to special issue): European Symposium on Algorithms [wiki]
Algorithmica 2014 special issue (for papers invited from ESA 2012) [wiki, link]
Last update: Nov 14, 2013
2011
12. Distributed Verification and Hardness of Distributed Approximation
with Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Gopal Pandurangan, David Peleg, Roger Wattenhofer
STOC 2011 (invited to special issue): 43rd ACM Symposium on Theory of Computing [wiki]
SICOMP 2012 special issue: SIAM Journal on Computing (Special issue for papers invited from STOC 2011) [wiki, link]
Links: detail, 📄pdf@sicomp, 📄pdf(arXiv), 🎬video@stoc11, 💬slides(short), 💬slides(long)
Misc: Covered at MIT Course, MPI Course, Freiburg Course, Paderborn Course, Weizmann Course, Heinz Nixdorf Institut Course, Sterling's blog
Note: SICOMP version = ArXiv v3 version + some grammatical errors fixed. Additional links: pdf@ACM(free), pdf@sicomp.
Last update: Nov 25, 2014
11. A Tight Unconditional Lower Bound on Distributed Random Walk Computation
Danupon Nanongkai, Atish Das Sarma, Gopal Pandurangan
PODC 2011: 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing [wiki]
Links: detail, 📄pdf (arXiv), 📄@ACM(free), 💬slides
Author names are NOT in alphabetical order.
Last update: Oct 15, 2011
10. Representative Skylines using Threshold-based Preference Distributions
Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Richard J. Lipton, Jun Xu
ICDE 2011: the IEEE International Conference on Data Engineering [link]
Misc: Selected as an excellent paper for 2011 by Cortes and Spector on GoogleAI blog.
Author names are NOT in alphabetical order.
Last update: November 25, 2014
2010
9. Regret-Minimizing Representative Databases
Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Richard J. Lipton, Jun Xu
VLDB 2010: 36th International Conference on Very Large Data Bases [wiki]
Author names are NOT in alphabetical order.
8. Efficient Distributed Random Walks with Applications
with Atish Das Sarma, Gopal Pandurangan, Prasad Tetali
PODC 2010: 29th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing [wiki]
JACM 2013: Journal of the ACM [wiki, link]
Links: detail, 📄arXiv of journal version, 📄arXiv - conf version, 📄pdf@acm(free conf version)
Journal version combines PODC 2009 and PODC 2010 papers
Suggested at: ETHZ Course
Last update: Feb 19, 2013
7. Faster Algorithms for Semi-Matching Problems
with Jittat Fakcharoenphol, Bundit Laekhanukit
ICALP 2010: 37th International Colloquium on Automata, Languages and Programming [wiki]
TALG 2014: ACM Transactions on Algorithms [link]
The preprint of the TALG version is on arXiv.
Last update: August 17, 2014
6. Improved Hardness of Approximation for Stackelberg Shortest-Path Pricing
with Patrick Briest, Parinya Chalermsook, Sanjeev Khanna, Bundit Laekhanukit
WINE 2010 (short paper): 6th Workshop on Internet & Network Economics [wiki]
This paper is a merge of two preprints: arXiv:0910.0443 and arXiv:0910.0110
2009 and Earlier
5. Randomized Multi-pass Streaming Skyline Algorithms
with Atish Das Sarma, Ashwin Lall, Jun Xu
VLDB 2009: 35th International Conference on Very Large Data Bases [wiki]
4. Fast Distributed Random Walks
with Atish Das Sarma, Gopal Pandurangan
PODC 2009: 28th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing [wiki]
JACM 2013: Journal of the ACM [wiki]
Links: detail, 📄pdf (arXiv of journal version), 📄pdf (conf version), 💬pptx, 📄pdf@acm (free)
(Journal version combines PODC 2009 and PODC 2010 papers)
Last update: Feb 19, 2013
3. Best-Order Streaming Model
with Atish Das Sarma, Richard J. Lipton
TAMC 2009 (invited to special issue): 6th Annual Conference on Theory and Applications of Models of Computation
TCS 2011 special issue: Theoretical Computer Science, Volume 412, Number 23, May 2011. (Special issue for papers invited from TAMC 2009) [wiki]
Links: detail, 📄pdf (preprint), 💬ppt, 🔗blog by R.J.L., 🔗link to the journal
Misc: Taught at Aarhus, Suggested reading at Georgetown course
Suggested at George Town Course
2. A Deterministic Nearly Linear-time Algorithm for Finding Minimum Cuts in Planar Graphs
with Jittat Fakcharoenphol, Parinya Chalermsook
SODA 2004 (short paper): 15th Annual ACM-SIAM Symposium on Discrete Algorithms
Links: detail, 📄pdf, 💬slides by J.F.
1. Detecting and Cleaning Intruders in Sensor Networks
Poonna Yospanya, Bundit Laekhanukit, Danupon Nanongkai, Jittat Fakcharoenphol
Author names are NOT in alphabetical order.
NCSEC 2004: 8th National Computer Science and Engineering Conference [link]
PhD Thesis
Graph and Geometric Algorithms on Distributed Networks and Databases
PhD Thesis 2011: Dissertation for the PhD degree in Algorithms, Combinatorics, and Optimization (ACO), Georgia Tech, USA, 2011.
Thesis advisor: Prof. Richard J. Lipton.
Principles of Distributed Computing Doctoral Dissertation Award 2013 (co-winner) [link].
Others
Parallel and Distributed Exact Single-Source Shortest Paths with Negative Edge Weights
with Vikrant Ashvinkumar, Aaron Bernstein, Nairen Cao, Christoph Grunau, Bernhard Haeupler, Yonggang Jiang, Hsin Hao Su
Manuscript 2023
Links: 📄arXiv
Interview as an ERC Grantee from Southeast Asia
EURAXESS ASEAN Quarterly Newsletter, Issue No. 1, 2017
Links: 📄pdf
Geometric Pricing: How Low Dimensionality Helps in Approximability
with Parinya Chalermsook, Khaled Elbassioni, He Sun
Manuscript 2012
Links: 📄arXiv
Minimum Cuts in Directed Graphs via $\sqrt{n}$ Max-Flows
with Ruoxu Cen, Jason Li, Debmalya Panigrahi, Thatchaphol Saranurak
Subsumed by the FOCS'21 paper.
Last update: Aug 17, 2021
Deterministic Graph Cuts in Subquadratic Time: Sparse, Balanced, and k-Vertex
with Yu Gao, Jason Li, Richard Peng, Thatchaphol Saranurak, Sorrachai Yingchareonthawornchai
Last update: Oct 18, 2019
This manuscript is the merge of several results. Parts of it were submitted to FOCS'19 and SODA'20. Part of it has since been subsumed by a new result involving a subset of the authors. It's uploaded in its current form due to its significant technical overlap with the improved result. We expect to upload splitted, more up to date, versions of this in the near future
A Note on Isolating Cut Lemma for Submodular Function Minimization
with Sagnik Mukhopadhyay
Links: 📄arXiv
Last update: April 2, 2021
Co-authors (81)
Vikrant Ashvinkumar
Nikhil Bansal
Sebastian Forster (Krinninger)
Ta-Wei Tu
Liu Yang
Sorrachai Yingchareonthawornchai
Poonna Yospanya