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 1: | Line 1: | ||
− | + | '''Citations:''' Write <tt>{{cite|</tt>''paper_id_1''<tt>|</tt>''paper_id_2''<tt>|</tt>…<tt>|</tt>''paper_id_k''<tt>}}</tt> to cite papers ''paper_id_1'', ''paper_id_2'', …, ''paper_id_k''. For instance, <tt>{{cite|AlonMS-99|BlumLR-93}}</tt> results in {{cite|AlonMS-99|BlumLR-93}}. | |
− | + | ---- | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{{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 15: | Line 6: | ||
{{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|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), pages 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) | ||
− | |||
− | |||
{{bibentry|AndoniDIW-09|Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David P. Woodruff. ''Efficient sketches for earth-mover distance, with applications.'' In ''IEEE Symposium on Foundations of Computer Science'', pages 324-330, 2009.}} | {{bibentry|AndoniDIW-09|Alexandr Andoni, Khanh Do Ba, Piotr Indyk, and David P. Woodruff. ''Efficient sketches for earth-mover distance, with applications.'' In ''IEEE Symposium on Foundations of Computer Science'', pages 324-330, 2009.}} | ||
− | |||
− | |||
{{bibentry|AndoniIK-08|Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. ''Earth mover distance over high-dimensional spaces.'' In ''SODA'', pages 343-352, 2008.}} | {{bibentry|AndoniIK-08|Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. ''Earth mover distance over high-dimensional spaces.'' In ''SODA'', pages 343-352, 2008.}} | ||
Line 40: | Line 21: | ||
{{bibentry|AndoniKR-14|Alexandr Andoni, Robert Krauthgamer, and Ilya Razenshteyn. ''Sketching and Embedding are Equivalent for Norms.'' In ''CoRR,'' abs/1411.2577, 2014.}} | {{bibentry|AndoniKR-14|Alexandr Andoni, Robert Krauthgamer, and Ilya Razenshteyn. ''Sketching and Embedding are Equivalent for Norms.'' In ''CoRR,'' abs/1411.2577, 2014.}} | ||
− | {{bibentry|AndoniN-12|Alexandr Andoni | + | {{bibentry|AndoniN-12|Alexandr Andoni, Huy L. Nguyen. ''Width of points in the streaming model.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 447-452, 2012.}} |
{{bibentry|AndoniO-09|Alexandr Andoni and Krzysztof Onak. ''Approximating edit distance in near-linear time.'' In ''ACM Symposium on Theory of Computing'', pages 199-204, 2009.}} | {{bibentry|AndoniO-09|Alexandr Andoni and Krzysztof Onak. ''Approximating edit distance in near-linear time.'' In ''ACM Symposium on Theory of Computing'', pages 199-204, 2009.}} | ||
− | |||
− | |||
− | |||
− | |||
{{bibentry|BahBC-14|Bubaccar Bah, Luca Baldassarre, and Volkan Cevher. ''Model-based Sketching and Recovery with Expanders.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', 2014.}} | {{bibentry|BahBC-14|Bubaccar Bah, Luca Baldassarre, and Volkan Cevher. ''Model-based Sketching and Recovery with Expanders.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', 2014.}} | ||
Line 59: | Line 36: | ||
{{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|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 73: | Line 44: | ||
{{bibentry|BerindeIR-08|Radu Berinde, Piotr Indyk, and Milan Ruzic. ''Practical near-optimal sparse recovery in the $l_1$ norm.'' Allerton, 2008.}} | {{bibentry|BerindeIR-08|Radu Berinde, Piotr Indyk, and Milan Ruzic. ''Practical near-optimal sparse recovery in the $l_1$ norm.'' Allerton, 2008.}} | ||
− | |||
− | |||
{{bibentry|BhattacharyyaMMY-07|S. Bhattacharyya, A. Madeira, S. Muthukrishnan, and T. Ye. ''How to scalably skip past streams.'' In ''WSSP (Workshop with ICDE)'', 2007.}} | {{bibentry|BhattacharyyaMMY-07|S. Bhattacharyya, A. Madeira, S. Muthukrishnan, and T. Ye. ''How to scalably skip past streams.'' In ''WSSP (Workshop with ICDE)'', 2007.}} | ||
Line 82: | Line 51: | ||
{{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), pages 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) | ||
{{bibentry|BogdanovOT-02|Andrej Bogdanov, Kenji Obata, and Luca Trevisan. ''A lower bound for testing 3-colorability in bounded-degree graphs.'' In ''FOCS'', pages 93-102, 2002.}} | {{bibentry|BogdanovOT-02|Andrej Bogdanov, Kenji Obata, and Luca Trevisan. ''A lower bound for testing 3-colorability in bounded-degree graphs.'' In ''FOCS'', pages 93-102, 2002.}} | ||
{{bibentry|BonisGV-05|Annalisa De Bonis, Leszek Gasieniec, and Ugo Vaccaro. ''Optimal two-stage algorithms for group testing problems.'' SIAM J. Comput., 34(5):1253-1270, 2005.}} | {{bibentry|BonisGV-05|Annalisa De Bonis, Leszek Gasieniec, and Ugo Vaccaro. ''Optimal two-stage algorithms for group testing problems.'' SIAM J. Comput., 34(5):1253-1270, 2005.}} | ||
− | |||
− | |||
{{bibentry|BravermanGPW-13|Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. ''Information lower bounds via self-reducibility.'' In ''CSR'', 2013.}} | {{bibentry|BravermanGPW-13|Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. ''Information lower bounds via self-reducibility.'' In ''CSR'', 2013.}} | ||
Line 96: | Line 61: | ||
{{bibentry|BravermanO-10|Vladimir Braverman and Rafail Ostrovsky. ''Zero-one frequency laws.'' In ''ACM Symposium on Theory of Computing'', pages 281-290, 2010.}} | {{bibentry|BravermanO-10|Vladimir Braverman and Rafail Ostrovsky. ''Zero-one frequency laws.'' In ''ACM Symposium on Theory of Computing'', pages 281-290, 2010.}} | ||
− | {{bibentry|BroderCFM-00|Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. ''Min-wise independent permutations.'' ''J. Comput. Syst. Sci.'', 60(3) | + | {{bibentry|BroderCFM-00|Andrei Z. Broder, Moses Charikar, Alan M. Frieze, and Michael Mitzenmacher. ''Min-wise independent permutations.'' ''J. Comput. Syst. Sci.'', 60(3), pages 630-659, 2000.}} |
{{bibentry|BrodyC-09|Joshua Brody and Amit Chakrabarti. ''A multi-round communication lower bound for Gap Hamming and some consequences.'' In ''IEEE Conference on Computational Complexity'', pages 358-368, 2009.}} | {{bibentry|BrodyC-09|Joshua Brody and Amit Chakrabarti. ''A multi-round communication lower bound for Gap Hamming and some consequences.'' In ''IEEE Conference on Computational Complexity'', pages 358-368, 2009.}} | ||
{{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|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.}} | ||
{{bibentry|CandesRT-06|Emmanuel J. Candès, Justin K. Romberg, and Terence Tao. ''Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information.'' IEEE Transactions on Information Theory, 52(1):489-509, 2006.}} | {{bibentry|CandesRT-06|Emmanuel J. Candès, Justin K. Romberg, and Terence Tao. ''Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information.'' IEEE Transactions on Information Theory, 52(1):489-509, 2006.}} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{{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| | + | {{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|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 82: | ||
{{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 144: | Line 97: | ||
{{bibentry|Charikar-02|Moses Charikar. ''Similarity estimation techniques from rounding algorithms.'' In ''STOC'', pages 380-388, 2002.}} | {{bibentry|Charikar-02|Moses Charikar. ''Similarity estimation techniques from rounding algorithms.'' In ''STOC'', pages 380-388, 2002.}} | ||
− | {{bibentry|ChazelleRT-05|Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. ''Approximating the Minimum Spanning Tree Weight in Sublinear Time.'' SIAM J. Comput. 34(6) | + | {{bibentry|ChazelleRT-05|Bernard Chazelle, Ronitt Rubinfeld, and Luca Trevisan. ''Approximating the Minimum Spanning Tree Weight in Sublinear Time.'' SIAM J. Comput. 34(6), pages 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|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), pages 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) | ||
{{bibentry|CormodeKMS-06|Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava. ''Space- and time-efficient deterministic algorithms for biased quantiles over data streams.'' In ''PODS'', pages 263-272, 2006.}} | {{bibentry|CormodeKMS-06|Graham Cormode, Flip Korn, S. Muthukrishnan, and Divesh Srivastava. ''Space- and time-efficient deterministic algorithms for biased quantiles over data streams.'' In ''PODS'', pages 263-272, 2006.}} | ||
− | {{bibentry|CormodeM-05|Graham Cormode and S. Muthukrishnan. ''An improved data stream summary: the count-min sketch and its applications.'' ''J. Algorithms'', 55(1) | + | {{bibentry|CormodeM-05|Graham Cormode and S. Muthukrishnan. ''An improved data stream summary: the count-min sketch and its applications.'' ''J. Algorithms'', 55(1), pages 58-75, 2005.}} |
− | {{bibentry|CormodeM-05a|Graham Cormode and S. Muthukrishnan. ''What's new: finding significant differences in network data streams.'' ''IEEE/ACM Trans. Netw.'', 13(6) | + | {{bibentry|CormodeM-05a|Graham Cormode and S. Muthukrishnan. ''What's new: finding significant differences in network data streams.'' ''IEEE/ACM Trans. Netw.'', 13(6), pages 1219-1232, 2005.}} |
{{bibentry|CormodeM-05b|Graham Cormode and S. Muthukrishnan. ''Space efficient mining of multigraph streams.'' In ''ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems'', pages 271-282, 2005.}} | {{bibentry|CormodeM-05b|Graham Cormode and S. Muthukrishnan. ''Space efficient mining of multigraph streams.'' In ''ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems'', pages 271-282, 2005.}} | ||
Line 177: | Line 118: | ||
{{bibentry|CrouchS-14|Michael Crouch and Daniel Stubbs. In Andrew McGregor's presentation at the 2014 Bertinoro Workshop on Sublinear Algorithms.}} | {{bibentry|CrouchS-14|Michael Crouch and Daniel Stubbs. In Andrew McGregor's presentation at the 2014 Bertinoro Workshop on Sublinear Algorithms.}} | ||
− | |||
− | |||
{{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 193: | Line 130: | ||
{{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|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.}} | ||
Line 207: | Line 142: | ||
{{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 219: | Line 152: | ||
{{bibentry|ErgunJ-08|Funda Ergün and Hossein Jowhari. ''On distance to monotonicity and longest increasing subsequence of a data stream.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 730-736, 2008.}} | {{bibentry|ErgunJ-08|Funda Ergün and Hossein Jowhari. ''On distance to monotonicity and longest increasing subsequence of a data stream.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 730-736, 2008.}} | ||
− | |||
− | |||
{{bibentry|FeigenbaumKMSZ-05|Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. ''Graph distances in the streaming model: the value of space.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 745-754, 2005.}} | {{bibentry|FeigenbaumKMSZ-05|Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. ''Graph distances in the streaming model: the value of space.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 745-754, 2005.}} | ||
Line 228: | Line 159: | ||
{{bibentry|FeigenbaumKMSZ-08|Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. ''Graph distances in the data-stream model.'' SIAM J. Comput., 38(5):1709-1727, 2008.}} | {{bibentry|FeigenbaumKMSZ-08|Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. ''Graph distances in the data-stream model.'' SIAM J. Comput., 38(5):1709-1727, 2008.}} | ||
− | {{bibentry|FeigenbaumKSV-02|Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan. ''An approximate $L^1$ difference algorithm for massive data streams.'' ''Journal on Computing'', 32(1) | + | {{bibentry|FeigenbaumKSV-02|Joan Feigenbaum, Sampath Kannan, Martin Strauss, and Mahesh Viswanathan. ''An approximate $L^1$ difference algorithm for massive data streams.'' ''Journal on Computing'', 32(1), pages 131-151, 2002.}} |
{{bibentry|FeldmanMSSS-06|Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, and Zoya Svitkina. ''On the complexity of processing massive, unordered, distributed data.'' 2006.}} | {{bibentry|FeldmanMSSS-06|Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Cliff Stein, and Zoya Svitkina. ''On the complexity of processing massive, unordered, distributed data.'' 2006.}} | ||
{{bibentry|FeldmanMSSS-10|Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Clifford Stein, and Zoya Svitkina. ''On distributing symmetric streaming computations.'' ACM Transactions on Algorithms, 6(4), 2010.}} | {{bibentry|FeldmanMSSS-10|Jon Feldman, S. Muthukrishnan, Anastasios Sidiropoulos, Clifford Stein, and Zoya Svitkina. ''On distributing symmetric streaming computations.'' ACM Transactions on Algorithms, 6(4), 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.}} | {{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 252: | Line 177: | ||
{{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, Dana Ron. ''Property Testing in Bounded Degree Graphs.'' Algorithmica, 32(2):302-343, 2002}} | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | {{bibentry|GoldreichR-02|Oded Goldreich | ||
− | |||
− | |||
{{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.}} | ||
− | |||
− | |||
{{bibentry|GopalanJKK-07|Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar. ''Estimating the sortedness of a data stream.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 318-327, 2007.}} | {{bibentry|GopalanJKK-07|Parikshit Gopalan, T. S. Jayram, Robert Krauthgamer, and Ravi Kumar. ''Estimating the sortedness of a data stream.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 318-327, 2007.}} | ||
Line 279: | Line 194: | ||
{{bibentry|GroheGLSTV-07|Martin Grohe, Yuri Gurevich, Dirk Leinders, Nicole Schweikardt, Jerzy Tyszkiewicz, and Jan Van den Bussche. ''Database query processing using finite cursor machines.'' In ''ICDT'', pages 284-298, 2007.}} | {{bibentry|GroheGLSTV-07|Martin Grohe, Yuri Gurevich, Dirk Leinders, Nicole Schweikardt, Jerzy Tyszkiewicz, and Jan Van den Bussche. ''Database query processing using finite cursor machines.'' In ''ICDT'', pages 284-298, 2007.}} | ||
− | |||
− | |||
{{bibentry|GuE-96|M. Gu and S.C. Eisenstat. ''Efficient algorithms for computing a strong rank-revealing QR factorization.'' SIAM Journal on Scientific Computing, 17, pages 848-869, 1996.}} | {{bibentry|GuE-96|M. Gu and S.C. Eisenstat. ''Efficient algorithms for computing a strong rank-revealing QR factorization.'' SIAM Journal on Scientific Computing, 17, pages 848-869, 1996.}} | ||
Line 299: | Line 212: | ||
{{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|HarveyNO-08|Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak. ''Sketching and streaming entropy via approximation theory.'' In ''IEEE Symposium on Foundations of Computer Science'', pages 489-498, 2008.}} | {{bibentry|HarveyNO-08|Nicholas J. A. Harvey, Jelani Nelson, and Krzysztof Onak. ''Sketching and streaming entropy via approximation theory.'' In ''IEEE Symposium on Foundations of Computer Science'', pages 489-498, 2008.}} | ||
Line 331: | Line 240: | ||
{{bibentry|JainN-10|Rahul Jain and Ashwin Nayak. ''The space complexity of recognizing well-parenthesized expressions.'' Electronic Colloquium on Computational Complexity (ECCC), 17:71, 2010.}} | {{bibentry|JainN-10|Rahul Jain and Ashwin Nayak. ''The space complexity of recognizing well-parenthesized expressions.'' Electronic Colloquium on Computational Complexity (ECCC), 17:71, 2010.}} | ||
− | |||
− | |||
{{bibentry|JayramKS-07|T. S. Jayram, Ravi Kumar, and D. Sivakumar. ''Simple lower bound on one-way Gap-Hamming.'' In http://www.cse.iitk.ac.in/users/sganguly/slides/ravikumar.pdf, 2007.}} | {{bibentry|JayramKS-07|T. S. Jayram, Ravi Kumar, and D. Sivakumar. ''Simple lower bound on one-way Gap-Hamming.'' In http://www.cse.iitk.ac.in/users/sganguly/slides/ravikumar.pdf, 2007.}} | ||
Line 345: | Line 252: | ||
{{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|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.}} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{{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|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.}} | ||
− | |||
− | |||
{{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 269: | ||
{{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|LeviR-13|Reut Levi and Dana Ron. ''A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor.'' In ''CoRR'', abs/1302.3417, 2013.}} | {{bibentry|LeviR-13|Reut Levi and Dana Ron. ''A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor.'' In ''CoRR'', abs/1302.3417, 2013.}} | ||
Line 389: | Line 278: | ||
{{bibentry|LibenNowellVZ-06|David Liben-Nowell, Erik Vee, and An Zhu. ''Finding longest increasing and common subsequences in streaming data.'' J. Comb. Optim., 11(2):155-175, 2006.}} | {{bibentry|LibenNowellVZ-06|David Liben-Nowell, Erik Vee, and An Zhu. ''Finding longest increasing and common subsequences in streaming data.'' J. Comb. Optim., 11(2):155-175, 2006.}} | ||
− | |||
− | |||
{{bibentry|MagniezMN-10|Frédéric Magniez, Claire Mathieu, and Ashwin Nayak. ''Recognizing well-parenthesized expressions in the streaming model.'' In ''ACM Symposium on Theory of Computing'', pages 261-270, 2010.}} | {{bibentry|MagniezMN-10|Frédéric Magniez, Claire Mathieu, and Ashwin Nayak. ''Recognizing well-parenthesized expressions in the streaming model.'' In ''ACM Symposium on Theory of Computing'', pages 261-270, 2010.}} | ||
Line 412: | Line 299: | ||
{{bibentry|MicaliV-80|Silvio Micali and Vijay V. Vazirani. ''An ${O}(\sqrt{V}{E})$ algorithm for finding maximum matching in general graphs.'' In ''FOCS'', pages 17-27, 1980.}} | {{bibentry|MicaliV-80|Silvio Micali and Vijay V. Vazirani. ''An ${O}(\sqrt{V}{E})$ algorithm for finding maximum matching in general graphs.'' In ''FOCS'', pages 17-27, 1980.}} | ||
− | {{bibentry|MisraG-82|Jayadev Misra and David Gries. ''Finding repeated elements.'' ''Sci. Comput. Program.'', 2(2) | + | {{bibentry|MisraG-82|Jayadev Misra and David Gries. ''Finding repeated elements.'' ''Sci. Comput. Program.'', 2(2), pages143-152, 1982.}} |
{{bibentry|MitzenmacherV-08|Michael Mitzenmacher and Salil P. Vadhan. ''Why simple hash functions work: exploiting the entropy in a data stream.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 746-755, 2008.}} | {{bibentry|MitzenmacherV-08|Michael Mitzenmacher and Salil P. Vadhan. ''Why simple hash functions work: exploiting the entropy in a data stream.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 746-755, 2008.}} | ||
− | |||
− | |||
{{bibentry|MunroP-80|J. Ian Munro and Mike Paterson. ''Selection and sorting with limited storage.'' Theor. Comput. Sci., 12:315-323, 1980.}} | {{bibentry|MunroP-80|J. Ian Munro and Mike Paterson. ''Selection and sorting with limited storage.'' Theor. Comput. Sci., 12:315-323, 1980.}} | ||
Line 423: | Line 308: | ||
{{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 315: | ||
{{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|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 330: | ||
{{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|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.}} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |