Editing Bibliography

Jump to: navigation, search

Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.

The edit can be undone. Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
Latest revision Your text
Line 5: Line 5:
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
−
 
−
{{bibentry|AcharyaDOS-17|Jayadev Acharya, Hirakendu Das, Alon Orlitsky, and Ananda Theertha Suresh. ''Estimating Symmetric Properties of Distributions: A Maximum Likelihood Approach .'' In ''ICML'', 2017.}}
 
−
 
−
{{bibentry|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.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
Line 16: Line 12:
 
{{bibentry|AhnGM-12|Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. ''Analyzing graph structure via linear measurements.'' In ''SODA'', pages 459-467, 2012.}}
 
{{bibentry|AhnGM-12|Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. ''Analyzing graph structure via linear measurements.'' In ''SODA'', pages 459-467, 2012.}}
  
−
{{bibentry|AhnGM-12b|Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. ''Graph sketches: sparsification, spanners, and subgraphs.'' In ''PODS'', pages 5-14, 2012.}}
+
{{bibentry|AhnGM-12b|Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. ''Graph sketches: sparsification, spanners, and subgraphs'' In ''PODS'', pages 5-14, 2012.}}
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
−
 
−
{{bibentry|Alon-02|Noga Alon. ''Testing subgraphs in large graphs.'' Random Struct. Algorithms, 21(3-4):359-370, 2002.}}
 
−
 
−
{{bibentry|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.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
Line 59: Line 51:
  
 
{{bibentry|Baswana-06|Surender Baswana. ''Faster streaming algorithms for graph spanners.'' 2006.}}
 
{{bibentry|Baswana-06|Surender Baswana. ''Faster streaming algorithms for graph spanners.'' 2006.}}
−
 
−
{{bibentry|BatsonSS-14|Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. ''Twice-Ramanujan Sparsifiers.'' SIAM Review 56(2):315-334, 2014.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
−
 
−
{{bibentry|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.}}
 
  
 
{{bibentry|BenderR-02|Michael A. Bender and Dana Ron. ''Testing properties of directed graphs: acyclicity and connectivity.'' Random Struct. Algorithms, 20(2):184-205, 2002.}}
 
{{bibentry|BenderR-02|Michael A. Bender and Dana Ron. ''Testing properties of directed graphs: acyclicity and connectivity.'' Random Struct. Algorithms, 20(2):184-205, 2002.}}
Line 81: Line 69:
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
−
 
−
{{bibentry|BlaisCG-17| Eric Blais, Clément L. Canonne, and Tom Gur. ''Distribution Testing Lower Bounds via Reductions from Communication Complexity''. In ''CCC'', 2017.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
Line 102: Line 88:
 
{{bibentry|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.}}
 
{{bibentry|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.}}
  
−
{{bibentry|BrodyJSW-14|Joshua Brody, Sune K. Jakobsen, Dominik Scheder, and Peter Winkler. ''Cryptogenography.'' In ''ITCS'', pages 13-22, 2014.}}
+
{{bibentry|BrodyJSW-14| Joshua Brody, Sune K. Jakobsen, Dominik Scheder, and Peter Winkler. ''Cryptogenography.'' In ''ITCS'', pages 13-22, 2014.}}
−
 
 
−
{{bibentry|BunNS-18|Mark Bun, Jelani Nelson, and Uri Stemmer. ''Heavy Hitters and the Structure of Local Privacy.'' In ''PODS'', pages 435-447, 2018.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
Line 112: Line 96:
 
{{bibentry|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.}}
 
{{bibentry|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.}}
  
−
{{bibentry|Canonne-15|Clément L. Canonne. ''Big Data on the rise? Testing monotonicity of distributions.'' In ''ICALP'', 2015.}}
+
{{bibentry|CanonneGR-16|Clément L. Canonne, Themis Gouleakis, and Ronitt Rubinfeld. ''Sampling Correctors.'' In ''ITCS'' (to appear), 2016.}}
−
 
 
−
{{bibentry|CanonneGR-16|Clément L. Canonne, Themis Gouleakis, and Ronitt Rubinfeld. ''Sampling Correctors.'' In ''ITCS'', 2016.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
−
 
−
{{bibentry|CarlsonKST-17|Charles Carlson, Alexandra Kolla, Nikhil Srivastava, and Luca Trevisan. ''Optimal Lower Bounds for Sketching Graph Cuts.'' In ''CoRR,'' abs/1712.10261, 2017.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
Line 127: Line 107:
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
−
 
−
{{bibentry|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.}}
 
  
 
{{bibentry|ChakrabartiK-14|Amit Chakrabarti and Sagar Kale. ''Submodular Maximization Meets Streaming: Matchings, Matroids, and More.'' In ''IPCO'', to appear, 2014.}}
 
{{bibentry|ChakrabartiK-14|Amit Chakrabarti and Sagar Kale. ''Submodular Maximization Meets Streaming: Matchings, Matroids, and More.'' In ''IPCO'', to appear, 2014.}}
Line 146: Line 124:
 
{{bibentry|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.}}
 
{{bibentry|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.}}
  
−
{{bibentry|ChenKPSSY21|Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu. ''Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs.'' ICALP 2021: 52:1-52:19.}}
+
{{bibentry|ChakrabartiCMTV-15|Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. ''Verifiable Stream Computation and Arthur-Merlin Communication.'' In Proceedings of the 30th Conference on Computational Complexity, pages 217--243, 2015.}}
  
 
{{bibentry|ChienRS-03|Steve Chien, Lars Eilstrup Rasmussen, and Alistair Sinclair. ''Clifford algebras and approximating the permanent.'' J. Comput. Syst. Sci. 67(2), 2003.}}
 
{{bibentry|ChienRS-03|Steve Chien, Lars Eilstrup Rasmussen, and Alistair Sinclair. ''Clifford algebras and approximating the permanent.'' J. Comput. Syst. Sci. 67(2), 2003.}}
  
−
{{bibentry|ChiesaG-17|Alessandro Chiesa and Tom Gur. ''Proofs of Proximity for Distribution Testing.'' Electronic Colloquium on Computational Complexity (ECCC) 24:155, 2017.}}
+
{{bibentry|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.}}
−
 
 
−
{{bibentry|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.}}
 
−
 
 
−
{{bibentry|ChouGV-20|Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy. ''Optimal streaming approximations for all Boolean Max-2CSPs and Max-kSAT.'' In ''FOCS'', pages 330-341, 2020.}}
 
−
 
 
−
{{bibentry|ChouGSV-21|Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. ''Approximability of all Boolean CSPs with linear sketches.'' 2021.}}
 
−
 
 
−
{{bibentry|ChouGSV-21a|Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. ''Approximability of all finite CSPs with linear sketches.'' In ''FOCS'', pages 1197-1208, 2021.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
Line 181: Line 151:
  
 
{{bibentry|DaskalakisDS-11|Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. ''Learning transformed product distributions.'' CoRR, abs/1103.0598, 2011.}}
 
{{bibentry|DaskalakisDS-11|Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. ''Learning transformed product distributions.'' CoRR, abs/1103.0598, 2011.}}
−
 
−
{{bibentry|DaskalakisKW-18|Constantinos Daskalakis, Gautam Kamath, and John Wright. ''Which Distribution Distances are Sublinearly Testable?'' In ''SODA'', 2018.}}
 
  
 
{{bibentry|DasSarmaGP-08|Atish Das Sarma, Sreenivas Gollapudi, and Rina Panigrahy. ''Estimating PageRank on graph streams.'' In ''PODS'', pages 69-78, 2008.}}
 
{{bibentry|DasSarmaGP-08|Atish Das Sarma, Sreenivas Gollapudi, and Rina Panigrahy. ''Estimating PageRank on graph streams.'' In ''PODS'', pages 69-78, 2008.}}
Line 194: Line 162:
 
{{bibentry|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.}}
 
{{bibentry|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.}}
  
−
{{bibentry|DoerrK-16|Benjamin Doerr, Marvin Kunnemann. ''Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem.'' In ''ICALP'', 2016.}}
+
{{bibentry|Donoho-06|David L. Donoho. ''Compressed sensing.'' IEEE Transactions on Information Theory, 52(4):1289-1306, 2006.}}
  
−
{{bibentry|Donoho-06|David L. Donoho. ''Compressed sensing.'' IEEE Transactions on Information Theory, 52(4):1289-1306, 2006.}}
+
{{bibentry|DoerrK-16|Benjamin Doerr, Marvin Kunnemann. ''Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem.'' In ''ICALP'', 2016.}}
  
 
{{bibentry|DrakeH-03|Doratha E. Drake and Stefan Hougardy. ''Improved linear time approximation algorithms for weighted matchings.'' In ''RANDOM-APPROX'', pages 14-23, 2003.}}
 
{{bibentry|DrakeH-03|Doratha E. Drake and Stefan Hougardy. ''Improved linear time approximation algorithms for weighted matchings.'' In ''RANDOM-APPROX'', pages 14-23, 2003.}}
Line 207: Line 175:
  
 
{{bibentry|Eddy-04|Sean R Eddy. ''How do RNA folding algorithms work?'' Nature Biotechnology, 22, pages 1457-1458, 2004.}}
 
{{bibentry|Eddy-04|Sean R Eddy. ''How do RNA folding algorithms work?'' Nature Biotechnology, 22, pages 1457-1458, 2004.}}
−
 
−
{{bibentry|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.}}
 
  
 
{{bibentry|Edmonds-65|Jack Edmonds. ''Maximum matching and a polyhedron with 0,1-vertices.'' J. Res. Nat. Bur. Standards, 69(B):125-130, 1965.}}
 
{{bibentry|Edmonds-65|Jack Edmonds. ''Maximum matching and a polyhedron with 0,1-vertices.'' J. Res. Nat. Bur. Standards, 69(B):125-130, 1965.}}
Line 237: Line 203:
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
−
 
−
{{bibentry|ForsterY-19|Sebastian Forster and Liu Yang. ''A faster local algorithm for detecting bounded-size cuts with applications to higher-connectivity problems.'' In ''CoRR,'' abs/1904.08382, 2019.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
Line 251: Line 215:
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
−
 
−
{{bibentry|Goldreich-17|Oded Goldreich. ''Introduction to Property Testing.'' Cambridge University Press, November 2017.}}
 
−
 
−
{{bibentry|Goldreich-19a|Oded Goldreich. ''Testing graphs in vertex-distribution-free models.'' In ''STOC'', pages 527–534, 2019.}}
 
−
 
−
{{bibentry|Goldreich-19b|Oded Goldreich. ''On the complexity of estimating the effective support size.'' Electronic Colloquium on Computational Complexity (ECCC), 26:88, 2019.}}
 
  
 
{{bibentry|GoldreichR-02|Oded Goldreich and Dana Ron. ''Property Testing in Bounded Degree Graphs.'' Algorithmica, 32(2):302-343, 2002}}
 
{{bibentry|GoldreichR-02|Oded Goldreich and Dana Ron. ''Property Testing in Bounded Degree Graphs.'' Algorithmica, 32(2):302-343, 2002}}
−
 
−
{{bibentry|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.}}
 
  
 
{{bibentry|GolubV-89|G.H. Golub and C.F. Van Loan. ''Matrix Computations.'' Johns Hopkins University Press, Baltimore, 1989.}}
 
{{bibentry|GolubV-89|G.H. Golub and C.F. Van Loan. ''Matrix Computations.'' Johns Hopkins University Press, Baltimore, 1989.}}
Line 299: Line 255:
  
 
{{bibentry|GuruswamiR-05|Venkatesan Guruswami and Atri Rudra. ''Tolerant Locally Testable Codes.'' In ''Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM)'', 2005.}}
 
{{bibentry|GuruswamiR-05|Venkatesan Guruswami and Atri Rudra. ''Tolerant Locally Testable Codes.'' In ''Proceedings of the 9th International Workshop on Randomization and Computation (RANDOM)'', 2005.}}
−
 
−
{{bibentry|GuruswamiVV-17|Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy. ''Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph.'' In ''Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM)'', 2017.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
Line 345: Line 299:
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
−
 
−
{{bibentry|KamathT-19|Gautam Kamath, Christos Tzamos. ''Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing.'' In ''SODA'',  2019.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
  
−
{{bibentry|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/}}
+
{{bibentry|KannanMY-16|Sampath Kannan, Elchanan Mossel, and Grigory Yaroslavtsev. ''Linear Sketching over $\mathbb{F}_2$.'' In ''CoRR,'' abs/1611.01879, 2016.}}
  
 
{{bibentry|Kapralov-12|Michael Kapralov. ''Improved lower bounds for matchings in the streaming model.'' In ''CoRR'', abs/1206.2269, 2012.}}
 
{{bibentry|Kapralov-12|Michael Kapralov. ''Improved lower bounds for matchings in the streaming model.'' In ''CoRR'', abs/1206.2269, 2012.}}
Line 358: Line 310:
 
{{bibentry|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.}}
 
{{bibentry|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.}}
  
−
{{bibentry|KapralovK-19|Michael Kapralov and Dmitry Krachun. ''An optimal space lower bound for approximating MAX-CUT.'' In ''STOC'', pages 277-288, 2019.}}
+
{{bibentry|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.}}
  
−
{{bibentry|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.}}
+
{{bibentry|KoganK-15|Dmitry Kogan and Robert Krauthgamer. ''Sketching Cuts in Graphs and Hypergraphs'' In ''ITCS'', pages 367--376, 2015.}}
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
Line 367: Line 319:
  
 
{{bibentry|KhotN-06|Subhash Khot and Assaf Naor. ''Nonembeddability theorems via Fourier analysis.'' Math. Ann., 334(4):821-852, 2006.}}
 
{{bibentry|KhotN-06|Subhash Khot and Assaf Naor. ''Nonembeddability theorems via Fourier analysis.'' Math. Ann., 334(4):821-852, 2006.}}
−
 
−
{{bibentry|KhotN-19|Subhash Khot and Assaf Naor. ''The Andoni–Krauthgamer–Razenshteyn characterization of sketchable norms fails for sketchable metrics.'' In ''SODA'', pages 1814-1824. 2019}}
 
−
 
−
{{bibentry|KoganK-15|Dmitry Kogan and Robert Krauthgamer. ''Sketching Cuts in Graphs and Hypergraphs.'' In ''ITCS'', pages 367-376, 2015.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
Line 378: Line 326:
 
{{bibentry|KuroseR-04|James F. Kurose and Keith W. Ross. ''Computer Networking: A Top-Down Approach Featuring the Internet.'' Addison Wesley, 2004.}}
 
{{bibentry|KuroseR-04|James F. Kurose and Keith W. Ross. ''Computer Networking: A Top-Down Approach Featuring the Internet.'' Addison Wesley, 2004.}}
  
−
{{bibentry|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.}}
+
{{bibentry|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.}}
  
 
{{bibentry|LarsenW-17|Kasper Green Larsen and Ryan Williams. ''Faster Online Matrix-Vector Multiplication.''  In ''SODA'', pages 2182-2189, 2017.}}
 
{{bibentry|LarsenW-17|Kasper Green Larsen and Ryan Williams. ''Faster Online Matrix-Vector Multiplication.''  In ''SODA'', pages 2182-2189, 2017.}}
Line 423: Line 371:
  
 
{{bibentry|Muthukrishnan-06a|S. Muthukrishnan. ''Some algorithmic problems and results in compressed sensing.'' In ''Allerton Conference'', 2006.}}
 
{{bibentry|Muthukrishnan-06a|S. Muthukrishnan. ''Some algorithmic problems and results in compressed sensing.'' In ''Allerton Conference'', 2006.}}
−
 
−
{{bibentry|NanongkaiSY-19a|Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. ''Breaking quadratic time for small vertex connectivity and an approximation scheme.'' In ''STOC'', pages 241–252, 2019.}}
 
−
 
−
{{bibentry|NanongkaiSY-19b|Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. ''Computing and testing small vertex connectivity in near-linear time and queries.'' In ''CoRR,'' abs/1905.05329, 2019.}}
 
  
 
{{bibentry|NaorS-06|Assaf Naor and Gideon Schechtman. ''Planar earthmover is not in $l_1$.'' In ''FOCS'', pages 655-666, 2006.}}
 
{{bibentry|NaorS-06|Assaf Naor and Gideon Schechtman. ''Planar earthmover is not in $l_1$.'' In ''FOCS'', pages 655-666, 2006.}}
−
 
−
{{bibentry|NarayananT-22|Shyam Narayanan and Jakub Tětek. ''Estimating the effective support size in constant query complexity.'' In ''CoRR,'' abs/2211.11344, 2022.}}
 
−
 
−
{{bibentry|NewmanR-13|Ilan Newman and Yuri Rabinovich. ''On Multiplicative $\lambda$-Approximations and Some Geometric Applications.''  SIAM J. Comput. 42(3):855-883, 2013.}}
 
  
 
{{bibentry|NeedellT-10|Deanna Needell and Joel A. Tropp. ''Cosamp: iterative signal recovery from incomplete and inaccurate samples.'' Commun. ACM, 53(12):93-100, 2010.}}
 
{{bibentry|NeedellT-10|Deanna Needell and Joel A. Tropp. ''Cosamp: iterative signal recovery from incomplete and inaccurate samples.'' Commun. ACM, 53(12):93-100, 2010.}}
Line 438: Line 378:
 
{{bibentry|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.}}
 
{{bibentry|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.}}
  
−
{{bibentry|Onak-10|Krzysztof Onak. ''New Sublinear Methods in the Struggle Against Classical Problems.'' PhD thesis, Massachusetts Institute of Technology, 2010.}}
+
{{bibentry|Onak-10|Krzysztof Onak. ''New Sublinear Methods in the Struggle Against Classical Problems.''PhD thesis, Massachusetts Institute of Technology, 2010.}}
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
−
 
−
{{bibentry|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.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
−
 
−
{{bibentry|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.}}
 
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
Line 459: Line 395:
  
 
{{bibentry|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.}}
 
{{bibentry|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.}}
−
 
−
{{bibentry|Sudan-22|Madhu Sudan. ''Streaming and Sketching Complexity of CSPs: A survey.'' In ''ICALP'', 2022.}}
 
  
 
{{bibentry|Thaler-16|Justin Thaler. ''Semi-Streaming Algorithms for Annotated Graph Streams.'' In ''ICALP'', 2016.}}
 
{{bibentry|Thaler-16|Justin Thaler. ''Semi-Streaming Algorithms for Annotated Graph Streams.'' In ''ICALP'', 2016.}}
Line 466: Line 400:
 
{{bibentry|Trevisan-09|Luca Trevisan. ''Max Cut and the smallest eigenvalue.'' In ''ACM Symposium on Theory of Computing'', pages 263-272, 2009.}}
 
{{bibentry|Trevisan-09|Luca Trevisan. ''Max Cut and the smallest eigenvalue.'' In ''ACM Symposium on Theory of Computing'', pages 263-272, 2009.}}
  
−
{{bibentry|ValiantV-11|Gregory Valiant and Paul Valiant. ''The Power of Linear Estimators''. In ''FOCS'', 2011.}}
+
{{bibentry|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.}}
−
 
 
−
{{bibentry|ValiantV-14|Gregory Valiant and Paul Valiant. ''An Automatic Inequality Prover and Instance Optimal Identity Testing''. In ''FOCS'', 2014.}}
 
  
 
{{bibentry|Woodruff-04|David P. Woodruff. ''Optimal space lower bounds for all frequency moments.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 167-175, 2004.}}
 
{{bibentry|Woodruff-04|David P. Woodruff. ''Optimal space lower bounds for all frequency moments.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 167-175, 2004.}}
−
 
−
{{bibentry|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.}}
 
−
 
−
{{bibentry|Yu-21|Huacheng Yu. ''Tight distributed sketching lower bound for connectivity.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', 2021.}}
 
−
 
−
{{bibentry|MannorT-04|Shie Mannor and John N. Tsitsiklis. ''The Sample Complexity of Exploration in the Multi-Armed Bandit Problem.'' J. Mach. Learn. Res., 2004.}}
 
−
 
−
{{bibentry|AssadiW-20|Sepehr Assadi and Chen Wang. ''Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits.'' In ''Annual ACM Symposium on Theory of Computing'', 2020.}}
 
−
 
−
{{bibentry|JinHTX-21|Tianyuan Jin, Keke Huang, Jing Tang, Xiaokui Xiao. ''Optimal Streaming Algorithms for Multi-Armed Bandits.'' In ''International Conference on Machine Learning'', 2021.}}
 

Please note that all contributions to Open Problems in Sublinear Algorithms may be edited, altered, or removed by other contributors. If you do not want your writing to be edited mercilessly, then do not submit it here.
You are also promising us that you wrote this yourself, or copied it from a public domain or similar free resource (see Open Problems in Sublinear Algorithms:Copyrights for details). Do not submit copyrighted work without permission!

To edit this page, please answer the question that appears below (more info):

Cancel Editing help (opens in new window)

Templates used on this page:

Retrieved from "https://sublinear.info/index.php?title=Bibliography"