# Bibliography

From Open Problems in Sublinear Algorithms

Revision as of 19:15, 7 November 2018 by Gautam Kamath (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].

- [AaronsonW-09]
- Scott Aaronson and Avi Wigderson.
*Algebrization: A New Barrier in Complexity Theory.*ACM Transactions on Computation Theory, 1(1), 2009.

- [AcharyaCK-14]
- Jayadev Acharya, Clément Canonne, and Gautam Kamath.
*A Chasm Between Identity and Equivalence Testing with Conditional Queries.*In*CoRR,*abs/1411.7346, 2014.

- [AcharyaDOS-17]
- Jayadev Acharya, Hirakendu Das, Alon Orlitsky, and Ananda Theertha Suresh.
*Estimating Symmetric Properties of Distributions: A Maximum Likelihood Approach .*In*ICML*, 2017.

- [AcharyaOST-17]
- Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi.
*Estimating Renyi Entropy of Discrete Distributions.*In IEEE Transactions on Information Theory, vol. 63, no. 1, pages 38-56, 2017.

- [AhnG-09]
- Kook Jin Ahn and Sudipto Guha.
*Graph sparsification in the semi-streaming model.*In*International Colloquium on Automata, Languages and Programming*, pages 328-338, 2009.

- [AhnG-11]
- Kook Jin Ahn and Sudipto Guha.
*Laminar Families and Metric Embeddings: Non-bipartite Maximum Matching Problem in the Semi-Streaming Model.*In*CoRR,*abs/1104.4058, 2011.

- [AhnGM-12]
- Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.
*Analyzing graph structure via linear measurements.*In*SODA*, pages 459-467, 2012.

- [AhnGM-12b]
- Kook Jin Ahn, Sudipto Guha, and Andrew McGregor.
*Graph sketches: sparsification, spanners, and subgraphs.*In*PODS*, pages 5-14, 2012.

- [AilonL-11]
- Nir Ailon and Edo Liberty.
*An almost optimal unrestricted fast Johnson-Lindenstrauss transform.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 185-191, 2011.

- [Alon-02]
- Noga Alon.
*Testing subgraphs in large graphs.*Random Struct. Algorithms, 21(3-4):359-370, 2002.

- [AlonFNS-09]
- Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira.
*A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity.*SIAM J. Comput. 39(1):143-167, 2009.

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

- [AndoniCKQWZ-16]
- Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, and Qin Zhang.
*On Sketching Quadratic Forms.*In*ITCS*, pages 311-319, 2016.

- [AndoniDIW-09]
- Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David P. Woodruff.
*Efficient sketches for earth-mover distance, with applications.*In*IEEE Symposium on Foundations of Computer Science*, pages 324-330, 2009.

- [AndoniGK-14]
- Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer.
*Towards $(1+\varepsilon)$-Approximate Flow Sparsifiers.*In*SODA*, pages 279-293, 2014.

- [AndoniIK-08]
- Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer.
*Earth mover distance over high-dimensional spaces.*In*SODA*, pages 343-352, 2008.

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

- [AndoniKR-14]
- Alexandr Andoni, Robert Krauthgamer, and Ilya Razenshteyn.
*Sketching and Embedding are Equivalent for Norms.*In*CoRR,*abs/1411.2577, 2014.

- [AndoniN-12]
- Alexandr Andoni and 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.

- [AssadiKLY-16]
- Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev.
*Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model.*In*SODA*, pages 1345-1364, 2016.

- [AssadiKL-17]
- Sepehr Assadi, Sanjeev Khanna, and Yang Li.
*On Estimating Maximum Matching Size in Graph Streams.*In*SODA*, pages 1723-1742, 2017.

- [BahBC-14]
- Bubaccar Bah, Luca Baldassarre, and Volkan Cevher.
*Model-based Sketching and Recovery with Expanders.*In*ACM-SIAM Symposium on Discrete Algorithms*, 2014.

- [BaraniukCDH-10]
- Richard G. Baraniuk, Volkan Cevher, Marco F. Duarte, and Chinmay Hegde.
*Model-based compressive sensing.*IEEE Transactions on Information Theory, 56(4):1982-2001, 2010.

- [BarYossefJKS-04]
- Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar.
*An information statistics approach to data stream and communication complexity.*J. Comput. Syst. Sci., 68(4):702-732, 2004.

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

- [BatsonSS-14]
- Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava.
*Twice-Ramanujan Sparsifiers.*SIAM Review 56(2):315-334, 2014.

- [BatuFFKRW-01]
- Tugkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White.
*Testing random variables for independence and identity.*In*FOCS*, pages 442-451, 2001.

- [BenczurK-96]
- András A. Benczúr and David R. Karger.
*Approximating $s{-}t$ minimum cuts in $\tilde O(n^2)$ time.*In*ACM Symposium on Theory of Computing*, pages 47-55, 1996.

- [BenderR-02]
- Michael A. Bender and Dana Ron.
*Testing properties of directed graphs: acyclicity and connectivity.*Random Struct. Algorithms, 20(2):184-205, 2002.

- [BenjaminiSS-08]
- Itai Benjamini, Oded Schramm, and Asaf Shapira.
*Every minor-closed property of sparse graphs is testable.*In*ACM Symposium on Theory of Computing*, pages 393-402, 2008.

- [BenSassonGMSS-11]
- Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, and Madhu Sudan.
*On sums of locally testable affine invariant properties.*Electronic Colloquium on Computational Complexity (ECCC), 18:79, 2011.

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

- [BermanRY-14]
- Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev.
*$L_p$-Testing.*In*ACM Symposium on Theory of Computing*, pages 164-173, 2014.

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

- [BlaisCG-17]
- Eric Blais, Clément L. Canonne, and Tom Gur.
*Distribution Testing Lower Bounds via Reductions from Communication Complexity*. In*CCC*, 2017.

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

- [BogdanovOT-02]
- Andrej Bogdanov, Kenji Obata, and Luca Trevisan.
*A lower bound for testing 3-colorability in bounded-degree graphs.*In*FOCS*, pages 93-102, 2002.

- [BonisGV-05]
- Annalisa De Bonis, Leszek Gasieniec, and Ugo Vaccaro.
*Optimal two-stage algorithms for group testing problems.*SIAM J. Comput., 34(5):1253-1270, 2005.

- [BoulandCHTV-16]
- Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan.
*On SZK and PP.*CoRR abs/1609.02888, 2016.

- [BravermanGPW-13]
- Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein.
*Information lower bounds via self-reducibility.*In*CSR*, 2013.

- [BravermanO-10]
- Vladimir Braverman and Rafail Ostrovsky.
*Zero-one frequency laws.*In*ACM Symposium on Theory of Computing*, pages 281-290, 2010.

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

- [BrodyC-09]
- Joshua Brody and Amit Chakrabarti.
*A multi-round communication lower bound for Gap Hamming and some consequences.*In*IEEE Conference on Computational Complexity*, pages 358-368, 2009.

- [BrodyCRVW-10]
- Joshua Brody, Amit Chakrabarti, Oded Regev, Thomas Vidick, and Ronald de Wolf.
*Better Gap-Hamming lower bounds via better round elimination.*In*APPROX-RANDOM*, pages 476-489, 2010.

- [BrodyJSW-14]
- Joshua Brody, Sune K. Jakobsen, Dominik Scheder, and Peter Winkler.
*Cryptogenography.*In*ITCS*, pages 13-22, 2014.

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

- [CandesRT-06a]
- Emmanuel J. Candès, Justin Romberg, and Terence Tao.
*Stable signal recovery from incomplete and inaccurate measurements.*Comm. Pure Appl. Math., 59(8):1208-1223, 2006.

- [Canonne-15]
- Clément L. Canonne.
*Big Data on the rise? Testing monotonicity of distributions.*In*ICALP*, 2015.

- [CanonneGR-16]
- Clément L. Canonne, Themis Gouleakis, and Ronitt Rubinfeld.
*Sampling Correctors.*In*ITCS*, 2016.

- [CanonneRS-14]
- Clément L. Canonne, Dana Ron, and Rocco A. Servedio.
*Testing equivalence between distributions using conditional samples.*In*SODA*, pages 1174-1192, 2014.

- [CarlsonKST-17]
- Charles Carlson, Alexandra Kolla, Nikhil Srivastava, and Luca Trevisan.
*Optimal Lower Bounds for Sketching Graph Cuts.*In*CoRR,*abs/1712.10261, 2017.

- [Chakrabarti-10]
- Amit Chakrabarti.
*A note on randomized streaming space bounds for the longest increasing subsequence problem.*Electronic Colloquium on Computational Complexity (ECCC), 10(10), 2010.

- [ChakrabartiCKM-10]
- Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, and Andrew McGregor.
*Information cost tradeoffs for augmented index and streaming language recognition.*In*IEEE Symposium on Foundations of Computer Science*, pages 387-396, 2010.

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

- [ChakrabartiCM-09]
- Amit Chakrabarti, Graham Cormode, and Andrew McGregor.
*Annotations in data streams.*In*International Colloquium on Automata, Languages and Programming*, pages 222-234, 2009.

- [ChakrabartiCMTV-15]
- Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian.
*Verifiable Stream Computation and Arthur-Merlin Communication.*In*IEEE Conference on Computational Complexity*, pages 217-243, 2015.

- [ChakrabartiK-14]
- Amit Chakrabarti and Sagar Kale.
*Submodular Maximization Meets Streaming: Matchings, Matroids, and More.*In*IPCO*, to appear, 2014.

- [ChakrabartiR-11]
- Amit Chakrabarti and Oded Regev.
*An optimal lower bound on the communication complexity of Gap-Hamming-Distance.*In*ACM Symposium on Theory of Computing*, pages 51-60, 2011.

- [ChakrabartiSWY-01]
- Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew C. Yao.
*Informational complexity and the direct sum problem for simultaneous message complexity.*In*IEEE Symposium on Foundations of Computer Science*, pages 270-278, 2001.

- [ChakrabartyS-13]
- Deeparnab Chakrabarty and C. Seshadhri.
*Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids.*In*ACM Symposium on Theory of Computing*, 2013.

- [ChakrabortyFGM-13]
- Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah.
*On the power of conditional samples in distribution testing.*In*ITCS*, pages 561-580, 2013.

- [ChanC-07]
- Timothy M. Chan and Eric Y. Chen.
*Multi-pass geometric algorithms.*Discrete & Computational Geometry, 37(1):79-102, 2007.

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

- [ChazelleRT-05]
- Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan.
*Approximating the Minimum Spanning Tree Weight in Sublinear Time.*SIAM J. Comput. 34(6):1370-1379, 2005.

- [ChienRS-03]
- Steve Chien, Lars Eilstrup Rasmussen, and Alistair Sinclair.
*Clifford algebras and approximating the permanent.*J. Comput. Syst. Sci. 67(2), 2003.

- [ChiesaG-17]
- Alessandro Chiesa and Tom Gur.
*Proofs of Proximity for Distribution Testing.*Electronic Colloquium on Computational Complexity (ECCC) 24:155, 2017.

- [ChitnisCEHMMV-16]
- Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova.
*Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams.*In*SODA*, pages 1326-1344, 2016.

- [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):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):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):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.

- [CormodePSV-00]
- Graham Cormode, Mike Paterson, Suleyman Cenk Sahinalp, and Uzi Vishkin.
*Communication complexity of document exchange.*In*SODA*, 2000.

- [CrouchM-11]
- Michael S. Crouch and Andrew McGregor.
*Periodicity and Cyclic Shifts via Linear Sketches.*In*APPROX*, 2011.

- [CrouchS-14]
- Michael Crouch and Daniel Stubbs. In Andrew McGregor's presentation at the 2014 Bertinoro Workshop on Sublinear Algorithms.

- [CzumajS-09]
- Artur Czumaj and Christian Sohler.
*Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time.*In*SIAM J. Comput.*, 39(3):904–922, 2009.

- [DaskalakisDS-11]
- Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio.
*Learning transformed product distributions.*CoRR, abs/1103.0598, 2011.

- [DaskalakisKW-18]
- Constantinos Daskalakis, Gautam Kamath, and John Wright.
*Which Distribution Distances are Sublinearly Testable?*In*SODA*, 2018.

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

- [DodisGLRRS-99]
- Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, and Alex Samorodnitsky.
*Improved testing algorithms for monotonicity.*In*RANDOM-APPROX*, pages 97-108, 1999.

- [DoerrK-16]
- Benjamin Doerr, Marvin Kunnemann.
*Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem.*In*ICALP*, 2016.

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

- [Eddy-04]
- Sean R Eddy.
*How do RNA folding algorithms work?*Nature Biotechnology, 22, pages 1457-1458, 2004.

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

- [EpsteinLMS-11]
- Leah Epstein, Asaf Levin, Julian Mestre, and Danny Segev.
*Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model.*SIAM J. Discrete Math. 25(3), 2011.

- [ErgunJ-08]
- Funda Ergün and Hossein Jowhari.
*On distance to monotonicity and longest increasing subsequence of a data stream.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 730-736, 2008.

- [FalahatgarJOPS-15]
- Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapathi, and Ananda Theertha Suresh.
*Faster Algorithms for Testing under Conditional Sampling.*In*CoRR,*abs/1504.04103, 2015.

- [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):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.

- [FichtenbergerPS-15]
- Hendrik Fichtenberger, Pan Peng, and Christian Sohler.
*On constant-size graphs that preserve the local structure of high-girth graphs.*In*APPROX-RANDOM,*pages 786-799, 2015.

- [Forster-01]
- Jurgen Forster.
*A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity.*In*IEEE Conference on Computational Complexity*, pages 100-106, 2001.

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

- [GalG-07]
- Anna Gál and Parikshit Gopalan.
*Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence.*In*IEEE Symposium on Foundations of Computer Science*, pages 294-304, 2007.

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

- [Goldreich-17]
- Oded Goldreich.
*Introduction to Property Testing.*Cambridge University Press, November 2017.

- [GoldreichR-02]
- Oded Goldreich and Dana Ron.
*Property Testing in Bounded Degree Graphs.*Algorithmica, 32(2):302-343, 2002

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

- [GomoryH-61]
- R. E. Gomory and T. C. Hu.
*Multi-terminal network flows.*Journal of the Society for Industrial and Applied Mathematics, 9(4):551-570, 1961.

- [GopalanJKK-07]
- Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar.
*Estimating the sortedness of a data stream.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 318-327, 2007.

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

- [GrigorescuKS-08]
- Elena Grigorescu, Tali Kaufman, and Madhu Sudan.
*2-transitivity is insufficient for local testability.*In*IEEE Conference on Computational Complexity*, pages 259-267, 2008.

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

- [GuchtWWZ-15]
- Dirk Van Gucht, Ryan Williams, David P. Woodruff, and Qin Zhang.
*The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication.*In*PODS*, pages 199-212, 2015.

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

- [GuhaM-08]
- Sudipto Guha and Andrew McGregor.
*Tight lower bounds for multi-pass stream computation via pass elimination.*In*International Colloquium on Automata, Languages and Programming*, pages 760-772, 2008.

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

- [GuruswamiO-13]
- Venkatesan Guruswami and Krzysztof Onak.
*Superlinear lower bounds for multipass graph processing.*In*IEEE Conference on Computational Complexity*, 2013.

- [GuruswamiR-05]
- Venkatesan Guruswami and Atri Rudra.
*Tolerant Locally Testable Codes.*In*Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM)*, 2005.

- [HagerupKNR-98]
- Torben Hagerup, Jyrki Katajainen, Naomi Nishimura, and Prabhakar Ragde.
*Characterizing Multiterminal Flow Networks and Computing Flows in Networks of Small Treewidth.*In J. Comput. Syst. Sci. (JCSS) 57(3):366-375, 1998.

- [HarveyNO-08]
- Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak.
*Sketching and streaming entropy via approximation theory.*In*IEEE Symposium on Foundations of Computer Science*, pages 489-498, 2008.

- [HassidimKNO-09]
- Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, and Krzysztof Onak.
*Local graph partitions for approximation and testing.*In*IEEE Symposium on Foundations of Computer Science*, pages 22-31, 2009.

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

- [IndykP-11]
- Piotr Indyk and Eric Price.
*K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance.*In*ACM Symposium on Theory of Computing*, pages 627-636, 2011.

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

- [IndykR-13]
- Piotr Indyk and Ilya Razenshteyn.
*On Model-Based RIP-1 Matrices.*In*International Colloquium on Automata, Languages and Programming (ICALP)*, pages 564-575, 2013.

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

- [JainN-10]
- Rahul Jain and Ashwin Nayak.
*The space complexity of recognizing well-parenthesized expressions.*Electronic Colloquium on Computational Complexity (ECCC), 17:71, 2010.

- [Jakobsen-14]
- Sune Jakobsen.
*Information Theoretical Cryptogenography.*In*ITCS*, 2014.

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

- [JhaR-11]
- Madhav Jha and Sofya Raskhodnikova.
*Testing and reconstruction of Lipschitz functions with applications to data privacy.*Electronic Colloquium on Computational Complexity (ECCC), 18:57, 2011.

- [Jowhari-12]
- Hossein Jowhari.
*Efficient Communication Protocols for Deciding Edit Distance.*In*ESA*, 2012.

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

- [KamathT-19]
- Gautam Kamath, Christos Tzamos.
*Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing.*In*SODA*, 2019.

- [KaneMSS-12]
- Daniel M. Kane, Kurt Mehlhorn, Thomas Sauerwald, and He Sun.
*Counting Arbitrary Subgraphs in Data Streams.*In*Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (2)*, 2012.

- [KannanMSY-18]
- Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev.
*Linear Sketching over $\mathbb{F}_2$.*In CCC'18, https://eccc.weizmann.ac.il/report/2016/174/

- [Kapralov-12]
- Michael Kapralov.
*Improved lower bounds for matchings in the streaming model.*In*CoRR*, abs/1206.2269, 2012.

- [KapralovKS-15]
- Michael Kapralov, Sanjeev Khanna, and Madhu Sudan.
*Streaming Lower Bounds for Approximating MAX-CUT.*In*SODA*, pages 1263-1282, 2015.

- [KapralovKSV-17]
- Michael Kapralov, Sanjeev Khanna, Madhu Sudan, and Ameya Velingker.
*$(1+\Omega(1))$-Approximation to MAX-CUT Requires Linear Space.*In*SODA*, pages 1703-1722, 2017.

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

- [KerenidisLLRX-12]
- Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao.
*Lower bounds on information complexity via zero-communication protocols and applications.*In*FOCS*, 2012.

- [KhanR-14]
- Arindam Khan and Prasad Raghavendra.
*On mimicking networks representing minimum terminal cuts.*Inf. Process. Lett. (IPL) 114(7):365-371, 2014.

- [KhotN-06]
- Subhash Khot and Assaf Naor.
*Nonembeddability theorems via Fourier analysis.*Math. Ann., 334(4):821-852, 2006.

- [KoganK-15]
- Dmitry Kogan and Robert Krauthgamer.
*Sketching Cuts in Graphs and Hypergraphs.*In*ITCS*, pages 367-376, 2015.

- [KonradMM-12]
- Christian Konrad, Frederic Magniez, and Claire Mathieu.
*Maximum Matching in Semi-Streaming with Few Passes.*In*Proceedings of 15th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems,*2012.

- [KrahmerW-11]
- Felix Krahmer, Rachel Ward.
*New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property.*SIAM J. Math. Anal., 43(3):1269-1281, 2011.

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

- [KushilevitzOR-00]
- Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani.
*Efficient search for approximate nearest neighbor in high dimensional spaces.*SIAM J. Comput., 30(2):457-474, 2000.

