Data structures

1. 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.
   
   


2. 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.
   
   


3. 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.
   
   
4. 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.
   
   
5. 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

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

• Computational Complexity: A Modern Approach. By Sanjeev Arora and Boaz Barak, Cambridge University Press, Draft


• Algorithmic Game Theory. Edited by Noam Nisan, Tim Roughgarden, Eva Tardos, Vijay V. Vazirani, Draft


• Cut problems and their application to divide-and-conquer. By David B. Shmoy, Draft

Open Problems

• LBs for randomized distributed streaming
• Depict the complete curve for dynamic external membership (fast updates)
• External priority queue
• Path clearance
• CO optimality

Link to the old version, self study