Editing Bibliography
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 102: | Line 102: | ||
{{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|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 145: | Line 143: | ||
{{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|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.}} | ||
Line 153: | Line 149: | ||
{{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|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 207: | Line 197: | ||
{{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|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 225: | ||
{{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|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 253: | Line 239: | ||
{{bibentry|Goldreich-17|Oded Goldreich. ''Introduction to Property Testing.'' Cambridge University Press, November 2017.}} | {{bibentry|Goldreich-17|Oded Goldreich. ''Introduction to Property Testing.'' Cambridge University Press, November 2017.}} | ||
− | |||
− | |||
− | |||
− | |||
{{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|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 279: | ||
{{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|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 357: | Line 335: | ||
{{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|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 343: | ||
{{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|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 397: | ||
{{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|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.}} | ||
Line 442: | Line 412: | ||
{{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|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.}} | ||
Line 473: | Line 443: | ||
{{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.}} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |