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 6: Line 6:
 
{{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|AcharyaDOST-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|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 19: Line 19:
  
 
{{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 55:
  
 
{{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 102: Line 94:
 
{{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 102:
 
{{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 145: Line 131:
  
 
{{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|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|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 182: Line 160:
 
{{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|DaskalakisKW-18|Constantinos Daskalakis, Gautam Kamath, and John Wright. ''Which Distribution Distances are Sublinearly Testable?'' 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 207: Line 185:
  
 
{{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 213:
  
 
{{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 225:
  
 
{{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 265:
  
 
{{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 309:
  
 
{{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 357: Line 319:
  
 
{{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.}}
Line 367: Line 327:
  
 
{{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|KoganK-15|Dmitry Kogan and Robert Krauthgamer. ''Sketching Cuts in Graphs and Hypergraphs.'' In ''ITCS'', pages 367-376, 2015.}}
Line 423: Line 381:
  
 
{{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|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 436: Line 388:
 
{{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 457: Line 405:
  
 
{{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 471: Line 417:
  
 
{{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|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: