# Bibliography

Revision as of 19:29, 20 October 2012 by Krzysztof Onak (talk | contribs)

**Citations:** Write `{{cite|`*paper_id_1*`|`*paper_id_2*`|`…`|`*paper_id_k*`}}` to cite papers *paper_id_1*, *paper_id_2*, …, *paper_id_k*. For instance, `{{cite|AlonMS-99|BlumLR-93}}` results in [AlonMS-99,BlumLR-93].

- [AlonMS-99]
- Noga Alon, Yossi Matias, Mario Szegedy.
*The Space Complexity of Approximating the Frequency Moments.*J. Comput. Syst. Sci. 58(1), pages 137-147, 1999.

- [AndoniIK-09]
- Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer.
*Overcoming the $\ell_1$ non-embeddability barrier: algorithms for product metrics.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 865-874, 2009.

- [AndoniJP-10]
- Alexandr Andoni, T. S. Jayram, and Mihai Patrascu.
*Lower bounds for edit distance and product metrics via Poincaré-type inequalities.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 184-192, 2010.

- [AndoniN-12]
- Alexandr Andoni, Huy L. Nguyen.
*Width of points in the streaming model.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 447-452, 2012.

- [AndoniO-09]
- Alexandr Andoni and Krzysztof Onak.
*Approximating edit distance in near-linear time.*In*ACM Symposium on Theory of Computing*, pages 199-204, 2009.

- [BarYossefJKST-02]
- Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan.
*Counting distinct elements in a data stream.*In*Proc. 6th International Workshop on Randomization and Approximation Techniques in Computer Science*, pages 1-10, 2002.

- [BarYossefKS-02]
- Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar.
*Reductions in streaming algorithms, with an application to counting triangles in graphs.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 623-632, 2002.

- [Baswana-06]
- Surender Baswana.
*Faster streaming algorithms for graph spanners.*2006.

- [BerindeIR-08]
- Radu Berinde, Piotr Indyk, and Milan Ruzic.
*Practical near-optimal sparse recovery in the $l_1$ norm.*Allerton, 2008.

- [BhattacharyyaMMY-07]
- S. Bhattacharyya, A. Madeira, S. Muthukrishnan, and T. Ye.
*How to scalably skip past streams.*In*WSSP (Workshop with ICDE)*, 2007.

- [BhuvanagiriG-06]
- Lakshminath Bhuvanagiri and Sumit Ganguly.
*Estimating entropy over data streams.*In*ESA*, pages 148--159, 2006.

- [BhuvanagiriGKS-06]
- Lakshminath Bhuvanagiri, Sumit Ganguly, Deepanjan Kesh, and Chandan Saha.
*Simpler algorithm for estimating frequency moments of data streams.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 708-713, 2006.

- [BlumLR-93]
- Manuel Blum, Michael Luby, Ronitt Rubinfeld.
*Self-Testing/Correcting with Applications to Numerical Problems.*J. Comput. Syst. Sci. 47(3), pages 549-595, 1993.

- [BroderCFM-00]
- Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher.
*Min-wise independent permutations.**J. Comput. Syst. Sci.*, 60(3), pages 630-659, 2000.

- [BuriolFLMS-06]
- Luciana S. Buriol, Gereon Frahling, Stefano Leonardi, Alberto Marchetti-Spaccamela, and Christian Sohler.
*Counting triangles in data streams.*In*ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems*, pages 253-262, 2006.

- [CandesRT-06]
- Emmanuel J. Candès, Justin K. Romberg, and Terence Tao.
*Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information.*IEEE Transactions on Information Theory, 52(1):489-509, 2006.

- [ChakrabartiCM-07]
- Amit Chakrabarti, Graham Cormode, and Andrew McGregor.
*A near-optimal algorithm for computing the entropy of a stream.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 328-335, 2007.

- [Charikar-02]
- Moses Charikar.
*Similarity estimation techniques from rounding algorithms.*In*STOC*, pages 380-388, 2002.

- [CormodeDIM-03]
- Graham Cormode, Mayur Datar, Piotr Indyk, and S. Muthukrishnan.
*Comparing data streams using hamming norms (how to zero in).**IEEE Trans. Knowl. Data Eng.*, 15(3), pages 529-540, 2003.

- [CormodeKMS-06]
- Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava.
*Space- and time-efficient deterministic algorithms for biased quantiles over data streams.*In*PODS*, pages 263-272, 2006.

- [CormodeM-05]
- Graham Cormode and S. Muthukrishnan.
*An improved data stream summary: the count-min sketch and its applications.**J. Algorithms*, 55(1), pages 58-75, 2005.

- [CormodeM-05a]
- Graham Cormode and S. Muthukrishnan.
*What's new: finding significant differences in network data streams.**IEEE/ACM Trans. Netw.*, 13(6), pages 1219-1232, 2005.

- [CormodeM-05b]
- Graham Cormode and S. Muthukrishnan.
*Space efficient mining of multigraph streams.*In*ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems*, pages 271-282, 2005.

- [CormodeM-06]
- Graham Cormode and S. Muthukrishnan.
*Combinatorial algorithms for compressed sensing.*In Paola Flocchini and Leszek Gasieniec, editors,*Structural Information and Communication Complexity, 13th International Colloquium, SIROCCO 2006, Chester, UK, July 2-5, 2006, Proceedings*, volume 4056 of*Lecture Notes in Computer Science*, pages 280-294. Springer, 2006.

- [DasSarmaGP-08]
- Atish Das Sarma, Sreenivas Gollapudi, and Rina Panigrahy.
*Estimating PageRank on graph streams.*In*PODS*, pages 69-78, 2008.

- [DeanG-04]
- Jeffrey Dean and Sanjay Ghemawat.
*MapReduce: Simplified data processing on large clusters.*In*OSDI*, pages 137-150, 2004.

- [DemaineLM-02]
- Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro.
*Frequency estimation of internet packet streams with limited space.*In*ESA*, pages 348-360, 2002.

- [DemetrescuFR-06]
- Camil Demetrescu, Irene Finocchi, and Andrea Ribichini.
*Trading off space for passes in graph streaming problems.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 714-723, 2006.

- [Donoho-06]
- David L. Donoho.
*Compressed sensing.*IEEE Transactions on Information Theory, 52(4):1289-1306, 2006.

- [DrakeH-03]
- Doratha E. Drake and Stefan Hougardy.
*Improved linear time approximation algorithms for weighted matchings.*In*RANDOM-APPROX*, pages 14-23, 2003.

- [DrineasMM-06]
- Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan.
*Sampling algorithms for $\ell_2$ regression and applications.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 1127-1136, 2006.

- [DrineasMM-06a]
- Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan.
*Subspace sampling and relative-error matrix approximation: Column-based methods.*In*APPROX-RANDOM*, pages 316-326, 2006.

- [DrineasMM-06b]
- Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan.
*Subspace sampling and relative-error matrix approximation: Column-row-based methods.*In*ESA*, pages 304-314, 2006.

- [Edmonds-65]
- Jack Edmonds.
*Maximum matching and a polyhedron with 0,1-vertices.*J. Res. Nat. Bur. Standards, 69(B):125-130, 1965.

- [Elkin-06]
- Michael Elkin.
*A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners.*2006.

- [ElkinZ-06]
- Michael Elkin and Jian Zhang.
*Efficient algorithms for constructing $(1+\epsilon, \beta)$-spanners in the distributed and streaming models.*Distributed Computing, 18(5):375-385, 2006.

- [FeigenbaumKMSZ-05]
- Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.
*Graph distances in the streaming model: the value of space.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 745-754, 2005.

- [FeigenbaumKMSZ-05a]
- Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.
*On graph problems in a semi-streaming model.*Theoretical Computer Science, 348(2-3):207-216, 2005.

- [FeigenbaumKMSZ-08]
- Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang.
*Graph distances in the data-stream model.*SIAM J. Comput., 38(5):1709-1727, 2008.

- [FeigenbaumKSV-02]
- Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan.
*An approximate $L^1$ difference algorithm for massive data streams.**Journal on Computing*, 32(1), pages 131-151, 2002.

- [FeldmanMSSS-06]
- Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, and Zoya Svitkina.
*On the complexity of processing massive, unordered, distributed data.*2006.

- [FeldmanMSSS-10]
- Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Clifford Stein, and Zoya Svitkina.
*On distributing symmetric streaming computations.*ACM Transactions on Algorithms, 6(4), 2010.

- [GabizonH-10]
- Ariel Gabizon and Avinatan Hassidim.
*Derandomizing algorithms on product distributions and other applications of order-based extraction.*In*ICS*, pages 397-405, 2010.

- [Gabow-90]
- Harold N. Gabow.
*Data structures for weighted matching and nearest common ancestors with linking.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 434-443, 1990.

- [Ganguly-06]
- Sumit Ganguly and Anirban Majumder.
*CR-precis: A deterministic summary structure for update data streams.*In*ESCAPE*, 2007.

- [GilbertKMS-02]
- Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, and Martin Strauss.
*How to summarize the universe: Dynamic maintenance of quantiles.*In*Proc. 28th International Conference on Very Large Data Bases*, pages 454-465, 2002.

- [GilbertSTV-07]
- A. C. Gilbert, M. J. Strauss, J. A. Tropp, and R. Vershynin.
*One sketch for all: fast algorithms for compressed sensing.*ACM Symposium on Theory of Computing, 2007.

- [GolubV-89]
- G.H. Golub and C.F. Van Loan.
*Matrix Computations.*Johns Hopkins University Press, Baltimore, 1989.

- [GoreinovT-01]
- S. A. Goreinov and E. E. Tyrtyshnikov.
*The maximum-volume concept in approximation by low-rank matrices.*Contemporary Mathematics, 280, pages 47-51, 2001.

- [GoreinovTZ-97]
- S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin.
*A theory of pseudoskeleton approximations.*Linear Algebra and its Applications, 261, pages 1-21, August 1997.

- [Gould-96]
- Stephen Jay Gould.
*The Mismeasure of Man.*W. W. Norton and Company, 1996.

- [GreenwaldK-01]
- Michael Greenwald and Sanjeev Khanna.
*Space-efficient online computation of quantile*

summaries.* In *ACM SIGMOD International Conference on Management of Data*, pages 58-66, 2001.*

- [GroheGLSTV-07]
- Martin Grohe, Yuri Gurevich, Dirk Leinders, Nicole Schweikardt, Jerzy Tyszkiewicz, and Jan Van den Bussche.
*Database query processing using finite cursor machines.*In*ICDT*, pages 284-298, 2007.

- [GuE-96]
- M. Gu and S.C. Eisenstat.
*Efficient algorithms for computing a strong rank-revealing QR factorization.*SIAM Journal on Scientific Computing, 17, pages 848-869, 1996.

- [GuhaIM-07]
- Sudipto Guha, Piotr Indyk, and Andrew McGregor.
*Sketching information divergences.*In*Conference on Learning Theory*, 2007.

- [GuhaM-06]
- Sudipto Guha and Andrew McGregor.
*Approximate quantiles and the order of the stream.*In*ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems*, pages 273-279, 2006.

- [GuhaM-07]
- Sudipto Guha and Andrew McGregor.
*Lower bounds for quantile estimation in random-order and multi-pass streaming.*Manuscript, 2007.

- [GuhaM-07a]
- Sudipto Guha and Andrew McGregor.
*Space-efficient sampling.*In*AISTATS*, pages 169-176, 2007.

- [GuhaMV-06]
- Sudipto Guha, Andrew McGregor, and Suresh Venkatasubramanian.
*Streaming and sublinear approximation of entropy and information distances.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 733-742, 2006.

- [HershbergerSST-04]
- John Hershberger, Nisheeth Shrivastava, Subhash Suri, and Csaba D. Tóth.
*Adaptive spatial partitioning for multidimensional data streams.*In*ISAAC*, pages 522-533, 2004.

- [HoffmannMR-04]
- M. Hoffmann, S. Muthukrishnan, and R. Raman.
*Location streams: Models and algorithms.*Technical Report 2004-28, DIMACS, May 2004.

- [HopcroftK-73]
- John E. Hopcroft and Richard M. Karp.
*An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs.*SIAM J. Comput., 2(4):225-231, 1973.

- [Indyk-00]
- Piotr Indyk.
*Stable distributions, pseudorandom generators, embeddings and data stream computation.*In*IEEE Symposium on Foundations of Computer Science*, pages 189-197, 2000.

- [Indyk-04]
- Piotr Indyk.
*Algorithms for dynamic geometric problems over data streams.*In*ACM Symposium on Theory of Computing*, pages 373-380, 2004.

- [IndykR-08]
- Piotr Indyk and Milan Ruzic.
*Near-optimal sparse recovery in the $\ell_1$ norm.*In*IEEE Symposium on Foundations of Computer Science*, pages 199-207, 2008.

- [IndykT-03]
- Piotr Indyk and Niten Thaper.
*Fast color image retrieval via embeddings.*Workshop on Statistical and Computational Theories of Vision (at ICCV), 2003.

- [IndykW-03]
- Piotr Indyk and David P. Woodruff.
*Tight lower bounds for the distinct elements problem.*In*IEEE Symposium on Foundations of Computer Science*, pages 283-288, 2003.

- [IndykW-05]
- Piotr Indyk and David P. Woodruff.
*Optimal approximations of the frequency moments of data streams.*In*ACM Symposium on Theory of Computing*, pages 202-208, 2005.

- [JayramKS-07]
- T. S. Jayram, Ravi Kumar, and D. Sivakumar.
*Simple lower bound on one-way Gap-Hamming.*In http://www.cse.iitk.ac.in/users/sganguly/slides/ravikumar.pdf, 2007.

- [JayramW-09]
- T. S. Jayram and David P. Woodruff.
*The data stream space complexity of cascaded norms.*In*IEEE Symposium on Foundations of Computer Science*, 2009.

- [JowhariG-05]
- Hossein Jowhari and Mohammad Ghodsi.
*New streaming algorithms for counting triangles in graphs.*In*COCOON*, pages 710-716, 2005.

- [KalantariS-95]
- Bahman Kalantari and Ali Shokoufandeh.
*Approximation schemes for maximum cardinality matching.*Technical Report LCSR-TR-248, Laboratory for Computer Science Research, Department of Computer Science. Rutgers University, August 1995.

- [KarloffSV-10]
- Howard J. Karloff, Siddharth Suri, and Sergei Vassilvitskii.
*A model of computation for MapReduce.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 938-948, 2010.

- [KuroseR-04]
- James F. Kurose and Keith W. Ross.
*Computer Networking: A Top-Down Approach Featuring the Internet.*Addison Wesley, 2004.

- [Li-06]
- Ping Li.
*Very sparse stable random projections, estimators and tail bounds for stable random projections.*

- [LiHC-06]
- Ping Li, Trevor Hastie, and Kenneth Ward Church.
*Very sparse random projections.*In*KDD*, pages 287-296, 2006.

- [MahoneyMD-06]
- Michael W. Mahoney, Mauro Maggioni, and Petros Drineas.
*Tensor-cur decompositions for tensor-based data.*In*ACM SIGKDD international conference on knowledge discovery and data mining*, pages 327-336, 2006.

- [MankuRL-98]
- Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay.
*Approximate medians and other quantiles in one pass and with limited memory.*In*ACM SIGMOD International Conference on Management of Data*, pages 426-435, 1998.

- [MankuRL-99]
- Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay.
*Random sampling techniques for space efficient online computation of order statistics of large datasets.*In*ACM SIGMOD International Conference on Management of Data*, pages 251-262, 1999.

- [Matousek-02]
- Jiří Matoušek.
*Lectures on Discrete Geometry*. Springer, 2002.

- [McGregor-05]
- Andrew McGregor.
*Finding graph matchings in data streams.*In*APPROX-RANDOM*, pages 170-181, 2005.

- [MetwallyAA-05]
- Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi.
*Efficient computation of frequent and top-k elements in data streams.*In*ICDT*, pages 398-412, 2005.

- [MicaliV-80]
- Silvio Micali and Vijay V. Vazirani.
*An ${O}(\sqrt{V}{E})$ algorithm for finding maximum matching in general graphs.*In*FOCS*, pages 17-27, 1980.

- [MisraG-82]
- Jayadev Misra and David Gries.
*Finding repeated elements.**Sci. Comput. Program.*, 2(2), pages143--152, 1982.

- [MitzenmacherV-08]
- Michael Mitzenmacher and Salil P. Vadhan.
*Why simple hash functions work: exploiting the entropy in a data stream.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 746-755, 2008.

- [MunroP-80]
- J. Ian Munro and Mike Paterson.
*Selection and sorting with limited storage.*Theor. Comput. Sci., 12:315-323, 1980.

- [Muthukrishnan-06]
- S. Muthukrishnan.
*Data streams: Algorithms and applications.*Now Publishers, 2006.

- [Muthukrishnan-06a]
- S. Muthukrishnan.
*Some algorithmic problems and results in compressed sensing.*In*Allerton Conference*, 2006.

- [NaorS-06]
- Assaf Naor and Gideon Schechtman.
*Planar earthmover is not in $l_1$.*In*FOCS*, pages 655-666, 2006.

- [NeedellT-10]
- Deanna Needell and Joel A. Tropp.
*Cosamp: iterative signal recovery from incomplete and inaccurate samples.*Commun. ACM, 53(12):93-100, 2010.

- [PettieS-04]
- Seth Pettie and Peter Sanders.
*A simpler linear time $2/3-\epsilon$ approximation for maximum weight matching.*Inf. Process. Lett., 91(6):271-276, 2004.

- [RudelsonV-06]
- Mark Rudelson and Roman Vershynin.
*Sparse reconstruction by convex relaxation: Fourier and gaussian measurements.*In*Proceedins of 40th Annual Conference on Information Sciences and Systems*, 2006.

- [ShrivastavaBAS-04]
- Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal, and Subhash Suri.
*Medians and beyond: new aggregation techniques for sensor networks.*In*SenSys*, pages 239--249, 2004.

- [Stewart-99]
- G.W. Stewart.
*Four algorithms for the efficient computation of truncated QR approximations to a sparse matrix.*Numerische Mathematik, 83, pages 313-323, 1999.

- [Stewart-04]
- G.W. Stewart.
*Error analysis of the quasi-Gram-Schmidt algorithm.*Technical Report UMIACS TR-2004-17 CMSC TR-4572, University of Maryland, College Park, MD, 2004.

- [Woodruff-04]
- David P. Woodruff.
*Optimal space lower bounds for all frequency moments.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 167-175, 2004.