Qin Zhang's Reading Library

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.

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

Contact