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 145: | Line 125: | ||
{{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.}} | ||
− | + | {{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 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{{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|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 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|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|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|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 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|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|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 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| | + | {{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 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|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|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 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|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 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|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| | + | {{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.}} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |