### 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).

## 2013

22. Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization ]
with Monika Henzinger, Sebastian Krinninger
FOCS201354th Annual IEEE Symposium on Foundations of Computer Science []
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 ]
with Parinya Chalermsook, Bundit Laekhanukit
FOCS 2013: 54th Annual IEEE Symposium on Foundations of Computer Science []
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
with Monika Henzinger, Sebastian Krinninger
ICALP 2013: 40th International Colloquium on Automata, Languages and Programming []
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 ]
IPL 2013: Information Processing Letters [wiki,link]
Last update: July 28, 2013

16. An Approximate Restatement of the Four Color Theorem [detailpdf(preprint)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) []
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) []
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. Efﬁcient 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