- [LarsenW-17]
- Kasper Green Larsen and Ryan Williams.
*Faster Online Matrix-Vector Multiplication.*In*SODA*, pages 2182-2189, 2017.

- [LeviR-13]
- Reut Levi and Dana Ron.
*A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor.*In*CoRR*, abs/1302.3417, 2013.

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

- [LibenNowellVZ-06]
- David Liben-Nowell, Erik Vee, and An Zhu.
*Finding longest increasing and common subsequences in streaming data.*J. Comb. Optim., 11(2):155-175, 2006.

- [LibertySS-16]
- Edo Liberty, Ram Sriharsha, and Maxim Sviridenko.
*An Algorithm for Online K-Means Clustering.*In*ALENEX*, pages 81-89, 2016.

- [MagniezMN-10]
- Frédéric Magniez, Claire Mathieu, and Ashwin Nayak.
*Recognizing well-parenthesized expressions in the streaming model.*In*ACM Symposium on Theory of Computing*, pages 261-270, 2010.

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

- [ManjunathMPS-11]
- Madhusudan Manjunath, Kurt Mehlhorn, Konstantinos Panagiotou, and He Sun.
*Approximate Counting of Cycles in Streams.*In*Proceedings of the 19th Annual European Symposium*, 2011.

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

- [McGregorRU-11]
- Andrew McGregor, Atri Rudra, and Steve Uurtamo.
*Polynomial Fitting of Data Streams with Applications to Codeword Testing.*In*Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS)*, 2011.

- [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):143-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.

- [MontanaroO-09]
- Ashley Montanaro and Tobias Osborne.
*On the communication complexity of XOR functions.*In*CoRR,*abs/0909.3392, 2009.

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

- [NewmanR-13]
- Ilan Newman and Yuri Rabinovich.
*On Multiplicative $\lambda$-Approximations and Some Geometric Applications.*SIAM J. Comput. 42(3):855-883, 2013.

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

- [NguyenO-08]
- Huy N. Nguyen and Krzysztof Onak.
*Constant-time approximation algorithms via local improvements.*In*IEEE Symposium on Foundations of Computer Science*, pages 327-336, 2008.

- [Onak-10]
- Krzysztof Onak.
*New Sublinear Methods in the Struggle Against Classical Problems.*PhD thesis, Massachusetts Institute of Technology, 2010.

- [OnakRRR-12]
- Krzysztof Onak, Dana Ron, Michal Rosen, and Ronitt Rubinfeld.
*A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size.*In*ACM-SIAM Symposium on Discrete Algorithms*, pages 1123-1131, 2012.

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

- [Pogrow-17]
- Yosef Pogrow.
*Solving Symmetric Diagonally Dominant Linear Systems in Sublinear Time and Some Observations on Graph Sparsification.*MSc thesis, Weizmann Institute of Science, 2017.

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

- [RudraU-10]
- Atri Rudra and Steve Uurtamo.
*Data Stream Algorithms for Codeword Testing.*In*Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP),*2010.

- [SeshadhriV-11]
- C. Seshadhri and Jan Vondrák.
*Is submodularity testable?*In*ICS*, 2011.

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

- [Thaler-16]
- Justin Thaler.
*Semi-Streaming Algorithms for Annotated Graph Streams.*In*ICALP*, 2016.

- [Trevisan-09]
- Luca Trevisan.
*Max Cut and the smallest eigenvalue.*In*ACM Symposium on Theory of Computing*, pages 263-272, 2009.

- [ValiantV-11]
- Gregory Valiant and Paul Valiant.
*The Power of Linear Estimators*. In*FOCS*, 2011.

- [ValiantV-14]
- Gregory Valiant and Paul Valiant.
*An Automatic Inequality Prover and Instance Optimal Identity Testing*. In*FOCS*, 2014.

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

- [YoshidaYI-09]
- Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito.
*An improved constant-time approximation algorithm for maximum matchings.*In*ACM Symposium on Theory of Computing*, pages 225-234, 2009.