Data structures
- Cell probe lower bounds
- Low-Contention Data Structures by James Aspnes, David Eisenstat and Yitong Yin. SPAA 2010.
Comments: The lower bound proof is nice and entirely new to me, eps. the construction of the adversary by increasing the probabilities step by step. - Hardness Results for Dynamic Problems by Extensions of Fredman and Saks' Chronogram Method by Thore Husfeldt and Theis Rauhe. ICALP 1998.
- Lower bounds for predecessor searching in the cell probe model by Pranab Sen and S. Venkatesh. CCC 2003.
Comments: A nice paper to learn how to round elimination. - Worst-case and amortised optimality in union-find by Stephen Alstrup, Amir M. Ben-Amram and Theis Rauhe. STOC 1999.
Comments: An application of Ben-Amram and Galil's general framework. - A generalization of a lower bound technique due to Fredman and Saks by A. M. Ben-Amram and Z. Galil. Algorithmica 2001.
Comments: Proposed a general framework that can be applied to different problems and computational tools, by extending the chronogram method. A very nice paper to read, eps. for learning how to generalize good techniques. - Cell-Probe Lower Bounds for Succinct Partial Sums by Mihai Pătraşcu and Emanuele Viola. SODA 2010..
Comments: Similar techniques to ours are used: put cells into the cache. The pure information theoretic arguments are very cool. - A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match by Rina Panigrahy, Kunal Talwar, and Udi Wieder. FOCS 2008.
Comments: (1) I guess that there are connections between the lower bound construction + Sec. 4.3 and Mihai's "asking many queries at at time".
(2) The proof of Lemma "perturbations create many lenses" reminds me something like "trace the query paths", and I believe that it is one of the keys for understanding DS lower bounds. - Unifying the Landscape of Cell-Probe Lower Bounds by Mihai Pătraşcu. SICOMP/FOCS 2008.
Comments: Beautiful paper. The randomized LB for LSD is a good textbook proof on the use of information theory. - Lower Bounds for 2-Dimensional Range Counting by Mihai Pătraşcu. STOC 2007.
Comments: Magic use of entropy. - On Dynamic Bit-Probe Complexity by Mihai Pătraşcu and Corina Tarnită ICALP, 2005.
Comments: A polynomial lower bound for partial sum with fast updates is proved, by a clever adjustment of the classic chronogram method. - Cell Probe Complexity - a survey by P. B. Miltersen. 2000.
Comments: Very beautiful survey. A Must Read for anyone who wants to study cell probe complexity - Optimal bounds for the Predecessor Problem and Related Problem by Paul Beame and Faith E, Fich. JCSS 2002 also STOC 1999.
- Marked Ancestor Problem by S. Alstrup, T. Husfeldt and T. Rauhe. FOCS 1998.
Comments: A nice application of the chronogram method. - On the Cell Probe Complexity of Membership and Perfect Hashing by Rasmus Ragh. STOC 2001.
- The Cell Probe Complexity of Dynamic Data Structures by M. L. Fredman and M. E. Saks. STOC 1989.
Comments: The classical paper proposed the chronogram method. But it is very hard to read and one can refer to Miltersen's survey. - On data structures and asymmetric communication complexity by P. B. Miltersen, N. Nisan, S. Safra, A. Wigderson. JCSS 1998.
Comments: Two classical techniques are discussed the richness method and the round elimination. Very well written and definitely worth reading.
- Low-Contention Data Structures by James Aspnes, David Eisenstat and Yitong Yin. SPAA 2010.
- External and succinct DS lower bounds
- Dynamic optimality for skip lists and B-trees by Prosenjit Bose , Karim Douieb , Stefan Langerman. SODA, 2008.
Comments: In contrast with the long-standing dynamic optimality conjecture, where all DS are rotation-based, this paper introduced dynamic optimal data structures (Skip-List and B-Tree) among all split/merge-based DS. - Lower bounds for External Memory Dictionaries by G. S. Brodal and R. Fagerberg. SODA, 2003.
- Membership in Constant Time and Almost-Minimum Space by Andrej Brodnik, J. Ian Munro. SICOMP, 1999.
- The cell probe complexity of succinct data structures by A. Gál, P.B. Miltersen. TCS 2007 / ICALP 2003.
Comments: Techniques like the "sunflower" are very nice. One problem is mentioned: whether a solution with r(edundancy) = 0 and t = O(log u) exists for the Membership problem, and how about constant r.
- Dynamic optimality for skip lists and B-trees by Prosenjit Bose , Karim Douieb , Stefan Langerman. SODA, 2008.
- Lower bounds in other models
- On the Complexity of a Game Related to the Dictionary Problem by Kurt Mehlhorn Stefan Naher Monika Rauch. SICOMP 1990.
Comments: Easy but worth reading. - Lower bounds for Union-Split-Find related problems on random access machines by Peter Bro Miltersen. STOC 1994.
Comments: One problem is mentioned at the end of the paper: maintaining a set S under insertions, deletions and min queries. This problem is somewhat different from membership since we have to consider "deletions" carefully. - On a model of indexability and its bounds for range queries by Hellerstein, Joseph M. and Koutsoupias, Elias and Miranker, Daniel P. and Papadimitriou, Christos H. and Samoladas, Vasilis.
- Optimal biweighted binary trees and the complexity of maintaining partial sums by Haripriyan Hampapuram and Michael L. Fredman. SICOMP 1998.
- On the single-operation worst-case time complexity of the disjoint set union problem by Norbert Blum. SICOMP 1986.
- A lower bound for the dictionary problem under a hashing model by Rajamani Sundar. FOCS 1991.
Comments: Very complicated but beautiful inductions.
- On the Complexity of a Game Related to the Dictionary Problem by Kurt Mehlhorn Stefan Naher Monika Rauch. SICOMP 1990.
- Upper bounds
- De-amortized Cuckoo Hashing: Provable Worst Case Performance and Experimental Results by Yuriy Arbitman, Moni Naor and Gil Segev, ICALP 2009.
- On Dynamic Range Reporting in One Dimension by C. W. Mortensen, R. Ragh and M. Patrascu, STOC 2005.
Comments: The limit of "bit-tricks". - Dynamic Optimality--Almost by Demaine, E.D. and Harmon, D. and Iacono, J. and Patrascu, M. FOCS 2004.
Comments: The paper introduced an O(lglg n)-competitive BST, which is the currently best. The DS is built on Wilber's "interleave lower bound". Once the lower bound is thoroughly understood, the DS is straightforward. - Splay Trees, Davenport-Schinzel Sequences, and the Deque Conjecture by Seth Pettie. SODA 2008.
- Making data structures persistent by James R. Driscoll, Neil Sarnak. STOC 1986
- Self-adjusting binary search trees by Sleator, D.D. and Tarjan, R.E. JACM 1985.
- Approximate distance oracles by Mikkel Thorup and Uri Zwick. JACM 2004.
- Hash Functions for Priority Queues by M. Ajtai, M. Fredman, and J. Komlos. FOCS 1983.
- Related
- Better Gap-Hamming Lower Bounds via Better Round Elimination by Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, and Ronald de Wolf, RANDOM 2010.
Comments: A novel round elimination technique without reducing the universe is introduced for the Gap-Hamming problem.
Advanced data structure. By Erik Demaine, MIT, 2005 2007
- Better Gap-Hamming Lower Bounds via Better Round Elimination by Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, and Ronald de Wolf, RANDOM 2010.
Geometry
- Coresets for k-Means and k-Median Clustering and their Applications by Sariel Har-Peled and Soham Mazumdar STOC 2004.
- Approximating Extent Measure of Points by P.K. Agarwal and K. R. Varadarajan. JACM 2004.
- Geometric Approximation via Coresets by Pankaj K. Agarwal, Sariel Har-Peled and Kasturi R. Varadarajan. Survey 2005.
- A Space-Optimal Data-Stream Algorithm for Coresets in the Plane by Pankaj K. Agarwal, Hai Yu. SoCG 2007.
Metric embeddings
- Embeddings of Negative-type Metrics and An Improved Approximation to Generalized Sparsest Cut by N. Linial, E. London and Yu. Rabinovich. Combinatorica 2005.
- The geometry of graphs and some of its algorithmic applications by Chawla, Gupta, Racke. SODA 2005.
- Distance scales, embeddings, and metrics of negative type by James R. Lee. SODA 2005.
- Probabilistic Approximations of Metric Spaces and its Algorithmic Applications by Y. Bartal. FOCS 1996.
- Small distortion and volume preserving embeddings for Planar and Euclidean metrics by Satish Rao. SoCG 1999.
- Expander Flows, Geometric Embeddings, and Graph Partitionings by Arora, Rao, Vazirani. STOC 2004.
- Measured descent: A new embedding method for finite metrics by Krauthgamer, Lee, Mendel, Naor. FOCS 2004.
- Advances in metric embedding theory by Ittai Abraham and Yair Bartal and Ofer Neimany. STOC 2006.
- Euclidean distortion and the Sparsest Cut by Arora, Lee, Naor. STOC 2005.
- Approximating metrics by tree metrics by Jittat Fakcharoenphol and Satish Rao and Kunal Talwar. SIGACT News 2004.
- Approximating the bandwidth via volume respecting embeddings by U. Feige. STOC 1998.
- Buy-at-Bulk Network Design by B. Awerbuch and Y.Azar, FOCS 1997.
Here is a paper library I maintained on Metri Embedding.
Network design
- Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms by Tom Leighton and Satish Rao. JACM 1999.
- Minimizing Congestion in General Networks by Harald R?cke. FOCS 2002.
- Edge-Disjoint Paths in Planar Graphs with Constant Congestion by Chandra Chekuri, Sanjeev Khanna and Bruce Shepherd. STOC 2006.
- A Polynomial time Tree Decomposition to Minimize Congestion by Chris Harrelson, Kirsten Hildrum and Satish Rao. SPAA 2003.
- Multicommodity Demand Flow in a Tree and Packing Integer Programs by Chandra Chekuriy Marcelo Mydlarzz and F. Bruce Shepherd. ICALP 2003.
- Edge Disjoint Paths in Planar Graphs by Chandra Chekuriy Sanjeev Khanna and Bruce Shepherd. FOCS 2004.
Online
- Strongly Competitive Algorithms for Paging with Locality of Reference. by Sandy Irani, Anna R. Karlin, Steven Phillips. SODA 1992.
- A Primal-Dual Randomized Algorithm for Weighted Paging by Nikhil Bansal, Niv Buchbinder and Seffi Naor. FOCS 2007.
- Improved Bounds for Online Routing and Packing via a Primal-Dual Approach by Niv Buchbinder and Seffi Naor. FOCS 2006.
- Online Primal-Dual Algorithms for Covering and Packing Problems by Niv Buchbinder and Seffi Naor. ESA 2005.
Streaming
- Adaptive sampling for geometric problems over data streams by Hershberger, John and Suri, Subhash. PODS 2004.
- Algorithms for dynamic geometric problems over data streams by Piotr Indyk. STOC 2004.
- Graph distances in the streaming model: the value of space
by Feigenbaum, J. and Kannan, S. and McGregor, A. and Suri, S. and Zhang, J. SODA 2005. Talk in an Indian workshop
On graph problems in a semi-streaming model by Feigenbaum, J. and Kannan, S. and McGregor, A. and Suri, S. and Zhang, J. ICALP 2004. - Clustering data streams by Guha, S. and Mishra, N. and Motwani, R. and O¡¯Callaghan, L. FOCS 2000.
- The space complexity of approximating the frequency moments by Alon, N. and Matias, Y. and Szegedy, M. STOC 1996.
- Space-efficient online computation of quantile summaries by Greenwald, Michael and Khanna, Sanjeev. SIGMOD 2001.
- Data Streams: Algorithms and Applications (survey) by S. Muthukrishnan. TCS 2005.
Approximation
- Achieving anonymity via clustering by Aggarwal, Gagan and Feder, Tomas and Kenthapadi, Krishnaram and Khuller, Samir and Panigrahy, Rina and Thomas, Dilys and Zhu, An. PODS 2006
- Approximation schemes for covering and packing problems in image processing and VLSI by Dorit S. Hochbaum, Wolfgang Maass. JACM 1985.
- Incremental Clustering and Dynamic Information Retrieval Charikar, Moses and Chekuri, Chandra and Feder, Tomas and Motwani, Rajeev. STOC 1997.
- Divide-and-conquer approximation algorithms via spreading metrics by Even, Guy and Naor, Joseph Seffi and Rao, Satish and Schieber, Baruch. JACM 2000.
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming by Goemans, Michel X. and Williamson, David P. JACM 1995.
Sublinear Algorithms
- Constant-Time Approximation Algorithms via Local Improvements by Huy N. Nguyen, Krzysztof Onak, FOCS 2008.
- Sublinear time algorithms for metric space problems. by Piotr Indyk. STOC 1999.
- Property Testing and Its Connection to Learning and Approximation. by Oded Goldreich and Shafi Goldwasser and Dana Ron. JACM 1998.
Algorithmic Game Theory
- Revenue in Truly Combinatorial Auctions and Adversarial Mechanism Design by Micali, Silvio; Valiant, Paul
- Algorithms for Secretary Problems on Graphs and Hypergraphs by Nitish Korula, Martin Pal, ICALP 2009.
- A new approach to auctions and resilient mechanism design by Jing Chen, Silvio Micali, STOC 2009.
- On Profit-Maximizing Envy-free Pricing by Guruswami, Venkatesan and Hartline, Jason D. and Karlin, Anna R. and Kempe, David and Kenyon, Claire and McSherry, Frank. SODA 2005.
- Single-minded unlimited supply pricing on sparse instances by Patrick Briest and Piotr Krysta. SODA 2006.
I/O Algorithms
- I/O-Efficient Graph Algorithms by Norbert Zeh
- External-memory graph algorithms by Chiang, Y.J. and Goodrich, M.T. and Grove, E.F. and Tamassia, R. and Vengroff, D.E. and Vitter, J.S. SODA 1995
- Cache-oblivious priority queue and graph algorithm applications by Arge, L. and Bender, M.A. and Demaine, E.D. and Holland-Minkley, B. and Munro, J.I. SICOMP 2006
- Cache oblivious distribution sweeping by Brodal, G.S. and Fagerberg, R. ICALP 2002
- On two-dimensional indexability and optimal range search indexing by Arge, L. and Samoladas, V. and Vitter, J.S. PODS 1999
Others
- Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operationn by Monika Rauch Henzinger , Valerie King, JACM 1999
- Inapproximability of Combinatorial Optimization Problems (Survey) by Luca Trevisan.
- Sampling Lattice Points by Ravi Kannan and Santosh Vempala. STOC 1997.
- An optimal minimum spanning tree algorithm by Seth Pettie and Vijaya Ramachandran. JACM 2002.
- How Much Can Hardware Help Routing? by Allan Borodin and Prabhakar Raghavan and Baruch Scheiber and Eli Upfal. JACM 1997.
- The Unified Theory of Pseudorandomness. by Salil Vadhan. SIGACT News Sep. 2007.
- Some NP-complete geometric problems. by Garey, MR and Graham, RL and Johnson, DS. STOC 1976.
- Parallel monotonicity reconstruction by Michael Saks and C. Seshadhri, SODA 2008
- Conflict-Free colorings of Shallow Discs by Noga Alon. Shakhar Smorodinsky, SOCG 2006
- Topology control and routing in Ad hoc networks: a survey by R. Rajaraman. ACM SIGACT News 2002
- The string edit distance matching problem with moves by G. Cormode and S. Muthukrishnan. ACM SIGACT News 2002
- On Developing New Models, with Paging as a Case Study. by Reza Dorrigiv and Alejandro Lopez-Ortiz. ACM SIGACT News 2009
Lecture Notes
- Advanced data structure. By Erik Demaine, MIT, 2005 2007
- Graph Theory. By Therese Biedl, Waterloo, 2005
- Approximation Algorithm. By Shuchi, 2007
- Advanced Topics in Computer Science: A Theorist's Toolkit. By Sanjeev Arora, Princeton, 2002
- An Elementary Introduction to Modern Convex Geometry. By Keith Ball, Draft
- Semidefinite programs and combinatorial optimization. By L Lovász. Draft
- The Probabilistic Method. By Jiri Matousek and Jan Vondrak. Draft
- Solving geometric optimization problems using parametric search. By Michiel Smid. Draft
Books/Chapters
Open Problems
- LBs for randomized distributed streaming
- Depict the complete curve for dynamic external membership (fast updates)
- External priority queue
- Path clearance
- CO optimality