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.}} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{{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|AndoniIK-09|Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. ''Overcoming the $\ell_1$ non-embeddability barrier: algorithms for product metrics.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 865-874, 2009.}} | {{bibentry|AndoniIK-09|Alexandr Andoni, Piotr Indyk, and Robert Krauthgamer. ''Overcoming the $\ell_1$ non-embeddability barrier: algorithms for product metrics.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 865-874, 2009.}} | ||
Line 38: | Line 11: | ||
{{bibentry|AndoniJP-10|Alexandr Andoni, T. S. Jayram, and Mihai Patrascu. ''Lower bounds for edit distance and product metrics via Poincaré-type inequalities.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 184-192, 2010.}} | {{bibentry|AndoniJP-10|Alexandr Andoni, T. S. Jayram, and Mihai Patrascu. ''Lower bounds for edit distance and product metrics via Poincaré-type inequalities.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 184-192, 2010.}} | ||
− | + | {{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|AndoniN-12|Alexandr Andoni | ||
{{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|BarYossefJKS-04|Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. ''An information statistics approach to data stream and communication complexity.'' J. Comput. Syst. Sci., 68(4):702-732, 2004.}} | {{bibentry|BarYossefJKS-04|Ziv Bar-Yossef, T. S. Jayram, Ravi Kumar, and D. Sivakumar. ''An information statistics approach to data stream and communication complexity.'' J. Comput. Syst. Sci., 68(4):702-732, 2004.}} | ||
Line 59: | Line 22: | ||
{{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 30: | ||
{{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 37: | ||
{{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, 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, | ||
− | |||
− | |||
{{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|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|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 60: | ||
{{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|ChakrabartiR-11|Amit Chakrabarti and Oded Regev. ''An optimal lower bound on the communication complexity of Gap-Hamming-Distance.'' In ''ACM Symposium on Theory of Computing'', pages 51-60, 2011.}} | {{bibentry|ChakrabartiR-11|Amit Chakrabarti and Oded Regev. ''An optimal lower bound on the communication complexity of Gap-Hamming-Distance.'' In ''ACM Symposium on Theory of Computing'', pages 51-60, 2011.}} | ||
{{bibentry|ChakrabartiSWY-01|Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew C. Yao. ''Informational complexity and the direct sum problem for simultaneous message complexity.'' In ''IEEE Symposium on Foundations of Computer Science'', pages 270-278, 2001.}} | {{bibentry|ChakrabartiSWY-01|Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, and Andrew C. Yao. ''Informational complexity and the direct sum problem for simultaneous message complexity.'' In ''IEEE Symposium on Foundations of Computer Science'', pages 270-278, 2001.}} | ||
− | |||
− | |||
− | |||
− | |||
{{bibentry|ChanC-07|Timothy M. Chan and Eric Y. Chen. ''Multi-pass geometric algorithms.'' Discrete & Computational Geometry, 37(1):79-102, 2007.}} | {{bibentry|ChanC-07|Timothy M. Chan and Eric Y. Chen. ''Multi-pass geometric algorithms.'' Discrete & Computational Geometry, 37(1):79-102, 2007.}} | ||
Line 144: | Line 69: | ||
{{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|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.}} | ||
{{bibentry|CormodeM-06|Graham Cormode and S. Muthukrishnan. ''Combinatorial algorithms for compressed sensing.''In Paola Flocchini and Leszek Gasieniec, editors, ''Structural Information and Communication Complexity, 13th International Colloquium, SIROCCO 2006, Chester, UK, July 2-5, 2006, Proceedings'', volume 4056 of ''Lecture Notes in Computer Science'', pages 280-294. Springer, 2006.}} | {{bibentry|CormodeM-06|Graham Cormode and S. Muthukrishnan. ''Combinatorial algorithms for compressed sensing.''In Paola Flocchini and Leszek Gasieniec, editors, ''Structural Information and Communication Complexity, 13th International Colloquium, SIROCCO 2006, Chester, UK, July 2-5, 2006, Proceedings'', volume 4056 of ''Lecture Notes in Computer Science'', pages 280-294. Springer, 2006.}} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{{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 92: | ||
{{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 205: | Line 102: | ||
{{bibentry|DrineasMM-06b|Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. ''Subspace sampling and relative-error matrix approximation: Column-row-based methods.'' In ''ESA'', pages 304-314, 2006.}} | {{bibentry|DrineasMM-06b|Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. ''Subspace sampling and relative-error matrix approximation: Column-row-based methods.'' In ''ESA'', pages 304-314, 2006.}} | ||
− | |||
− | |||
− | |||
− | |||
{{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 215: | Line 108: | ||
{{bibentry|ElkinZ-06|Michael Elkin and Jian Zhang. ''Efficient algorithms for constructing $(1+\epsilon, \beta)$-spanners in the distributed and streaming models.'' Distributed Computing, 18(5):375-385, 2006.}} | {{bibentry|ElkinZ-06|Michael Elkin and Jian Zhang. ''Efficient algorithms for constructing $(1+\epsilon, \beta)$-spanners in the distributed and streaming models.'' Distributed Computing, 18(5):375-385, 2006.}} | ||
− | |||
− | |||
{{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 117: | ||
{{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 251: | Line 134: | ||
{{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|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 150: | ||
{{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 295: | Line 164: | ||
{{bibentry|GuhaMV-06|Sudipto Guha, Andrew McGregor, and Suresh Venkatasubramanian. ''Streaming and sublinear approximation of entropy and information distances.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 733-742, 2006.}} | {{bibentry|GuhaMV-06|Sudipto Guha, Andrew McGregor, and Suresh Venkatasubramanian. ''Streaming and sublinear approximation of entropy and information distances.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 733-742, 2006.}} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
{{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 317: | Line 178: | ||
{{bibentry|Indyk-04| Piotr Indyk. ''Algorithms for dynamic geometric problems over data streams.'' In ''ACM Symposium on Theory of Computing'', pages 373-380, 2004.}} | {{bibentry|Indyk-04| Piotr Indyk. ''Algorithms for dynamic geometric problems over data streams.'' In ''ACM Symposium on Theory of Computing'', pages 373-380, 2004.}} | ||
− | |||
− | |||
{{bibentry|IndykR-08|Piotr Indyk and Milan Ruzic. ''Near-optimal sparse recovery in the $\ell_1$ norm.'' In ''IEEE Symposium on Foundations of Computer Science'', pages 199-207, 2008.}} | {{bibentry|IndykR-08|Piotr Indyk and Milan Ruzic. ''Near-optimal sparse recovery in the $\ell_1$ norm.'' In ''IEEE Symposium on Foundations of Computer Science'', pages 199-207, 2008.}} | ||
− | |||
− | |||
{{bibentry|IndykT-03|Piotr Indyk and Niten Thaper. ''Fast color image retrieval via embeddings.'' Workshop on Statistical and Computational Theories of Vision (at ICCV), 2003.}} | {{bibentry|IndykT-03|Piotr Indyk and Niten Thaper. ''Fast color image retrieval via embeddings.'' Workshop on Statistical and Computational Theories of Vision (at ICCV), 2003.}} | ||
Line 331: | Line 188: | ||
{{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 339: | Line 194: | ||
{{bibentry|JhaR-11|Madhav Jha and Sofya Raskhodnikova. ''Testing and reconstruction of Lipschitz functions with applications to data privacy.'' Electronic Colloquium on Computational Complexity (ECCC), 18:57, 2011.}} | {{bibentry|JhaR-11|Madhav Jha and Sofya Raskhodnikova. ''Testing and reconstruction of Lipschitz functions with applications to data privacy.'' Electronic Colloquium on Computational Complexity (ECCC), 18:57, 2011.}} | ||
− | |||
− | |||
{{bibentry|JowhariG-05|Hossein Jowhari and Mohammad Ghodsi. ''New streaming algorithms for counting triangles in graphs.'' In ''COCOON'', pages 710-716, 2005.}} | {{bibentry|JowhariG-05|Hossein Jowhari and Mohammad Ghodsi. ''New streaming algorithms for counting triangles in graphs.'' In ''COCOON'', pages 710-716, 2005.}} | ||
{{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|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|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|Li-06|Ping Li. ''Very sparse stable random projections, estimators and tail bounds for stable random projections.''}} | {{bibentry|Li-06|Ping Li. ''Very sparse stable random projections, estimators and tail bounds for stable random projections.''}} | ||
Line 389: | Line 208: | ||
{{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.}} | ||
{{bibentry|MahoneyMD-06|Michael W. Mahoney, Mauro Maggioni, and Petros Drineas. ''Tensor-cur decompositions for tensor-based data.'' In ''ACM SIGKDD international conference on knowledge discovery and data mining'', pages 327-336, 2006.}} | {{bibentry|MahoneyMD-06|Michael W. Mahoney, Mauro Maggioni, and Petros Drineas. ''Tensor-cur decompositions for tensor-based data.'' In ''ACM SIGKDD international conference on knowledge discovery and data mining'', pages 327-336, 2006.}} | ||
− | |||
− | |||
{{bibentry|MankuRL-98|Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay. ''Approximate medians and other quantiles in one pass and with limited memory.'' In ''ACM SIGMOD International Conference on Management of Data'', pages 426-435, 1998.}} | {{bibentry|MankuRL-98|Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay. ''Approximate medians and other quantiles in one pass and with limited memory.'' In ''ACM SIGMOD International Conference on Management of Data'', pages 426-435, 1998.}} | ||
Line 405: | Line 220: | ||
{{bibentry|McGregor-05|Andrew McGregor. ''Finding graph matchings in data streams.'' In ''APPROX-RANDOM'', pages 170-181, 2005.}} | {{bibentry|McGregor-05|Andrew McGregor. ''Finding graph matchings in data streams.'' In ''APPROX-RANDOM'', pages 170-181, 2005.}} | ||
− | |||
− | |||
{{bibentry|MetwallyAA-05|Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. ''Efficient computation of frequent and top-k elements in data streams.'' In ''ICDT'', pages 398-412, 2005.}} | {{bibentry|MetwallyAA-05|Ahmed Metwally, Divyakant Agrawal, and Amr El Abbadi. ''Efficient computation of frequent and top-k elements in data streams.'' In ''ICDT'', pages 398-412, 2005.}} | ||
Line 412: | Line 225: | ||
{{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 234: | ||
{{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 241: | ||
{{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.}} | ||
− | |||
− | |||
{{bibentry|SeshadhriV-11|C. Seshadhri and Jan Vondrák. ''Is submodularity testable?'' In ''ICS'', 2011.}} | {{bibentry|SeshadhriV-11|C. Seshadhri and Jan Vondrák. ''Is submodularity testable?'' In ''ICS'', 2011.}} | ||
Line 459: | Line 254: | ||
{{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.}} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |