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 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|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 | + | {{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|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|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|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|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|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|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|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|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| | + | {{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|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 149: | ||
{{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|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 160: | ||
{{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| | + | {{bibentry|Donoho-06|David L. Donoho. ''Compressed sensing.'' IEEE Transactions on Information Theory, 52(4):1289-1306, 2006.}} |
− | {{bibentry| | + | {{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 173: | ||
{{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 236: | Line 200: | ||
{{bibentry|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.}} | {{bibentry|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.}} | ||
− | {{bibentry|Forster-01|Jurgen Forster. ''A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity.'' In | + | {{bibentry|Forster-01|Jurgen Forster. ''A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity.'' In "Proceedings of the 16th Annual {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 251: | Line 213: | ||
{{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|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 253: | ||
{{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 345: | Line 297: | ||
{{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|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| | + | {{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 308: | ||
{{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| | + | {{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| | + | {{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 317: | ||
{{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|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 324: | ||
{{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 369: | ||
{{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.}} | ||
− | |||
− | |||
− | |||
− | |||
{{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 376: | ||
{{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|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|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 393: | ||
{{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|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 398: | ||
{{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| | + | {{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|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.}} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |