Bibliography - Revision history

Krzysztof Onak: Adding a new citation.

2023-03-13T02:01:32Z

Adding a new citation.

71.226.226.13 at 20:56, 11 July 2022

2022-07-11T20:56:14Z

71.226.226.13 at 20:55, 11 July 2022

2022-07-11T20:55:17Z

71.226.226.13 at 20:53, 11 July 2022

2022-07-11T20:53:36Z

SVelusamy at 05:16, 27 June 2022

2022-06-27T05:16:44Z

SVelusamy at 05:15, 27 June 2022

2022-06-27T05:15:46Z

SVelusamy at 05:06, 27 June 2022

2022-06-27T05:06:06Z

SVelusamy at 05:00, 27 June 2022

2022-06-27T05:00:32Z

SVelusamy at 03:41, 27 June 2022

2022-06-27T03:41:17Z

98.110.124.189 at 16:27, 16 June 2022

2022-06-16T16:27:25Z

← Older revision		Revision as of 02:01, 13 March 2023
Line 429:		Line 429:

	{{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\|NarayananT-22\|Shyam Narayanan and Jakub Tětek. ''Estimating the effective support size in constant query complexity.'' In ''CoRR,'' abs/2211.11344, 2022.}}

	{{bibentry\|NewmanR-13\|Ilan Newman and Yuri Rabinovich. ''On Multiplicative $\lambda$-Approximations and Some Geometric Applications.'' SIAM J. Comput. 42(3):855-883, 2013.}}		{{bibentry\|NewmanR-13\|Ilan Newman and Yuri Rabinovich. ''On Multiplicative $\lambda$-Approximations and Some Geometric Applications.'' SIAM J. Comput. 42(3):855-883, 2013.}}

@@ Line 458: / Line 458: @@
 {{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|Sudan-22|Madhu Sudan. ''Streaming and Sketching Complexity of CSPs: A survey.'' In "49th International Colloquium on Automata, Languages, and Programming (ICALP)", 2022.}}
+{{bibentry|Sudan-22|Madhu Sudan. ''Streaming and Sketching Complexity of CSPs: A survey.'' In ''ICALP'', 2022.}}
 {{bibentry|Thaler-16|Justin Thaler. ''Semi-Streaming Algorithms for Annotated Graph Streams.'' In ''ICALP'', 2016.}}

@@ Line 458: / Line 458: @@
 {{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|Sudan-22|Madhu Sudan. ''Streaming and Sketching Complexity of CSPs: A survey.'' 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Dagstuhl, Germany, 2022.}}
+{{bibentry|Sudan-22|Madhu Sudan. ''Streaming and Sketching Complexity of CSPs: A survey.'' In "49th International Colloquium on Automata, Languages, and Programming (ICALP)", 2022.}}
 {{bibentry|Thaler-16|Justin Thaler. ''Semi-Streaming Algorithms for Annotated Graph Streams.'' In ''ICALP'', 2016.}}

← Older revision		Revision as of 20:53, 11 July 2022
Line 457:		Line 457:

	{{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\|Sudan-22\|Madhu Sudan. ''Streaming and Sketching Complexity of CSPs: A survey.'' 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Dagstuhl, Germany, 2022.}}

	{{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 156: / Line 156: @@
 {{bibentry|ChouGV-20|Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy. ''Optimal streaming approximations for all Boolean Max-2CSPs and Max-kSAT.'' In ''FOCS'', pages 330-341, 2020.}}
-{{bibentry|ChouGSV-21|Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. ''Approximability of all Boolean CSPs with linear sketches.'', 2021.}}
+{{bibentry|ChouGSV-21|Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. ''Approximability of all Boolean CSPs with linear sketches.'' 2021.}}
 {{bibentry|ChouGSV-21a|Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. ''Approximability of all finite CSPs with linear sketches.'' In ''FOCS'', pages 1197-1208, 2021.}}

← Older revision		Revision as of 05:15, 27 June 2022
Line 155:		Line 155:

	{{bibentry\|ChouGV-20\|Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy. ''Optimal streaming approximations for all Boolean Max-2CSPs and Max-kSAT.'' In ''FOCS'', pages 330-341, 2020.}}		{{bibentry\|ChouGV-20\|Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy. ''Optimal streaming approximations for all Boolean Max-2CSPs and Max-kSAT.'' In ''FOCS'', pages 330-341, 2020.}}
		+
		+	{{bibentry\|ChouGSV-21\|Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. ''Approximability of all Boolean CSPs with linear sketches.'', 2021.}}
		+
		+	{{bibentry\|ChouGSV-21a\|Chi-Ning Chou, Alexander Golovnev, Madhu Sudan, and Santhoshini Velusamy. ''Approximability of all finite CSPs with linear sketches.'' In ''FOCS'', pages 1197-1208, 2021.}}

	{{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.}}

← Older revision		Revision as of 05:06, 27 June 2022
Line 153:		Line 153:

	{{bibentry\|ChitnisCEHMMV-16\|Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova. ''Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams.'' In ''SODA'', pages 1326-1344, 2016.}}		{{bibentry\|ChitnisCEHMMV-16\|Rajesh Chitnis, Graham Cormode, Hossein Esfandiari, MohammadTaghi Hajiaghayi, Andrew McGregor, Morteza Monemizadeh, and Sofya Vorotnikova. ''Kernelization via Sampling with Applications to Finding Matchings and Related Problems in Dynamic Graph Streams.'' In ''SODA'', pages 1326-1344, 2016.}}
		+
		+	{{bibentry\|ChouGV-20\|Chi-Ning Chou, Alexander Golovnev, and Santhoshini Velusamy. ''Optimal streaming approximations for all Boolean Max-2CSPs and Max-kSAT.'' In ''FOCS'', pages 330-341, 2020.}}

	{{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.}}

← Older revision		Revision as of 05:00, 27 June 2022
Line 293:		Line 293:

	{{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\|GuruswamiVV-17\|Venkatesan Guruswami, Ameya Velingker, and Santhoshini Velusamy. ''Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subgraph.'' In ''Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM)'', 2017.}}

	{{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.}}

← Older revision		Revision as of 03:41, 27 June 2022
Line 349:		Line 349:

	{{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\|KapralovK-19\|Michael Kapralov and Dmitry Krachun. ''An optimal space lower bound for approximating MAX-CUT.'' In ''STOC'', pages 277-288, 2019.}}

	{{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.}}

← Older revision		Revision as of 16:27, 16 June 2022
Line 459:		Line 459:

	{{bibentry\|YoshidaYI-09\|Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. ''An improved constant-time approximation algorithm for maximum matchings.'' In ''ACM Symposium on Theory of Computing'', pages 225-234, 2009.}}		{{bibentry\|YoshidaYI-09\|Yuichi Yoshida, Masaki Yamamoto, and Hiro Ito. ''An improved constant-time approximation algorithm for maximum matchings.'' In ''ACM Symposium on Theory of Computing'', pages 225-234, 2009.}}
		+
		+	{{bibentry\|Yu-21\|Huacheng Yu. ''Tight distributed sketching lower bound for connectivity.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', 2021.}}

	{{bibentry\|MannorT-04\|Shie Mannor and John N. Tsitsiklis. ''The Sample Complexity of Exploration in the Multi-Armed Bandit Problem.'' J. Mach. Learn. Res., 2004.}}		{{bibentry\|MannorT-04\|Shie Mannor and John N. Tsitsiklis. ''The Sample Complexity of Exploration in the Multi-Armed Bandit Problem.'' J. Mach. Learn. Res., 2004.}}