Publications



Remarks: 
  • Color codes: ConferencesJournalsOthers
  • 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: dblpgoogle scholararnetmineracmmicrosoft, semanticscholar
  • 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. (Note however that there is a high degree of disagreement on the use of this ranking; see e.g. a discussion from 2006.) Additionally, PODC is a top conference in theory of distributed algorithms, and VLDB, SIGMOD and ICDE are top conferences in databases. For other conferences see, e.g. the ranking by CORE. Aforementioned conferences are all ranked A* by CORE (as of 2017).
 

2018


46. Dynamic Algorithms for Graph Coloring [pdf-soon]
with Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger
SODA 201829th Annual ACM-SIAM Symposium on Discrete Algorithms [link]
Last update: Sep 29, 2017 

2017


45. Dynamic Minimum Spanning Forest with Subpolynomial Worst-case Update Time [pdf@arXiv]
with Thatchaphol Saranurak, Christian Wulff-Nilsen
FOCS 201758th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Last update: Aug 15, 2017 

44. From Gap-ETH to FPT-Inapproximability: Clique, Dominating Set, and More [pdf@arXiv]
with Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Luca Trevisan
FOCS 201758th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Last update: Aug 15, 2017 

43. Distributed Exact Weighted All-Pairs Shortest Paths in $\tilde O(n^{5/4})$ Rounds [pdf@arXiv]
with Chien-Chung Huang, Thatchaphol Saranurak
FOCS 201758th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Last update: Aug 15, 2017 

42. Dynamic Spanning Forest with Worst-Case Update Time: Adaptive, Las Vegas, and O(n^{1/2−ε})-Time [pdf@arXiv]
with Thatchaphol Saranurak
STOC 201749th ACM Symposium on Theory of Computing [wiki,link]
Covered at CMU
Last update: Feb 7, 2017 

41. Fully Dynamic Maximum Matching and Vertex Cover in O(log^3 n) Worst Case Update Time [pdf@arXiv]
with Sayan Bhattacharya, Monika Henzinger
SODA 201728th Annual ACM-SIAM Symposium on Discrete Algorithms [link]
Last update: Oct 7, 2016 

2016


40. Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization (survey) [link]
with Monika Henzinger and Sebastian Krinninger
Encyclopedia of Algorithms.
Last update: Mar 30, 2017 

39. Some Challenges on Distributed Shortest Paths Problems, A Survey [link (see front matter)]
SORICCO 2016 (invited talk)Structural Information and Communication Complexity 
Last update: Nov 7, 2016 

38. New Deterministic Approximation Algorithms for Fully Dynamic Matching [pdf@arXivslides]
with Sayan Bhattacharya, Monika Henzinger
STOC 201648th ACM Symposium on Theory of Computing [wiki,link]
Covered at CMU
Last update: Feb 1, 2016 

37. A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths [pdf@arXiv]
with Monika Henzinger, Sebastian Krinninger
STOC 201648th ACM Symposium on Theory of Computing [wiki,link]
SICOMP 201x special issue: SIAM Journal on Computing (Special issue for selected papers from STOC 2016) [wiki]
Covered at CMU
Last update: July 30, 2016 


2015

36. Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs [pdf@arXiv]
with Monika Henzinger, Sebastian Krinninger
ICALP 2015: 42nd International Colloquium on Automata, Languages and Programming [wiki,link]
The full version combines ICALP'15 and STOC'14 papers. 
Last update: Apr 30, 2015

35. Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streams [pdf@arXiv]
with Sayan Bhattacharya, Monika Henzinger, Charalampos E. Tsourakakis
STOC 201547th ACM Symposium on Theory of Computing [wiki,link]
Last update: Apr 14, 2015 

34. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture [pdf@arXivslides by T.S.]
with Monika Henzinger, Sebastian Krinninger, Thatchaphol Saranurak
STOC 201547th ACM Symposium on Theory of Computing [wiki,link]
Covered at Charles Univ
Last update: Apr 14, 2015 

33. Social Network Monetization via Sponsored Viral Marketing [pdf(preprint)]
with Parinya Chalermsook, Atish Das Sarma, Ashwin Lall
SIGMETRICS 2015: ACM International Conference on Measurement and Modeling of Computer Systems [wiki,link]
Last update: Feb 8, 2015 

32. The Distributed Complexity of Large-scale Graph Processing [pdf@arxiv]
with Hartmut Klauck, Gopal Pandurangan, Peter Robinson
SODA 201526th Annual ACM-SIAM Symposium on Discrete Algorithms [link]
Last update: Sep 14, 2014 

2014

31. Distributed Symmetry Breaking in Hypergraphs [pdf@arxiv]
with Shay Kutten, Gopal Pandurangan, Peter Robinson
DISC 201428th International Symposium on Distributed Computing [wiki]
Last update: August 6, 2014

30. Almost-Tight Distributed Minimum Cut Algorithms [pdf@arxiv]
with Hsin-Hao Su
DISC 201428th International Symposium on Distributed Computing [wiki]
Preliminary versions appeared as brief announcements at PODC 2014 and SPAA 2014.
Last update: August 6, 2014

29. Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time [pdf@arxivvideo@focs14]
with Monika Henzinger, Sebastian Krinninger
FOCS 201455th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Last update: August 6, 2014

28. Pre-Reduction Graph Products: Hardnesses of Properly Learning DFAs and Approximating EDP on DAGs [pdf@arxiv, videos by P.C. (@focs, @Hausdorff)]
with Parinya Chalermsook, Bundit Laekhanukit
FOCS 201455th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Last update: August 6, 2014

27. Can Quantum Communication Speed Up Distributed  Computation? [pdf@arXiv]
with Michael Elkin, Hartmut Klauck, Gopal Pandurangan
PODC 201433rd Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing [wiki]
Last update: Apr 20, 2014

26. Sublinear-Time Decremental Algorithms for Single-Source Reachability and Shortest Paths on Directed Graphs [pdf@arXivpptxvideo@stoc14]
with Monika Henzinger, Sebastian Krinninger
STOC 201446th ACM Symposium on Theory of Computing [wiki]
The full version combines STOC'14 and ICALP'15 papers. For the previous full version of the STOC'14 paper, see here
Covered at: Bar-Ilan
Last update: Apr 30, 2015 

25. Distributed Approximation Algorithms for Weighted Shortest Paths [pdf@arXivpptxvideo@stoc14]
STOC 201446th ACM Symposium on Theory of Computing [wiki]
Covered at: MIT
Last update: Oct 8, 2014

24. A Subquadratic-Time Algorithm for Decremental Single-Source Shortest Paths [pdf (full version)pdf(conf version)]
with Monika Henzinger, Sebastian Krinninger
SODA 2014: 25th Annual ACM-SIAM Symposium on Discrete Algorithms [link]
Last update: October 13, 2013

23. Coloring Graph Powers: Graph Product Bounds and Hardness of Approximation [pdf(conference)pdf(full - a bit outdated)]
with Parinya Chalermsook, Bundit Laekhanukit
LATIN 2014: 11th Latin American Theoretical Informatics [link]
Last update: April 11, 2014

2013


22. Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization [abstractfull version@arXivsurveyposter by S.Kvideo@FOCS by S.K.]
with Monika Henzinger, Sebastian Krinninger
FOCS201354th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
SICOMP 2016 special issue: SIAM Journal on Computing (Special issue for selected papers from FOCS 2013) [wiki]
Covered at: Bar-Ilan 
Last update: September May 28, 2015

21. Independent Set, Induced Matching, and Pricing: Connections and Tight (Subexponential Time) Approximation Hardnesses [abstractfull version@arXivvideo@FOCS by P.C. and B.L.]
with Parinya Chalermsook, Bundit Laekhanukit
FOCS 2013: 54th Annual IEEE Symposium on Foundations of Computer Science [wiki,link]
Last update: August 13, 2013

20. Graph Products Revisited: Tight Approximation Hardness of Induced Matching, Poset Dimension and More [pdf@arXivslides]
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 [pdf@arXiv]
with Monika Henzinger, Sebastian Krinninger
ICALP 2013: 40th International Colloquium on Automata, Languages and Programming [wiki,link]
Last update: May 15, 2013

18. Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-Partite Graphs [pdf@arXivjournal version]
with Parinya Chalermsook, Shiva Kintali, Richard J. Lipton
CJTCS 2013: Chicago Journal of Theoretical Computer Science [link]
Last update: November 12, 2013

17. Simple FPTAS for the Subset-Sums Ratio Problem [pdf(preprint)pdf(Elsevier)]
IPL 2013: Information Processing Letters [wiki,link]
Last update: July 28, 2013

16. An Approximate Restatement of the Four Color Theorem [detailpdf(preprint)pdf(jgaa)blog by R.J.L + related]
with Atish Das Sarma, Amita Gajewar, Richard J. Lipton
JGAA 2013: Journal of Graph Algorithms and Applications [wiki,link]
Last update: June 29, 2013

2012


15. Interactive Regret Minimization [detailpdf@ACM(free)ppt]
Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Kazuhisa Makino
SIGMOD 2012: the ACM SIGMOD International Conference on Management of Data [wiki]
Author names are NOT in alphabetical order.
Last update: Mar 14, 2012

14. Dense Subgraphs on Dynamic Networks [pdf@arXivconference spoiler by A.T.]
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]
Covered at Umass
Last update: Jan 13, 2013

13. Polynomial-time Algorithms for Energy Games with Special Weight Structures [pdf@arxivslides]
with Krishnendu Chatterjee, Monika Henzinger, Sebastian Krinninger
ESA 2012: European Symposium on Algorithms [wiki]
Algorithmica 2014 special issue: Invited to Algorithmica (Special issue for selected papers from ESA 2012) [wikilink]
Last update: Nov 14, 2013

2011


12. Distributed Verification and Hardness of Distributed Approximation [detailpdf(arXiv), video@stoc11pptx(short)pptx(long)]
with Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Gopal Pandurangan, David Peleg, Roger Wattenhofer
STOC 2011: 43rd ACM Symposium on Theory of Computing [wiki]
SICOMP 2012 special issue: SIAM Journal on Computing (Special issue for selected papers from STOC 2011) [wikilink]
Additional links: pdf@ACM(free)pdf@sicomp
Note: SICOMP version = ArXiv v3 version + some grammatical errors fixed. 
Last update: Nov 25, 2014

11. A Tight Unconditional Lower Bound on Distributed Random Walk Computation [detailpdf (arXiv)pptx@ACM(free)]
Danupon Nanongkai, Atish Das Sarma, Gopal Pandurangan
PODC 2011: 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing [wiki]
Author names are NOT in alphabetical order.
Last update: Oct 15, 2011

10. Representative Skylines using Threshold-based Preference Distributions [detailpdf]
Atish Das Sarma, Ashwin Lall, Danupon Nanongkai, Richard J. Lipton, Jun Xu
ICDE 2011: the IEEE International Conference on Data Engineering [link]
Author names are NOT in alphabetical order.
Additional info: Selected as an excellent paper for 2011 by Cortes and Spector
Last update: November 25, 2014

2010


9. Regret-Minimizing Representative Databases [detailpdfpptx]
Danupon Nanongkai, Atish Das Sarma, Ashwin Lall, Richard J. Lipton, Jun Xu
Author names are NOT in alphabetical order.
VLDB 2010: 36th International Conference on Very Large Data Bases [wiki]

8. Efficient Distributed Random Walks with Applications [detailpdf (arXiv of journal version)pdf (arXiv - conf version), pdf@acm(free conf version)]
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 [wikilink] 
(Journal version combines PODC 2009 and PODC 2010 papers)
Covered at: ETHZ
Last update: Feb 19, 2013

7. Faster Algorithms for Semi-Matching Problems [detailpdf (arXiv)]
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 [detailpdf]
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 [detailpdfpptx]
with Atish Das Sarma, Ashwin Lall, Jun Xu
VLDB 2009: 35th International Conference on Very Large Data Bases [wiki]

4. Fast Distributed Random Walks [detailpdf (arXiv of journal version), pdf (conf version)pptxpdf@acm (free)]
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] 
(Journal version combines PODC 2009 and PODC 2010 papers) 
Last update: Feb 19, 2013 

3. Best-Order Streaming Model [detailpdf (preprint)blog by R.J.L.link to the journalppt]
with Atish Das Sarma, Richard J. Lipton
TAMC 2009: 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 selected papers from TAMC 2009) [wiki]
Covered at George Town

2. A Deterministic Nearly Linear-time Algorithm for Finding Minimum Cuts in Planar Graphs [detailpdfslides by J.F.]
with Jittat Fakcharoenphol, Parinya Chalermsook
SODA 2004 (short paper): 15th Annual ACM-SIAM Symposium on Discrete Algorithms 

1. Detecting and Cleaning Intruders in Sensor Networks [detailpdf]
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 [pdf@GaTech]
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


New Tools and Connections for Exponential-time Approximation [pdf@arXiv]
with Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Jesper Nederlof
Manuscript 2017

Interview as an ERC Grantee from Southeast Asia [link]
EURAXESS ASEAN Quarterly Newsletter, Issue No. 1, 2017

Geometric Pricing: How Low Dimensionality Helps in Approximability [pdf@arXiv]
with Parinya Chalermsook, Khaled Elbassioni, He Sun
Manuscript 2012

  

 


Comments