Bibliography

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.

[EdenJPRS-18]

Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C. Seshadhri. Provable and practical approximations for the degree distribution using sublinear graph samples. In WWW, pages 449–458. 2018.

[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-19a]

Oded Goldreich. Testing graphs in vertex-distribution-free models. In STOC, pages 527–534, 2019.

[Goldreich-19b]

Oded Goldreich. On the complexity of estimating the effective support size. Electronic Colloquium on Computational Complexity (ECCC), 26:88, 2019.

[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

[GoldreichGR-98]

Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653–750, 1998.

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

[Paninski-08]

Liam Paninski. A coincidence-based test for uniformity given very sparsely sampled discrete data. In IEEE Trans. Information Theory, 54(10):4750–4755, 2008.

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