Open Problems in Sublinear Algorithms - User contributions [en]

News

2025-07-14T18:36:34Z

Krzysztof Onak: Updating the news

'''Jul 14, 2025:''' Announcement about recent problems with spam:
* We had to roll the wiki back to an older version to delete thousands of spam edits. We believe that no important edits in recent months have been lost, but if you posted an update recently, please check if it is still there.
* If you recently created an account, it was most likely deleted in the process, so you may have to register again.
* From now on, registration is required to edit the wiki and the question to register was updated to something that should be more difficult for modern LLMs (but hopefully it won't be a problem for legit users).

'''Aug 28, 2019:''' Open problems from two workshops have been posted: [[Workshops:Warwick_2018|the 2018 Workshop on Data Summarization at the University of Warwick]] and [[Workshops:WOLA_2019|the 3rd Workshop on Local Algorithms at ETH Zurich]].

'''Jun 13, 2019:''' The webpage has been updated to the 1.31 branch of MediaWiki. Please email us at [mailto:admin@sublinear.info admin@sublinear.info] if you notice any problems.

'''Nov 08, 2017:''' [[Workshops:FOCS_2017|A list of open problems]] from [http://www.cs.columbia.edu/~ccanonne/workshop-focs2017/ Frontiers in Distribution Testing], a workshop at FOCS 2017, has been posted.

'''Apr 28, 2017:''' [[Workshops:Banff_2017|A list of open problems]] from a BIRS workshop on communication complexity has been posted.

'''Jan 19, 2017:''' We made the switch to HTTPS for more security. Please let us know at [mailto:admin@sublinear.info admin@sublinear.info] if something stops to work. Consider also updating your password.

'''Dec 13, 2016:''' The webpage has been updated to the 1.27 branch of MediaWiki. Please email us at [mailto:admin@sublinear.info admin@sublinear.info] if you notice any problems.

'''May 26, 2016:''' The webpage has been updated and math rendering should work correctly again. Please email us at [mailto:admin@sublinear.info admin@sublinear.info] if you notice any problems.

'''May 21, 2016:''' The latest security update of MediaWiki unfortunately broke the extension responsible for rendering math equations. We turned it off for now. Versions of the problems with correctly rendered math can be enjoyed in the [https://{{SERVERNAME}}/sublinear_info.pdf pdf form].

'''Jan 18, 2016:''' [[Workshops:Baltimore_2016|Open problems]] from the Sublinear Algorithms Workshop at the Johns Hopkins University have been posted.

'''May 09, 2015:''' The entire list is now available as a [https://{{SERVERNAME}}/sublinear_info.pdf single pdf]. Checking the online version is still recommended. The pdf may become outdated and we can't promise prompt updates.

'''May 07, 2015:''' The wiki has just been updated to MediaWiki 1.23, the current long term support release. Please notify us at [mailto:admin@sublinear.info admin@sublinear.info] if anything stops working.

'''Jun 13, 2014:''' [[Workshops:Bertinoro_2014|Open problems]] from the 2014 Bertinoro Workshop on Sublinear Algorithms have been posted.

'''Sep 21, 2013:''' Eric Blais, Sourav Chakraborty, and C. Seshadhri have started [http://ptreview.sublinear.info/ ''Property Testing Review''], a blog dedicated to new developments in property testing and sublinear-time algorithms.

'''May 20, 2013:''' Recently submitted updates:
* {{ProblemLink|50}}

'''Mar 29, 2013:''' Recently submitted updates:
* {{ProblemLink|31}} (resolved)
* {{ProblemLink|38}}
* {{ProblemLink|40}} (resolved)

'''Feb 10, 2013:''' A simple anti-spam solution has been installed. Email confirmation is no longer required to edit the wiki, but we suggest that you still log in if you don't want your IP address to be displayed in the edit history.

'''Dec 12, 2012:''' The wiki is now officially open to celebrate 12/12/12!

'''Nov 10, 2012:''' Email confirmation is now required to prevent spammers.

'''Oct 01, 2012:''' This website will contain a list of open problems. There will be an official opening soon! Stay tuned!

Main Page

2025-07-14T18:36:10Z

Krzysztof Onak: Update on spam for the news

{{DISPLAYTITLE:List of Open Problems in Sublinear Algorithms}}
== About ==

The goal of this wiki is to collate a set of open problems in sub-linear algorithms and to track progress that is made on these problems. Important topics within sub-linear algorithms include data stream algorithms (sub-linear space), property testing (sub-linear time), and communication complexity (sub-linear communication) but this list isn't exhaustive. Indeed many of the early problems were posted at related workshops. We invite you to add further questions and update the wiki when progress is made on existing questions.

== News ==
'''Jul 14, 2025:''' Announcement about recent problems with spam:
* We had to roll the wiki back to an older version to delete thousands of spam edits. We believe that no important edits in recent months have been lost, but if you posted an update recently, please check if it is still there.
* If you recently created an account, it was most likely deleted in the process, so you may have to register again.
* From now on, registration is required to edit the wiki and the question to register was updated to something that should be more difficult for modern LLMs (but hopefully it won't be a problem for legit users).

'''Aug 28, 2019:''' Open problems from two workshops have been posted: [[Workshops:Warwick_2018|the 2018 Workshop on Data Summarization at the University of Warwick]] and [[Workshops:WOLA_2019|the 3rd Workshop on Local Algorithms at ETH Zurich]].

'''Jun 13, 2019:''' The webpage has been updated to the 1.31 branch of MediaWiki. Please email us at [mailto:admin@sublinear.info admin@sublinear.info] if you notice any problems.

[[News|Old news…]]

== Content ==
*[[Open_Problems:By_Number|Ordered list of open problems]]
*[https://{{SERVERNAME}}/sublinear_info.pdf The entire list compiled into a single pdf] (May be out of date. Save trees! Don't print unless you really have to.)
*[[Workshops|Workshops where open problems were suggested]]
*[[Resources|Resources on sublinear algorithms]]

== Random (Unsolved) Problem ==
*{{RandomUnsolved}}

== Citing and Editing ==
*[[Citing|Citing open problems]]
*[[Editing]]
*[[Waiting|Submiting a new problem]]
*[[TODO|Improvement suggestions]]

== Contact information ==
*Please send questions and comments to [mailto:admin@sublinear.info admin@sublinear.info].
__NOTOC__

Open Problems:100

2023-03-13T02:03:22Z

Krzysztof Onak: Fixing the citation. Please use the proper citation rules. See "Editing" on the main page.

{{Header
|source=wola19
|who=Oded Goldreich
}}
For a probability distribution $p$ over a discrete domain $\Omega$, and a parameter $\varepsilon\in[0,1]$, denote by
\[
\operatorname{ess}_\varepsilon(p) \stackrel{\rm def}{=} \min\{ \operatorname{supp}(q) : \operatorname{d}_{\rm TV}(p,q) \leq \varepsilon \}
\]
the $\varepsilon$-effective suport size of $p$, i.e., the smallest possible support size of any distribution $\varepsilon$-close to $p$. This turns out to be a more robust and interesting measure in general than the support of $p$, which is $\operatorname{ess}_0(p) = \operatorname{supp}(p)$. In recent work, Goldreich {{Cite|Goldreich-19b}} focused on the query complexity of approximating the effective support size of a discrete distribution provided via two oracles: sampling ($\textsf{samp}_p$), and query access (to the probability mass function), $\textsf{eval}_p$. In particular, the goal is, given parameters $\varepsilon$ and $\beta>1$, to output an $f(\varepsilon,\beta,n)$-factor approximation of $\operatorname{ess}_{\varepsilon'}(p)$, for some $\varepsilon' \in [\varepsilon,\beta\varepsilon]$.

In the aforementioned work, algorithms are obtained achieving (for constant $\beta>1$)

* query complexity $\operatorname{poly}(1/\varepsilon)$ and approximation factor $f = O(\log\log\log\log(n/\varepsilon))$, that is, any constant number of iterated logarithms;

* query complexity $\operatorname{poly}(\log^\ast n, 1/\varepsilon)$ even for approximation factor $f = O(1)$;

where $n \stackrel{\rm def}{=} \operatorname{ess}_\varepsilon(p)$. (As well as several other results interpolating between the two extremes.)

'''Question:''' Can one get the best of both worlds, and get rid of the $\log^\ast n$ to obtain query complexity $\operatorname{poly}(1/\varepsilon)$ ''and'' constant approximation factor?

== Update ==
This problem has been resolved in the positive direction by Narayanan and Tětek {{cite|NarayananT-22}}.

Bibliography

2023-03-13T02:01:32Z

Krzysztof Onak: Adding a new citation.

<p class="dontprint">'''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}}.</p>
<hr class="dontprint">

{{bibentry|AaronsonW-09|Scott Aaronson and Avi Wigderson. ''Algebrization: A New Barrier in Complexity Theory.'' ACM Transactions on Computation Theory, 1(1), 2009.}}

{{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|AcharyaDOS-17|Jayadev Acharya, Hirakendu Das, Alon Orlitsky, and Ananda Theertha Suresh. ''Estimating Symmetric Properties of Distributions: A Maximum Likelihood Approach .'' In ''ICML'', 2017.}}

{{bibentry|AcharyaOST-17|Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. ''Estimating Renyi Entropy of Discrete Distributions.'' In IEEE Transactions on Information Theory, vol. 63, no. 1, pages 38-56, 2017.}}

{{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-11|Kook Jin Ahn and Sudipto Guha. ''Laminar Families and Metric Embeddings: Non-bipartite Maximum Matching Problem in the Semi-Streaming Model.'' In ''CoRR,'' abs/1104.4058, 2011.}}

{{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.'' 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|Alon-02|Noga Alon. ''Testing subgraphs in large graphs.'' Random Struct. Algorithms, 21(3-4):359-370, 2002.}}

{{bibentry|AlonFNS-09|Noga Alon, Eldar Fischer, Ilan Newman, and Asaf Shapira. ''A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity.'' SIAM J. Comput. 39(1):143-167, 2009.}}

{{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|AndoniCKQWZ-16| Alexandr Andoni, Jiecao Chen, Robert Krauthgamer, Bo Qin, David P. Woodruff, and Qin Zhang. ''On Sketching Quadratic Forms.'' In ''ITCS'', pages 311-319, 2016.}}

{{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|AndoniGK-14|Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer. ''Towards $(1+\varepsilon)$-Approximate Flow Sparsifiers.'' In ''SODA'', pages 279-293, 2014.}}

{{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-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|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|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 and 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|AssadiKLY-16|Sepehr Assadi, Sanjeev Khanna, Yang Li, and Grigory Yaroslavtsev. ''Maximum Matchings in Dynamic Graph Streams and the Simultaneous Communication Model.'' In ''SODA'', pages 1345-1364, 2016.}}

{{bibentry|AssadiKL-17|Sepehr Assadi, Sanjeev Khanna, and Yang Li. ''On Estimating Maximum Matching Size in Graph Streams.'' In ''SODA'', pages 1723-1742, 2017.}}

{{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|BaraniukCDH-10|Richard G. Baraniuk, Volkan Cevher, Marco F. Duarte, and Chinmay Hegde. ''Model-based compressive sensing.'' IEEE Transactions on Information Theory, 56(4):1982-2001, 2010.}}

{{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|BarYossefJKST-02|Ziv Bar-Yossef, T.S. Jayram, Ravi Kumar, D. Sivakumar, and Luca Trevisan. ''Counting distinct elements in a data stream.'' In ''Proc. 6th International Workshop on Randomization and Approximation Techniques in Computer Science'', pages 1-10, 2002.}}

{{bibentry|BarYossefKS-02|Ziv Bar-Yossef, Ravi Kumar, and D. Sivakumar. ''Reductions in streaming algorithms, with an application to counting triangles in graphs.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 623-632, 2002.}}

{{bibentry|Baswana-06|Surender Baswana. ''Faster streaming algorithms for graph spanners.'' 2006.}}

{{bibentry|BatsonSS-14|Joshua D. Batson, Daniel A. Spielman, and Nikhil Srivastava. ''Twice-Ramanujan Sparsifiers.'' SIAM Review 56(2):315-334, 2014.}}

{{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|BenczurK-96|András A. Benczúr and David R. Karger. ''Approximating $s{-}t$ minimum cuts in $\tilde O(n^2)$ time.'' In ''ACM Symposium on Theory of Computing'', pages 47-55, 1996.}}

{{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|BenjaminiSS-08|Itai Benjamini, Oded Schramm, and Asaf Shapira. ''Every minor-closed property of sparse graphs is testable.'' In ''ACM Symposium on Theory of Computing'', pages 393-402, 2008.}}

{{bibentry|BenSassonGMSS-11|Eli Ben-Sasson, Elena Grigorescu, Ghid Maatouk, Amir Shpilka, and Madhu Sudan. ''On sums of locally testable affine invariant properties.'' Electronic Colloquium on Computational Complexity (ECCC), 18:79, 2011.}}

{{bibentry|BerindeIR-08|Radu Berinde, Piotr Indyk, and Milan Ruzic. ''Practical near-optimal sparse recovery in the $l_1$ norm.'' Allerton, 2008.}}

{{bibentry|BermanRY-14|Piotr Berman, Sofya Raskhodnikova, Grigory Yaroslavtsev. ''$L_p$-Testing.'' In ''ACM Symposium on Theory of Computing'', pages 164-173, 2014.}}

{{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|BhuvanagiriG-06|Lakshminath Bhuvanagiri and Sumit Ganguly. ''Estimating entropy over data streams.'' In ''ESA'', pages 148-159, 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|BlaisCG-17| Eric Blais, Clément L. Canonne, and Tom Gur. ''Distribution Testing Lower Bounds via Reductions from Communication Complexity''. In ''CCC'', 2017.}}

{{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|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|BoulandCHTV-16|Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan. ''On SZK and PP.'' CoRR abs/1609.02888, 2016.}}

{{bibentry|BravermanGPW-13|Mark Braverman, Ankit Garg, Denis Pankratov, and Omri Weinstein. ''Information lower bounds via self-reducibility.'' In ''CSR'', 2013.}}

{{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):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|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|BunNS-18|Mark Bun, Jelani Nelson, and Uri Stemmer. ''Heavy Hitters and the Structure of Local Privacy.'' In ''PODS'', pages 435-447, 2018.}}

{{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-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|Canonne-15|Clément L. Canonne. ''Big Data on the rise? Testing monotonicity of distributions.'' In ''ICALP'', 2015.}}

{{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|CarlsonKST-17|Charles Carlson, Alexandra Kolla, Nikhil Srivastava, and Luca Trevisan. ''Optimal Lower Bounds for Sketching Graph Cuts.'' In ''CoRR,'' abs/1712.10261, 2017.}}

{{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|ChakrabartiCKM-10|Amit Chakrabarti, Graham Cormode, Ranganath Kondapally, and Andrew McGregor. ''Information cost tradeoffs for augmented index and streaming language recognition.'' In ''IEEE Symposium on Foundations of Computer Science'', pages 387-396, 2010.}}

{{bibentry|ChakrabartiCM-07|Amit Chakrabarti, Graham Cormode, and Andrew McGregor. ''A near-optimal algorithm for computing the entropy of a stream.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 328-335, 2007.}}

{{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|ChakrabartiCMTV-15|Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. ''Verifiable Stream Computation and Arthur-Merlin Communication.'' In ''IEEE Conference on Computational Complexity'', pages 217-243, 2015.}}

{{bibentry|ChakrabartiK-14|Amit Chakrabarti and Sagar Kale. ''Submodular Maximization Meets Streaming: Matchings, Matroids, and More.'' In ''IPCO'', to appear, 2014.}}

{{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|ChakrabartyS-13|Deeparnab Chakrabarty and C. Seshadhri. ''Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids.'' In ''ACM Symposium on Theory of Computing'', 2013.}}

{{bibentry|ChakrabortyFGM-13|Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah. ''On the power of conditional samples in distribution testing.'' In ''ITCS'', pages 561-580, 2013.}}

{{bibentry|ChanC-07|Timothy M. Chan and Eric Y. Chen. ''Multi-pass geometric algorithms.'' Discrete & Computational Geometry, 37(1):79-102, 2007.}}

{{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):1370-1379, 2005.}}

{{bibentry|ChenKPSSY21|Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, Huacheng Yu. ''Near-Optimal Two-Pass Streaming Algorithm for Sampling Random Walks over Directed Graphs.'' ICALP 2021: 52:1-52:19.}}

{{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|ChiesaG-17|Alessandro Chiesa and Tom Gur. ''Proofs of Proximity for Distribution Testing.'' Electronic Colloquium on Computational Complexity (ECCC) 24:155, 2017.}}

{{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|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|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):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):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-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|CormodePSV-00|Graham Cormode, Mike Paterson, Suleyman Cenk Sahinalp, and Uzi Vishkin. ''Communication complexity of document exchange.'' In ''SODA'', 2000.}}

{{bibentry|CrouchM-11|Michael S. Crouch and Andrew McGregor. ''Periodicity and Cyclic Shifts via Linear Sketches.'' In ''APPROX'', 2011.}}

{{bibentry|CrouchS-14|Michael Crouch and Daniel Stubbs. In Andrew McGregor's presentation at the 2014 Bertinoro Workshop on Sublinear Algorithms.}}

{{bibentry|CzumajS-09|Artur Czumaj and Christian Sohler. ''Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time.'' In ''SIAM J. Comput.'', 39(3):904–922, 2009.}}

{{bibentry|DaskalakisDS-11|Constantinos Daskalakis, Ilias Diakonikolas, and Rocco A. Servedio. ''Learning transformed product distributions.'' CoRR, abs/1103.0598, 2011.}}

{{bibentry|DaskalakisKW-18|Constantinos Daskalakis, Gautam Kamath, and John Wright. ''Which Distribution Distances are Sublinearly Testable?'' In ''SODA'', 2018.}}

{{bibentry|DasSarmaGP-08|Atish Das Sarma, Sreenivas Gollapudi, and Rina Panigrahy. ''Estimating PageRank on graph streams.'' In ''PODS'', pages 69-78, 2008.}}

{{bibentry|DeanG-04|Jeffrey Dean and Sanjay Ghemawat. ''MapReduce: Simplified data processing on large clusters.'' In ''OSDI'', pages 137-150, 2004.}}

{{bibentry|DemaineLM-02|Erik D. Demaine, Alejandro López-Ortiz, and J. Ian Munro. ''Frequency estimation of internet packet streams with limited space.'' In ''ESA'', pages 348-360, 2002.}}

{{bibentry|DemetrescuFR-06|Camil Demetrescu, Irene Finocchi, and Andrea Ribichini. ''Trading off space for passes in graph streaming problems.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 714-723, 2006.}}

{{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|DoerrK-16|Benjamin Doerr, Marvin Kunnemann. ''Improved Protocols and Hardness Results for the Two-Player Cryptogenography Problem.'' In ''ICALP'', 2016.}}

{{bibentry|Donoho-06|David L. Donoho. ''Compressed sensing.'' IEEE Transactions on Information Theory, 52(4):1289-1306, 2006.}}

{{bibentry|DrakeH-03|Doratha E. Drake and Stefan Hougardy. ''Improved linear time approximation algorithms for weighted matchings.'' In ''RANDOM-APPROX'', pages 14-23, 2003.}}

{{bibentry|DrineasMM-06|Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. ''Sampling algorithms for $\ell_2$ regression and applications.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 1127-1136, 2006.}}

{{bibentry|DrineasMM-06a|Petros Drineas, Michael W. Mahoney, and S. Muthukrishnan. ''Subspace sampling and relative-error matrix approximation: Column-based methods.'' In ''APPROX-RANDOM'', pages 316-326, 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|Eddy-04|Sean R Eddy. ''How do RNA folding algorithms work?'' Nature Biotechnology, 22, pages 1457-1458, 2004.}}

{{bibentry|EdenJPRS-18|Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C. Seshadhri. ''Provable and practical approximations for the degree distribution using sublinear graph samples.'' In ''WWW'', pages 449–458. 2018.}}

{{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|Elkin-06|Michael Elkin. ''A near-optimal fully dynamic distributed algorithm for maintaining sparse spanners.'' 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|EpsteinLMS-11|Leah Epstein, Asaf Levin, Julian Mestre, and Danny Segev. ''Improved Approximation Guarantees for Weighted Matching in the Semi-streaming Model.'' SIAM J. Discrete Math. 25(3), 2011.}}

{{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|FalahatgarJOPS-15|Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapathi, and Ananda Theertha Suresh. ''Faster Algorithms for Testing under Conditional Sampling.'' In ''CoRR,'' abs/1504.04103, 2015.}}

{{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-05a|Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. ''On graph problems in a semi-streaming model.'' Theoretical Computer Science, 348(2-3):207-216, 2005.}}

{{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):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-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|FichtenbergerPS-15|Hendrik Fichtenberger, Pan Peng, and Christian Sohler. ''On constant-size graphs that preserve the local structure of high-girth graphs.'' In ''APPROX-RANDOM,'' pages 786-799, 2015.}}

{{bibentry|Forster-01|Jurgen Forster. ''A Linear Lower Bound on the Unbounded Error Probabilistic Communication Complexity.'' In ''IEEE Conference on Computational Complexity'', pages 100-106, 2001.}}

{{bibentry|ForsterY-19|Sebastian Forster and Liu Yang. ''A faster local algorithm for detecting bounded-size cuts with applications to higher-connectivity problems.'' In ''CoRR,'' abs/1904.08382, 2019.}}

{{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|Gabow-90|Harold N. Gabow. ''Data structures for weighted matching and nearest common ancestors with linking.'' In ''ACM-SIAM Symposium on Discrete Algorithms'', pages 434-443, 1990.}}

{{bibentry|GalG-07|Anna Gál and Parikshit Gopalan. ''Lower bounds on streaming algorithms for approximating the length of the longest increasing subsequence.'' In ''IEEE Symposium on Foundations of Computer Science'', pages 294-304, 2007.}}

{{bibentry|Ganguly-06|Sumit Ganguly and Anirban Majumder. ''CR-precis: A deterministic summary structure for update data streams.'' In ''ESCAPE'', 2007.}}

{{bibentry|GilbertKMS-02|Anna C. Gilbert, Yannis Kotidis, S. Muthukrishnan, and Martin Strauss. ''How to summarize the universe: Dynamic maintenance of quantiles.'' In ''Proc. 28th International Conference on Very Large Data Bases'', pages 454-465, 2002.}}

{{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|Goldreich-17|Oded Goldreich. ''Introduction to Property Testing.'' Cambridge University Press, November 2017.}}

{{bibentry|Goldreich-19a|Oded Goldreich. ''Testing graphs in vertex-distribution-free models.'' In ''STOC'', pages 527–534, 2019.}}

{{bibentry|Goldreich-19b|Oded Goldreich. ''On the complexity of estimating the effective support size.'' Electronic Colloquium on Computational Complexity (ECCC), 26:88, 2019.}}

{{bibentry|GoldreichR-02|Oded Goldreich and Dana Ron. ''Property Testing in Bounded Degree Graphs.'' Algorithmica, 32(2):302-343, 2002}}

{{bibentry|GoldreichGR-98|Oded Goldreich, Shafi Goldwasser, and Dana Ron. ''Property testing and its connection to learning and approximation.'' J. ACM, 45(4):653–750, 1998.}}

{{bibentry|GolubV-89|G.H. Golub and C.F. Van Loan. ''Matrix Computations.'' Johns Hopkins University Press, Baltimore, 1989.}}

{{bibentry|GomoryH-61|R. E. Gomory and T. C. Hu. ''Multi-terminal network flows.'' Journal of the Society for Industrial and Applied Mathematics, 9(4):551-570, 1961.}}

{{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|GoreinovT-01|S. A. Goreinov and E. E. Tyrtyshnikov. ''The maximum-volume concept in approximation by low-rank matrices.'' Contemporary Mathematics, 280, pages 47-51, 2001.}}

{{bibentry|GoreinovTZ-97|S. A. Goreinov, E. E. Tyrtyshnikov, and N. L. Zamarashkin. ''A theory of pseudoskeleton approximations.'' Linear Algebra and its Applications, 261, pages 1-21, August 1997.}}

{{bibentry|Gould-96|Stephen Jay Gould.''The Mismeasure of Man.'' W. W. Norton and Company, 1996.}}

{{bibentry|GreenwaldK-01|Michael Greenwald and Sanjeev Khanna. ''Space-efficient online computation of quantile summaries.'' In ''ACM SIGMOD International Conference on Management of Data'', pages 58-66, 2001.}}

{{bibentry|GrigorescuKS-08|Elena Grigorescu, Tali Kaufman, and Madhu Sudan. ''2-transitivity is insufficient for local testability.'' In ''IEEE Conference on Computational Complexity'', pages 259-267, 2008.}}

{{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|GuchtWWZ-15|Dirk Van Gucht, Ryan Williams, David P. Woodruff, and Qin Zhang. ''The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication.'' In ''PODS'', pages 199-212, 2015.}}

{{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|GuhaIM-07|Sudipto Guha, Piotr Indyk, and Andrew McGregor. ''Sketching information divergences.'' In ''Conference on Learning Theory'', 2007.}}

{{bibentry|GuhaM-06|Sudipto Guha and Andrew McGregor. ''Approximate quantiles and the order of the stream.'' In ''ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems'', pages 273-279, 2006.}}

{{bibentry|GuhaM-07|Sudipto Guha and Andrew McGregor. ''Lower bounds for quantile estimation in random-order and multi-pass streaming.'' Manuscript, 2007.}}

{{bibentry|GuhaM-07a|Sudipto Guha and Andrew McGregor. ''Space-efficient sampling.'' In ''AISTATS'', pages 169-176, 2007.}}

{{bibentry|GuhaM-08|Sudipto Guha and Andrew McGregor. ''Tight lower bounds for multi-pass stream computation via pass elimination.'' In ''International Colloquium on Automata, Languages and Programming'', pages 760-772, 2008.}}

{{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|GuruswamiO-13|Venkatesan Guruswami and Krzysztof Onak. ''Superlinear lower bounds for multipass graph processing.'' In ''IEEE Conference on Computational Complexity'', 2013.}}

{{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|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|HassidimKNO-09|Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, and Krzysztof Onak. ''Local graph partitions for approximation and testing.'' In ''IEEE Symposium on Foundations of Computer Science'', pages 22-31, 2009.}}

{{bibentry|HershbergerSST-04|John Hershberger, Nisheeth Shrivastava, Subhash Suri, and Csaba D. Tóth. ''Adaptive spatial partitioning for multidimensional data streams.'' In ''ISAAC'', pages 522-533, 2004.}}

{{bibentry|HoffmannMR-04|M. Hoffmann, S. Muthukrishnan, and R. Raman. ''Location streams: Models and algorithms.'' Technical Report 2004-28, DIMACS, May 2004.}}

{{bibentry|HopcroftK-73|John E. Hopcroft and Richard M. Karp. ''An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs.'' SIAM J. Comput., 2(4):225-231, 1973.}}

{{bibentry|Indyk-00| Piotr Indyk. ''Stable distributions, pseudorandom generators, embeddings and data stream computation.'' In ''IEEE Symposium on Foundations of Computer Science'', pages 189-197, 2000.}}

{{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|IndykP-11|Piotr Indyk and Eric Price. ''K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance.'' In ''ACM Symposium on Theory of Computing'', pages 627-636, 2011.}}

{{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-13|Piotr Indyk and Ilya Razenshteyn. ''On Model-Based RIP-1 Matrices.'' In ''International Colloquium on Automata, Languages and Programming (ICALP)'', pages 564-575, 2013.}}

{{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|IndykW-03|Piotr Indyk and David P. Woodruff. ''Tight lower bounds for the distinct elements problem.'' In ''IEEE Symposium on Foundations of Computer Science'', pages 283-288, 2003.}}

{{bibentry|IndykW-05|Piotr Indyk and David P. Woodruff. ''Optimal approximations of the frequency moments of data streams.'' In ''ACM Symposium on Theory of Computing'', pages 202-208, 2005.}}

{{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|Jakobsen-14|Sune Jakobsen. ''Information Theoretical Cryptogenography.'' In ''ITCS'', 2014.}}

{{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|JayramW-09|T. S. Jayram and David P. Woodruff. ''The data stream space complexity of cascaded norms.'' In ''IEEE Symposium on Foundations of Computer Science'', 2009.}}

{{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|Jowhari-12|Hossein Jowhari. ''Efficient Communication Protocols for Deciding Edit Distance.'' In ''ESA'', 2012.}}

{{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|KamathT-19|Gautam Kamath, Christos Tzamos. ''Anaconda: A Non-Adaptive Conditional Sampling Algorithm for Distribution Testing.'' In ''SODA'', 2019.}}

{{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|KannanMSY-18|Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev. ''Linear Sketching over $\mathbb{F}_2$.'' In CCC'18, https://eccc.weizmann.ac.il/report/2016/174/}}

{{bibentry|Kapralov-12|Michael Kapralov. ''Improved lower bounds for matchings in the streaming model.'' In ''CoRR'', abs/1206.2269, 2012.}}

{{bibentry|KapralovKS-15|Michael Kapralov, Sanjeev Khanna, and Madhu Sudan. ''Streaming Lower Bounds for Approximating MAX-CUT.'' In ''SODA'', pages 1263-1282, 2015.}}

{{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|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|KhanR-14|Arindam Khan and Prasad Raghavendra. ''On mimicking networks representing minimum terminal cuts.'' Inf. Process. Lett. (IPL) 114(7):365-371, 2014.}}

{{bibentry|KhotN-06|Subhash Khot and Assaf Naor. ''Nonembeddability theorems via Fourier analysis.'' Math. Ann., 334(4):821-852, 2006.}}

{{bibentry|KhotN-19|Subhash Khot and Assaf Naor. ''The Andoni–Krauthgamer–Razenshteyn characterization of sketchable norms fails for sketchable metrics.'' In ''SODA'', pages 1814-1824. 2019}}

{{bibentry|KoganK-15|Dmitry Kogan and Robert Krauthgamer. ''Sketching Cuts in Graphs and Hypergraphs.'' In ''ITCS'', pages 367-376, 2015.}}

{{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|KrahmerW-11|Felix Krahmer, Rachel Ward. ''New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property.'' SIAM J. Math. Anal., 43(3):1269-1281, 2011.}}

{{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|LarsenW-17|Kasper Green Larsen and Ryan Williams. ''Faster Online Matrix-Vector Multiplication.'' In ''SODA'', pages 2182-2189, 2017.}}

{{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|Li-06|Ping Li. ''Very sparse stable random projections, estimators and tail bounds for stable random projections.''}}

{{bibentry|LiHC-06|Ping Li, Trevor Hastie, and Kenneth Ward Church. ''Very sparse random projections.'' In ''KDD'', pages 287-296, 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|LibertySS-16|Edo Liberty, Ram Sriharsha, and Maxim Sviridenko. ''An Algorithm for Online K-Means Clustering.'' In ''ALENEX'', pages 81-89, 2016.}}

{{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|ManjunathMPS-11|Madhusudan Manjunath, Kurt Mehlhorn, Konstantinos Panagiotou, and He Sun. ''Approximate Counting of Cycles in Streams.'' In ''Proceedings of the 19th Annual European Symposium'', 2011.}}

{{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-99|Gurmeet Singh Manku, Sridhar Rajagopalan, and Bruce G. Lindsay. ''Random sampling techniques for space efficient online computation of order statistics of large datasets.'' In ''ACM SIGMOD International Conference on Management of Data'', pages 251-262, 1999.}}

{{bibentry|Matousek-02| Jiří Matoušek. ''Lectures on Discrete Geometry''. Springer, 2002.}}

{{bibentry|McGregor-05|Andrew McGregor. ''Finding graph matchings in data streams.'' In ''APPROX-RANDOM'', pages 170-181, 2005.}}

{{bibentry|McGregorRU-11|Andrew McGregor, Atri Rudra, and Steve Uurtamo. ''Polynomial Fitting of Data Streams with Applications to Codeword Testing.'' In ''Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science (STACS)'', 2011.}}

{{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|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):143-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|MontanaroO-09|Ashley Montanaro and Tobias Osborne. ''On the communication complexity of XOR functions.'' In ''CoRR,'' abs/0909.3392, 2009.}}

{{bibentry|MunroP-80|J. Ian Munro and Mike Paterson. ''Selection and sorting with limited storage.'' Theor. Comput. Sci., 12:315-323, 1980.}}

{{bibentry|Muthukrishnan-06|S. Muthukrishnan. ''Data streams: Algorithms and applications.'' Now Publishers, 2006.}}

{{bibentry|Muthukrishnan-06a|S. Muthukrishnan. ''Some algorithmic problems and results in compressed sensing.'' In ''Allerton Conference'', 2006.}}

{{bibentry|NanongkaiSY-19a|Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. ''Breaking quadratic time for small vertex connectivity and an approximation scheme.'' In ''STOC'', pages 241–252, 2019.}}

{{bibentry|NanongkaiSY-19b|Danupon Nanongkai, Thatchaphol Saranurak, and Sorrachai Yingchareonthawornchai. ''Computing and testing small vertex connectivity in near-linear time and queries.'' In ''CoRR,'' abs/1905.05329, 2019.}}

{{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|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|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|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|Paninski-08|Liam Paninski. ''A coincidence-based test for uniformity given very sparsely sampled discrete data.'' In ''IEEE Trans. Information Theory,'' 54(10):4750–4755, 2008.}}

{{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|Pogrow-17|Yosef Pogrow. ''Solving Symmetric Diagonally Dominant Linear Systems in Sublinear Time and Some Observations on Graph Sparsification.'' MSc thesis, Weizmann Institute of Science, 2017.}}

{{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|RudraU-10|Atri Rudra and Steve Uurtamo. ''Data Stream Algorithms for Codeword Testing.'' In ''Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP),'' 2010.}}

{{bibentry|SeshadhriV-11|C. Seshadhri and Jan Vondrák. ''Is submodularity testable?'' In ''ICS'', 2011.}}

{{bibentry|ShrivastavaBAS-04|Nisheeth Shrivastava, Chiranjeeb Buragohain, Divyakant Agrawal, and Subhash Suri. ''Medians and beyond: new aggregation techniques for sensor networks.'' In ''SenSys'', pages 239-249, 2004.}}

{{bibentry|Stewart-99|G.W. Stewart. ''Four algorithms for the efficient computation of truncated QR approximations to a sparse matrix.'' Numerische Mathematik, 83, pages 313-323, 1999.}}

{{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 ''ICALP'', 2022.}}

{{bibentry|Thaler-16|Justin Thaler. ''Semi-Streaming Algorithms for Annotated Graph Streams.'' In ''ICALP'', 2016.}}

{{bibentry|Trevisan-09|Luca Trevisan. ''Max Cut and the smallest eigenvalue.'' In ''ACM Symposium on Theory of Computing'', pages 263-272, 2009.}}

{{bibentry|ValiantV-11|Gregory Valiant and Paul Valiant. ''The Power of Linear Estimators''. In ''FOCS'', 2011.}}

{{bibentry|ValiantV-14|Gregory Valiant and Paul Valiant. ''An Automatic Inequality Prover and Instance Optimal Identity Testing''. In ''FOCS'', 2014.}}

{{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|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|AssadiW-20|Sepehr Assadi and Chen Wang. ''Exploration with Limited Memory: Streaming Algorithms for Coin Tossing, Noisy Comparisons, and Multi-Armed Bandits.'' In ''Annual ACM Symposium on Theory of Computing'', 2020.}}

{{bibentry|JinHTX-21|Tianyuan Jin, Keke Huang, Jing Tang, Xiaokui Xiao. ''Optimal Streaming Algorithms for Multi-Armed Bandits.'' In ''International Conference on Machine Learning'', 2021.}}

Main Page

2021-04-20T03:32:43Z

Krzysztof Onak: Removing an old broken link

{{DISPLAYTITLE:List of Open Problems in Sublinear Algorithms}}
== About ==

The goal of this wiki is to collate a set of open problems in sub-linear algorithms and to track progress that is made on these problems. Important topics within sub-linear algorithms include data stream algorithms (sub-linear space), property testing (sub-linear time), and communication complexity (sub-linear communication) but this list isn't exhaustive. Indeed many of the early problems were posted at related workshops. We invite you to add further questions and update the wiki when progress is made on existing questions.

== News ==
'''Aug 28, 2019:''' Open problems from two workshops have been posted: [[Workshops:Warwick_2018|the 2018 Workshop on Data Summarization at the University of Warwick]] and [[Workshops:WOLA_2019|the 3rd Workshop on Local Algorithms at ETH Zurich]].

'''Jun 13, 2019:''' The webpage has been updated to the 1.31 branch of MediaWiki. Please email us at [mailto:admin@sublinear.info admin@sublinear.info] if you notice any problems.

'''Nov 08, 2017:''' [[Workshops:FOCS_2017|A list of open problems]] from [http://www.cs.columbia.edu/~ccanonne/workshop-focs2017/ Frontiers in Distribution Testing], a workshop at FOCS 2017, has been posted.

[[News|Old news…]]

== Content ==
*[[Open_Problems:By_Number|Ordered list of open problems]]
*[https://{{SERVERNAME}}/sublinear_info.pdf The entire list compiled into a single pdf] (May be out of date. Save trees! Don't print unless you really have to.)
*[[Workshops|Workshops where open problems were suggested]]
*[[Resources|Resources on sublinear algorithms]]

== Random (Unsolved) Problem ==
*{{RandomUnsolved}}

== Citing and Editing ==
*[[Citing|Citing open problems]]
*[[Editing]]
*[[Waiting|Submiting a new problem]]
*[[TODO|Improvement suggestions]]

== Contact information ==
*Please send questions and comments to [mailto:admin@sublinear.info admin@sublinear.info].
__NOTOC__

Open Problems talk:65

2020-08-26T17:55:36Z

Krzysztof Onak: replying to the comment

Was solved July 2020:
https://arxiv.org/abs/2007.12323

'''Reply:''' Thanks for the heads up! Do you want to update the problem description? See “[[Open_Problems:23]]” for an example of how to do this. Also “[[Editing]]” has some technical info about editing.

News

2019-08-29T02:48:49Z

Krzysztof Onak:

'''Aug 28, 2019:''' Open problems from two workshops have been posted: [[Workshops:Warwick_2018|the 2018 Workshop on Data Summarization at the University of Warwick]] and [[Workshops:WOLA_2019|the 3rd Workshop on Local Algorithms at ETH Zurich]].

'''Jun 13, 2019:''' The webpage has been updated to the 1.31 branch of MediaWiki. Please email us at [mailto:admin@sublinear.info admin@sublinear.info] if you notice any problems.

'''Nov 08, 2017:''' [[Workshops:FOCS_2017|A list of open problems]] from [http://www.cs.columbia.edu/~ccanonne/workshop-focs2017/ Frontiers in Distribution Testing], a workshop at FOCS 2017, has been posted.

'''Apr 28, 2017:''' [[Workshops:Banff_2017|A list of open problems]] from a BIRS workshop on communication complexity has been posted.

'''Jan 19, 2017:''' We made the switch to HTTPS for more security. Please let us know at [mailto:admin@sublinear.info admin@sublinear.info] if something stops to work. Consider also updating your password.

'''Dec 13, 2016:''' The webpage has been updated to the 1.27 branch of MediaWiki. Please email us at [mailto:admin@sublinear.info admin@sublinear.info] if you notice any problems.

'''May 26, 2016:''' The webpage has been updated and math rendering should work correctly again. Please email us at [mailto:admin@sublinear.info admin@sublinear.info] if you notice any problems.

'''May 21, 2016:''' The latest security update of MediaWiki unfortunately broke the extension responsible for rendering math equations. We turned it off for now. Versions of the problems with correctly rendered math can be enjoyed in the [https://{{SERVERNAME}}/sublinear_info.pdf pdf form].

'''Jan 18, 2016:''' [[Workshops:Baltimore_2016|Open problems]] from the Sublinear Algorithms Workshop at the Johns Hopkins University have been posted.

'''May 09, 2015:''' The entire list is now available as a [https://{{SERVERNAME}}/sublinear_info.pdf single pdf]. Checking the online version is still recommended. The pdf may become outdated and we can't promise prompt updates.

'''May 07, 2015:''' The wiki has just been updated to MediaWiki 1.23, the current long term support release. Please notify us at [mailto:admin@sublinear.info admin@sublinear.info] if anything stops working.

'''Jun 13, 2014:''' [[Workshops:Bertinoro_2014|Open problems]] from the 2014 Bertinoro Workshop on Sublinear Algorithms have been posted.

'''Sep 21, 2013:''' Eric Blais, Sourav Chakraborty, and C. Seshadhri have started [http://ptreview.sublinear.info/ ''Property Testing Review''], a blog dedicated to new developments in property testing and sublinear-time algorithms.

'''May 20, 2013:''' Recently submitted updates:
* {{ProblemLink|50}}

'''Mar 29, 2013:''' Recently submitted updates:
* {{ProblemLink|31}} (resolved)
* {{ProblemLink|38}}
* {{ProblemLink|40}} (resolved)

'''Feb 10, 2013:''' A simple anti-spam solution has been installed. Email confirmation is no longer required to edit the wiki, but we suggest that you still log in if you don't want your IP address to be displayed in the edit history.

'''Dec 12, 2012:''' The wiki is now officially open to celebrate 12/12/12!

'''Nov 10, 2012:''' Email confirmation is now required to prevent spammers.

'''Oct 01, 2012:''' This website will contain a list of open problems. There will be an official opening soon! Stay tuned!

Main Page

2019-08-29T02:48:03Z

Krzysztof Onak: /* News */

{{DISPLAYTITLE:List of Open Problems in Sublinear Algorithms}}
== About ==

The goal of this wiki is to collate a set of open problems in sub-linear algorithms and to track progress that is made on these problems. Important topics within sub-linear algorithms include data stream algorithms (sub-linear space), property testing (sub-linear time), and communication complexity (sub-linear communication) but this list isn't exhaustive. Indeed many of the early problems were posted at related workshops. We invite you to add further questions and update the wiki when progress is made on existing questions.

== News ==
'''Aug 28, 2019:''' Open problems from two workshops have been posted: [[Workshops:Warwick_2018|the 2018 Workshop on Data Summarization at the University of Warwick]] and [[Workshops:WOLA_2019|the 3rd Workshop on Local Algorithms at ETH Zurich]].

'''Jun 13, 2019:''' The webpage has been updated to the 1.31 branch of MediaWiki. Please email us at [mailto:admin@sublinear.info admin@sublinear.info] if you notice any problems.

'''Nov 08, 2017:''' [[Workshops:FOCS_2017|A list of open problems]] from [http://www.cs.columbia.edu/~ccanonne/workshop-focs2017/ Frontiers in Distribution Testing], a workshop at FOCS 2017, has been posted.

[[News|Old news…]]

== Content ==
*[[Open_Problems:By_Number|Ordered list of open problems]]
*[https://{{SERVERNAME}}/sublinear_info.pdf The entire list compiled into a single pdf] (May be out of date. Save trees! Don't print unless you really have to.)
*[[Workshops|Workshops where open problems were suggested]]
*[[Resources|Resources on sublinear algorithms]]

== Random (Unsolved) Problem ==
*{{RandomUnsolved}}

== Citing and Editing ==
*[[Citing|Citing open problems]]
*[[Editing]]
*[[Waiting|Submiting a new problem]]
*[[TODO|Improvement suggestions]]

== Contact information ==
*Please send questions and comments to [mailto:admin@sublinear.info admin@sublinear.info].
*[//www.youtube.com/watch?v=_Sy9c0bQRsU Who we are]
__NOTOC__

Waiting

2019-08-26T18:38:49Z

Krzysztof Onak: Removing WOLA problems

Open Problems:102

2019-08-26T18:36:54Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Making edges happy in the LOCAL model to Open Problems:102 without leaving a redirect

{{Header
|source=wola19
|who=Jukka Suomela
}}
In this question, the input is the underlying graph $G=(V,E)$, promised to have maximum degree at most $\Delta$, and the goal is to compute an orientation of the edges of $E$ which makes all edges “happy.” Specifically, for any given orientation of the edges, the ''load'' of a node $v\in V$ is its number of incoming edges. An edge $e$ is then said to be ''happy'' if switching its orientation does not make it point to a smaller-node load.

One can show by a greedy argument that there always exists an orientation making all edges happy. Moreover, a surprising result established that, in the LOCAL model, such a configuration could be found in $\operatorname{poly}(\Delta)$ rounds, ''independent'' of the number of nodes $n$. However, the question of the dependence on $\Delta$ remains wide open, as even a $\operatorname{poly}\!\log(\Delta)$ upper bound is not ruled out.

'''Question:''' What is the right dependence on $\Delta$? Can one show ''any'' lower polynomial lower bound, e.g., $\Delta^{0.1}$, $\sqrt{\Delta}$, or $\Delta$?

Open Problems:102

2019-08-26T18:36:39Z

Krzysztof Onak: Updating the header

Open Problems:101

2019-08-26T18:36:22Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Vertex connectivity in the LOCAL model to Open Problems:101 without leaving a redirect

{{Header
|source=wola19
|who=Sorrachai Yingchareonthawornchai
}}
In this question, the input is the underlying graph $G=(V,E)$, as well as parameters $\nu,k$ and vertex $v\in V$. The goal is to output either $\bot$ or a subset $S\subseteq V$, such that

* if $\bot$ is the output, there is no $S$ such that $v\in S$ with $|S| \leq \nu$ and $|N(S)| < k$;

* if the output is a set $S$, then $|N(S)| < k$.

It is known that this problem can be solved with $O(\nu k)$ queries, and either time $O(\nu^{3/2} k)$ (deterministic) or $O(\nu k^2)$ (randomized) {{Cite|NanongkaiSY-19a|NanongkaiSY-19b|ForsterY-19}}.

'''Question:''' Can one achieve time $O(\nu k)$?

Open Problems:101

2019-08-26T18:36:07Z

Krzysztof Onak: Updating the header

Open Problems:100

2019-08-26T18:33:57Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Effective Support Size Estimation in the Dual Model to Open Problems:100 without leaving a redirect

Open Problems:100

2019-08-26T18:33:43Z

Krzysztof Onak: Updating the header

Open Problems:99

2019-08-26T18:26:50Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Vertex-Distribution-Free Graph Testing to Open Problems:99 without leaving a redirect

{{Header
|source=wola19
|who=Oded Goldreich
}}
The graph query model where one gets to query vertices uniformly at random may seem unrealistic in some cases. Thus, one may advocate alternative models, especially in the context of graph property testing, akin to the “distribution-free” model of property testing (for functions) and the PAC model (for learning). In this ''Vertex-Distribution-Free'' (VDF) model of testing suggested in a recent paper {{Cite|Goldreich-19a}}<ref>This model was also briefly discussed in Section 10.1 of {{Cite|GoldreichGR-98}}.</ref>, one gets i.i.d. vertices sampled from an arbitrary distribution $\mathcal{D}$ over the vertex set, and the goal is to test w.r.t. to the (pseudo) distance induced by $\mathcal{D}$.

'''Question:''' Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.

'''Question:''' ''(Suggested by C. Seshadhri)'' Can one define, motivate, and prove non-trivial results in an ''Edge''-Distribution-Free model, analogous to the VDF one but with regard to sampling random edges?<ref>This type of variant was also briefly evoked in Section 10.1.4 of {{Cite|GoldreichGR-98}}, where it was shown that Bipartiteness is not testable in such an EDF model.</ref>

==Notes==
<references />

Open Problems:99

2019-08-26T18:26:36Z

Krzysztof Onak: Updating the header

Open Problems:98

2019-08-26T18:25:06Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Estimating a Graph's Degree Distribution to Open Problems:98 without leaving a redirect

{{Header
|source=wola19
|who=C. Seshadhri
}}
The ''degree distribution'' of a graph $G=(V,E)$ is the histogram of the degree frequencies: i.e., letting $n(d)$ denote the number of degree-$d$ vertices, the histogram $(n(d))_{d\geq 0}$. Define the (complementary) cumulative distribution function as
\[
N(d) \stackrel{\rm def}{=} \sum_{d'\geq d} n(d'), \qquad d\geq 0\,.
\]
Assume one has access to the graph $G$ via the following (standard) three types of queries:

* sampling a vertex uniformly at random

* querying the degree of a given vertex

* sample a neighbor of a given vertex uniformly at random

and the goal is to obtain the following $(1\pm \varepsilon)$-“bicriteria” approximation $\hat{N}$ of the degree distribution: for all $d$,
\[
(1-\varepsilon)N( (1-\varepsilon)d) \leq \hat{N}(d) \leq (1+\varepsilon) N((1+\varepsilon)d)\,.
\]
Previous work of Eden, Jain, Pinar, Ron, and Seshadhri {{Cite|EdenJPRS-18}} shows an upper bound of
\[
\frac{n}{h} + \frac{m}{\min_d d\cdot N(d)}
\]
queries, where $h$ is the value s.t. $N(h)=h$ (where the complementary cdf intersects the diagonal).

'''Question:''' Can this upper bound be improved? Can one establish matching lower bounds?

And also, slightly less well-defined:

'''Question:''' Can one obtain better upper bounds when relaxing the goal to only learn the ''high-degree'' (tail) part of the distribution? What about testing properties of the degree distribution (e.g., “power-law-ness”) in this setting? And what about the first type of queries — can one relax it, or work with a different type of sampling than uniform (for instance, via random walks)?

Open Problems:98

2019-08-26T18:24:50Z

Krzysztof Onak: Updating the header

Open Problems:97

2019-08-26T18:16:48Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Local Computation Algorithm for MIS to Open Problems:97 without leaving a redirect

{{Header
|source=wola19
|who=Mohsen Gaffhari
}}
In the model of Local Computation Algorithms (LCA), given an input graph $G=(V,E)$, an algorithm gets, upon query any vertex $v$ of its choosing, the list of neighbors of $v$. In this model, the current state-of-the-art for the query complexity of computing a Maximal Independent Set (MIS) for graph $G$ of maximum degree at most $\Delta$ is an upper bound of
$$
\Delta^{O(\log\log \Delta)} \operatorname{poly}\!\log n
$$
queries.

'''Question:''' Does there exist a $\operatorname{poly}(\log n, \Delta)$-query LCA for MIS?

Open Problems:97

2019-08-26T18:16:31Z

Krzysztof Onak: Updating the header

Open Problems:96

2019-08-26T18:12:11Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Identity Testing Up to Coarsenings to Open Problems:96 without leaving a redirect

{{Header
|source=wola19
|who=Clément Canonne
}}
Given a distance parameter $\varepsilon\in(0,1]$, i.i.d. samples from an unknown distribution $p$, and a (known) reference distribution $q$, both over $[n] = \{1,\dots,n\}$, the identity testing question asks for the minimum number of samples sufficient to distinguish, with probability at least $2/3$, between (i) $p=q$ and (ii) $\operatorname{d}_{\rm TV}(p,q) > \varepsilon$. ($\operatorname{d}_{\rm TV}$ here denotes the total variation distance.) This question is by now fully resolved, with $\Theta(\sqrt{n}/\varepsilon^2)$ samples being necessary and sufficient {{Cite|Paninski-08|ValiantV-14}}.

However, consider the following variant: given a (fixed) family $\mathcal{F}$ of functions from $[n]$ to $[m]$, and a reference distribution $q$ over $[m]$, distinguish between (i) there exists $f\in \mathcal{F}$, $p = q\circ f$, and (ii) $\min_{f\in\mathcal{F}} \operatorname{d}_{\rm TV}(p,q\circ f) > \varepsilon$.

This ''$\mathcal{F}$-identity testing'' question includes the identity testing one as special case by setting $m=n$ and $\mathcal{F}$ to be the singleton containing the identity function. One can also take $m=n$ and $\mathcal{F}$ to be the class of all permutations, to test “identity up to relabeling” (a problem whose sample complexity is, from previous work of Valiant and Valiant, known to be $\Theta(n/(\varepsilon^2\log n))$ (see Corollary 11.30 of {{Cite|Goldreich-17}}).

'''Question:''' For a fixed $m$, and $\mathcal{F}$ the family of all partitions of $[n]$ into $m$ consecutive intervals, what is the sample complexity of $\mathcal{F}$-identity testing, as a function of $n$, $\varepsilon$, and $m$?

'''Note:''' This corresponds to testing whether $p$ is a ''refinement'' of the coarse distribution $q$; or, equivalently, if $p$ and $q$ are the same, up to the precision of the measurements.

Open Problems:96

2019-08-26T18:11:53Z

Krzysztof Onak: Updating the header

Open Problems:95

2019-08-26T18:11:33Z

Krzysztof Onak: Updating the header

{{Header
|source=wola19
|who=Oliver Gebhard
}}
In (non-adaptive) quantitative group testing, one has a population of $n$ individuals, among which $k=n^c$ (for some constant $c\in(0,1)$) are sick. The goal is to identity the $k$ sick individuals by performing $m$ non-adaptive tests. In each test, one specifies a subset $S\subseteq [n]$ and learns whether $S$ contains one or more sick individuals.

By a counting argument, one gets a lower bound of $m = \Omega\bigl( \frac{k}{\log k}\log \frac{n}{k} \bigr)$ tests; however, the best known upper bound is $m = O( k\log \frac{n}{k} )$.

'''Question:''' Can one get rid of the $\log k$ factor in the lower bound; or, conversely, improve the upper bound to match it?

Open Problems:95

2019-08-26T18:10:23Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Non-Adaptive Group Testing to Open Problems:95 without leaving a redirect

{{Header
|title=Non-Adaptive Group Testing
|source=wola19
|who=Oliver Gebhard
}}
In (non-adaptive) quantitative group testing, one has a population of $n$ individuals, among which $k=n^c$ (for some constant $c\in(0,1)$) are sick. The goal is to identity the $k$ sick individuals by performing $m$ non-adaptive tests. In each test, one specifies a subset $S\subseteq [n]$ and learns whether $S$ contains one or more sick individuals.

By a counting argument, one gets a lower bound of $m = \Omega\bigl( \frac{k}{\log k}\log \frac{n}{k} \bigr)$ tests; however, the best known upper bound is $m = O( k\log \frac{n}{k} )$.

'''Question:''' Can one get rid of the $\log k$ factor in the lower bound; or, conversely, improve the upper bound to match it?

Open Problems:By Number

2019-08-26T18:09:13Z

Krzysztof Onak: Adding WOLA problems

Problems suggested at the [[Workshops:Kanpur_2006|IITK Workshop on Algorithms for Data Streams 2006]]:
*{{ProblemLink|1}}
*{{ProblemLink|2}}
*{{ProblemLink|3}}
*{{ProblemLink|4}}
*{{ProblemLink|5}}
*{{ProblemLink|6}}
*{{ProblemLink|7}}
*{{ProblemLink|8}}
*{{ProblemLink|9}}
*{{ProblemLink|10}}
*{{ProblemLink|11}}
*{{ProblemLink|12}}
*{{ProblemLink|13}}
*{{ProblemLink|14}}
*{{ProblemLink|15}}
*{{ProblemLink|16}}
*{{ProblemLink|17}}
*{{ProblemLink|18}}
*{{ProblemLink|19}}
*{{ProblemLink|20}}
*{{ProblemLink|21}}

Problems suggested at the [[Workshops:Kanpur_2009|IITK Workshop on Algorithms for Processing Massive Data Sets 2009]]:
*{{ProblemLink|22}}
*{{ProblemLink|23}}
*{{ProblemLink|24}}
*{{ProblemLink|25}}
*{{ProblemLink|26}}
*{{ProblemLink|27}}
*{{ProblemLink|28}}
*{{ProblemLink|29}}
*{{ProblemLink|30}}
*{{ProblemLink|31}}
*{{ProblemLink|32}}
*{{ProblemLink|33}}
*{{ProblemLink|34}}
*{{ProblemLink|35}}

Problems suggested at the [[Workshops:Bertinoro_2011|Bertinoro Workshop on Sublinear Algorithms 2011]]:
*{{ProblemLink|36}}
*{{ProblemLink|37}}
*{{ProblemLink|38}}
*{{ProblemLink|39}}
*{{ProblemLink|40}}
*{{ProblemLink|41}}
*{{ProblemLink|42}}
*{{ProblemLink|43}}
*{{ProblemLink|44}}
*{{ProblemLink|45}}
*{{ProblemLink|46}}
*{{ProblemLink|47}}
*{{ProblemLink|48}}
*{{ProblemLink|49}}
*{{ProblemLink|50}}

Problems suggested at the [[Workshops:Dortmund_2012|Dortmund Workshop on Algorithms for Data Streams 2012]]:
*{{ProblemLink|51}}
*{{ProblemLink|52}}
*{{ProblemLink|53}}
*{{ProblemLink|54}}
*{{ProblemLink|55}}
*{{ProblemLink|56}}
*{{ProblemLink|57}}
*{{ProblemLink|58}}
*{{ProblemLink|59}}
*{{ProblemLink|60}}

Problems suggested at the [[Workshops:Bertinoro_2014|Bertinoro Workshop on Sublinear Algorithms 2014]]:
*{{ProblemLink|61}}
*{{ProblemLink|62}}
*{{ProblemLink|63}}
*{{ProblemLink|64}}
*{{ProblemLink|65}}
*{{ProblemLink|66}}
*{{ProblemLink|67}}
*{{ProblemLink|68}}

Problems suggested at the [[Workshops:Baltimore_2016|Sublinear Algorithms Workshop 2016 at Johns Hopkins University]]:
*{{ProblemLink|69}}
*{{ProblemLink|70}}
*{{ProblemLink|71}}
*{{ProblemLink|72}}
*{{ProblemLink|73}}
*{{ProblemLink|74}}

Problems suggested at the [[Workshops:Banff_2017|Workshop on Communication Complexity and Applications 2017 at the Banff International Research Station]]:
*{{ProblemLink|75}}
*{{ProblemLink|76}}
*{{ProblemLink|77}}
*{{ProblemLink|78}}
*{{ProblemLink|79}}
*{{ProblemLink|80}}

Problems suggested at the [[Workshops:FOCS 2017|Frontiers in Distribution Testing workshop at FOCS 2017]]:
*{{ProblemLink|81}}
*{{ProblemLink|82}}
*{{ProblemLink|83}}
*{{ProblemLink|84}}
*{{ProblemLink|85}}
*{{ProblemLink|86}}
*{{ProblemLink|87}}
*{{ProblemLink|88}}
*{{ProblemLink|89}}

Problems suggested at the [[Workshops:Warwick_2018|Workshop on Data Summarization at the University of Warwick in 2018]]:
*{{ProblemLink|90}}
*{{ProblemLink|91}}
*{{ProblemLink|92}}
*{{ProblemLink|93}}
*{{ProblemLink|94}}

Problems suggested at the [[Workshops:WOLA_2019|Workshop on Local Algorithms 2019 at ETH Zurich]]:
*{{ProblemLink|95}}
*{{ProblemLink|96}}
*{{ProblemLink|97}}
*{{ProblemLink|98}}
*{{ProblemLink|99}}
*{{ProblemLink|100}}
*{{ProblemLink|101}}
*{{ProblemLink|102}}

Template:RandomUnsolved

2019-08-26T18:06:47Z

Krzysztof Onak: Adding new problems

<choose uncached>
<option>1</option>
<option>2</option>
<option>3</option>
<option>4</option>
<option>5</option>
<option>6</option>
<option>7</option>
<option>8</option>
<option>9</option>
<option>10</option>
<option>11</option>
<option>12</option>
<option>13</option>
<option>14</option>
<option>15</option>
<option>16</option>
<option>17</option>
<option>18</option>
<option>19</option>
<option>20</option>
<option>21</option>
<option>22</option>
<option>24</option>
<option>25</option>
<option>26</option>
<option>27</option>
<option>28</option>
<option>29</option>
<option>30</option>
<option>32</option>
<option>33</option>
<option>34</option>
<option>35</option>
<option>36</option>
<option>37</option>
<option>38</option>
<option>39</option>
<option>41</option>
<option>42</option>
<option>43</option>
<option>44</option>
<option>45</option>
<option>46</option>
<option>48</option>
<option>49</option>
<option>50</option>
<option>51</option>
<option>52</option>
<option>53</option>
<option>54</option>
<option>55</option>
<option>56</option>
<option>57</option>
<option>58</option>
<option>59</option>
<option>60</option>
<option>61</option>
<option>62</option>
<option>63</option>
<option>64</option>
<option>65</option>
<option>66</option>
<option>67</option>
<option>68</option>
<option>69</option>
<option>70</option>
<option>71</option>
<option>72</option>
<option>73</option>
<option>74</option>
<option>75</option>
<option>76</option>
<option>77</option>
<option>78</option>
<option>79</option>
<option>80</option>
<option>81</option>
<option>82</option>
<option>83</option>
<option>84</option>
<option>85</option>
<option>86</option>
<option>87</option>
<option>88</option>
<option>89</option>
<option>90</option>
<option>91</option>
<option>92</option>
<option>93</option>
<option>94</option>
<option>95</option>
<option>96</option>
<option>97</option>
<option>98</option>
<option>99</option>
<option>100</option>
<option>101</option>
<option>102</option>
<choicetemplate>ProblemLink</choicetemplate>
</choose>

Template:Workshop

2019-08-26T18:05:35Z

Krzysztof Onak:

{{#switch: {{{1}}} |
kanpur06 = [[Workshops:Kanpur_2006|Kanpur 2006]] |
kanpur09 = [[Workshops:Kanpur_2009|Kanpur 2009]] |
bertinoro11 = [[Workshops:Bertinoro_2011|Bertinoro 2011]] |
dortmund12 = [[Workshops:Dortmund_2012|Dortmund 2012]] |
bertinoro14 = [[Workshops:Bertinoro_2014|Bertinoro 2014]] |
baltimore16 = [[Workshops:Baltimore_2016|Baltimore 2016]] |
banff17 = [[Workshops:Banff_2017|Banff 2017]] |
focs17 = [[Workshops:FOCS_2017|FOCS 2017]] |
warwick18 = [[Workshops:Warwick_2018|Warwick 2018]] |
wola19 = [[Workshops:WOLA_2019|WOLA 2019]] |
online = submitted online |
{{{1}}}
}}

Template:ProblemName

2019-08-26T18:05:07Z

Krzysztof Onak: Maybe this capitalization is more consistent

{{#switch: {{{1}}}
| 1 = Fast $L_1$ Difference
| 2 = Quantiles
| 3 = $L_\infty$ Estimation
| 4 = Deterministic Summary Structures
| 5 = Characterizing Sketchable Distances
| 6 = Filtering Irrelevant Data
| 7 = Estimating Earth-Mover Distance
| 8 = Mixed Norms
| 9 = Open-Shortest-Path-First Routing
| 10 = Multi-Round Communication of Gap-Hamming Distance
| 11 = Counting Triangles
| 12 = Deterministic $CUR$-Type Decompositions
| 13 = Effects of Subsampling
| 14 = Graph Distances
| 15 = Semi-Random Streams
| 16 = Graph Matchings
| 17 = The Massive, Unordered, Distributed-Data Model
| 18 = Finite Cursor Machines
| 19 = Sketching vs. Streaming
| 20 = Relations between Streaming Models
| 21 = Deterministic Heavy-Hitters & Fast Matrix Algorithms
| 22 = Random Walks
| 23 = Approximate 2D Width
| 24 = “Ultimate” Deterministic Sparse Recovery
| 25 = Communication Complexity and Metric Spaces
| 26 = Equivalence of Two MapReduce Models
| 27 = Modeling of Distributed Computation
| 28 = Randomness of Partially Random Streams
| 29 = Strong Lower Bounds for Graph Problems
| 30 = Universal Sketching
| 31 = Gap-Hamming Information Cost
| 32 = The Value of a Reverse Pass
| 33 = Group Testing
| 34 = Linear Algebra Computation
| 35 = Maximal Complex Equiangular Tight Frames
| 36 = Learning an $f$-Transformed Product Distribution
| 37 = Testing Submodularity
| 38 = Query Complexity of Local Partitioning Oracles
| 39 = Approximating Maximum Matching Size
| 40 = Testing Monotonicity and the Lipschitz Property
| 41 = Testing Acyclicity
| 42 = Graph Frequency Vectors
| 43 = Rank Lower Bound
| 44 = Approximating LIS Length in the Streaming Model
| 45 = Streaming Max-Cut/Max-CSP
| 46 = Fast JL Transform for Sparse Vectors
| 47 = Annotated Streaming
| 48 = Sketching Shift Metrics
| 49 = Sketching Earth Mover Distance
| 50 = Sparse Recovery for Tree Models
| 51 = “For All” Guarantee for Computationally Bounded Adversaries
| 52 = TSP in the Streaming Model
| 53 = Homomorphic Hash Functions
| 54 = Faster JL Dimensionality Reduction
| 55 = Applications of Clifford Algebras in Graph Streams
| 56 = Efficient Measures of “Surprisingness” of Sequences
| 57 = Coding Theory in the Streaming Model
| 58 = Signatures for Set Equality
| 59 = Low Expansion Encoding of Edit Distance
| 60 = Single-Pass Unweighted Matchings
| 61 = RNA Folding
| 62 = Principal Component Analysis with Nonnegativity Constraints
| 63 = Submodular Matching Maximization
| 64 = Matchings in the Turnstile Model
| 65 = Communication Complexity of Connectivity
| 66 = Distinguishing Distributions with Conditional Samples
| 67 = Difficult Instance for Max-Cut in the Streaming Model
| 68 = Approximating Rank in the Bounded-Degree Model
| 69 = Correcting Independence of Distributions
| 70 = Open Problems in $L_p$-Testing
| 71 = Metric TSP Cost Approximation
| 72 = Communication Complexity of Approximating Set-Intersection Join
| 73 = Streaming Online Algorithms
| 74 = Succinct Representation for Functions on Graphs
| 75 = Data Structure Lower Bound in the Cell Probe Model
| 76 = External Information and Amortized Expected Communication
| 77 = Frontiers in Structural Communication Complexity
| 78 = Linear Sketching Over $F_2$
| 79 = Cryptogenography
| 80 = Merlin–Arthur Communication Complexity of Connectivity
| 81 = Rényi Entropy Estimation
| 82 = Beyond Identity Testing
| 83 = Instance-Specific Hellinger Testing
| 84 = Efficient Profile Maximum Likelihood Computation
| 85 = Sample Stretching
| 86 = Equivalence Testing Lower Bound via Communication Complexity
| 87 = Equivalence Testing with Conditional Samples
| 88 = Separating PDF and CDF Query Models
| 89 = AM vs. NP for Proofs of Proximity in Distribution Testing
| 90 = Dense Graph Property Testing “Tradeoffs”
| 91 = Cut-Sparsification of Hypergraphs
| 92 = Streaming Algorithms for Approximating the Number of $H$-Subgraphs
| 93 = Locally Private Heavy Hitters and Other Problems in Streaming
| 94 = Ads, Impressions, and Statistics
| 95 = Non-Adaptive Group Testing
| 96 = Identity Testing up to Coarsenings
| 97 = Local Computation Algorithm for MIS
| 98 = Estimating a Graph's Degree Distribution
| 99 = Vertex-Distribution-Free Graph Testing
| 100 = Effective Support Size Estimation in the Dual Model
| 101 = Vertex Connectivity in the LOCAL Model
| 102 = Making Edges Happy in the LOCAL Model
| !!! ADD THE PROBLEM NAME TO Template:ProblemName !!!
}}

Workshops:WOLA 2019

2019-08-26T18:04:03Z

Krzysztof Onak: Creating the page for WOLA 2019

{{DISPLAYTITLE:Workshop on Local Algorithms 2019 at ETH Zurich}}
The 3rd Workshop on Local Algorithms was held at ETH Zurich in July of 2019. This list contains open problems suggested by participants during the open problems session. The list was written by Clément Cannone. More information about the workshop can be found at [https://people.inf.ethz.ch/gmohsen/WOLA19/ the workshop webpage].

== Links ==
* [https://people.inf.ethz.ch/gmohsen/WOLA19/ Workshop webpage]

== Open Problems ==
*{{ProblemLink|95}}
*{{ProblemLink|96}}
*{{ProblemLink|97}}
*{{ProblemLink|98}}
*{{ProblemLink|99}}
*{{ProblemLink|100}}
*{{ProblemLink|101}}
*{{ProblemLink|102}}

Workshops

2019-08-26T17:40:02Z

Krzysztof Onak: Adding a link to a new workshop

Many open problems were copied from lists of open problems compiled at workshops.
* [[Workshops:Kanpur_2006|IITK Workshop on Algorithms for Data Streams 2006]]
* [[Workshops:Kanpur_2009|IITK Workshop on Algorithms for Processing Massive Data Sets 2009]]
* [[Workshops:Bertinoro_2011|Bertinoro Workshop on Sublinear Algorithms 2011]]
* [[Workshops:Dortmund_2012|Dortmund Workshop on Algorithms for Data Streams 2012]]
* [[Workshops:Bertinoro_2014|Bertinoro Workshop on Sublinear Algorithms 2014]]
* [[Workshops:Baltimore_2016|Sublinear Algorithms Workshop 2016 at Johns Hopkins University]]
* [[Workshops:Banff_2017|Communication Complexity and Applications 2017 at the Banff International Research Station]]
* [[Workshops:FOCS_2017|Frontiers in Distribution Testing (workshop at FOCS 2017 in Berkeley)]]
* [[Workshops:Warwick_2018|Workshop on Data Summarization at the University of Warwick in 2018]]
* [[Workshops:WOLA_2019|Workshop on Local Algorithms 2019 at ETH Zurich]]

Open Problems:94

2019-08-25T03:12:41Z

Krzysztof Onak:

{{Header
|source=warwick18
}}
1. Consider the problem of reporting statistics about online ads to the advertisers that pay for them. Advertisers may wish to know how many unique people matching some demographic conditions have seen an ad at a particular time range. There are many ads and many demographic conditions and time ranges; and the service provider should be able to accurately answer any possible query over ads, demographics, and time. In other words, it’s an [https://en.wikipedia.org/wiki/OLAP_cube OLAP cube] problem where the aggregate is ''distinct count'' rather than ''sum''. How can one construct a sketch that will provide estimates with “good” errors that solves this with, say, $O(1)$ time complexity per query? Loosely speaking, “good” here means every query for an ad (without demographic conditions) has good relative error and any query that has a high count should have good relative error.

2. Suppose a company tracks an important high level metric (e.g., total network traffic) that is the sum of a metric over many discrete categories (e.g., country, device, network provider, etc.). When that metric changes in an unexpected way, it wishes to figure out what combinations of categories are driving that change. How can one find a small set of combination of categories that explains most of the change and can be described succinctly? Can this be done in real-time so that a streaming sketch can keep track of the appropriate approximate aggregates and the search for a succinct description of category can be done in “reasonable” time?

Open Problems:102

2019-08-25T02:43:27Z

Krzysztof Onak:

{{Header
|title=Making edges happy in the LOCAL model
|source=wola19
|who=Jukka Suomela
}}
In this question, the input is the underlying graph $G=(V,E)$, promised to have maximum degree at most $\Delta$, and the goal is to compute an orientation of the edges of $E$ which makes all edges “happy.” Specifically, for any given orientation of the edges, the ''load'' of a node $v\in V$ is its number of incoming edges. An edge $e$ is then said to be ''happy'' if switching its orientation does not make it point to a smaller-node load.

One can show by a greedy argument that there always exists an orientation making all edges happy. Moreover, a surprising result established that, in the LOCAL model, such a configuration could be found in $\operatorname{poly}(\Delta)$ rounds, ''independent'' of the number of nodes $n$. However, the question of the dependence on $\Delta$ remains wide open, as even a $\operatorname{poly}\!\log(\Delta)$ upper bound is not ruled out.

'''Question:''' What is the right dependence on $\Delta$? Can one show ''any'' lower polynomial lower bound, e.g., $\Delta^{0.1}$, $\sqrt{\Delta}$, or $\Delta$?

Open Problems:101

2019-08-25T02:35:56Z

Krzysztof Onak:

{{Header
|title=Vertex connectivity in the LOCAL model
|source=wola19
|who=Sorrachai Yingchareonthawornchai
}}
In this question, the input is the underlying graph $G=(V,E)$, as well as parameters $\nu,k$ and vertex $v\in V$. The goal is to output either $\bot$ or a subset $S\subseteq V$, such that

* if $\bot$ is the output, there is no $S$ such that $v\in S$ with $|S| \leq \nu$ and $|N(S)| < k$;

* if the output is a set $S$, then $|N(S)| < k$.

It is known that this problem can be solved with $O(\nu k)$ queries, and either time $O(\nu^{3/2} k)$ (deterministic) or $O(\nu k^2)$ (randomized) {{Cite|NanongkaiSY-19a|NanongkaiSY-19b|ForsterY-19}}.

'''Question:''' Can one achieve time $O(\nu k)$?

Open Problems:100

2019-08-25T02:27:36Z

Krzysztof Onak:

{{Header
|title=Effective Support Size Estimation in the Dual Model
|source=wola19
|who=Oded Goldreich
}}
For a probability distribution $p$ over a discrete domain $\Omega$, and a parameter $\varepsilon\in[0,1]$, denote by
\[
\operatorname{ess}_\varepsilon(p) \stackrel{\rm def}{=} \min\{ \operatorname{supp}(q) : \operatorname{d}_{\rm TV}(p,q) \leq \varepsilon \}
\]
the $\varepsilon$-effective suport size of $p$, i.e., the smallest possible support size of any distribution $\varepsilon$-close to $p$. This turns out to be a more robust and interesting measure in general than the support of $p$, which is $\operatorname{ess}_0(p) = \operatorname{supp}(p)$. In recent work, Goldreich {{Cite|Goldreich-19b}} focused on the query complexity of approximating the effective support size of a discrete distribution provided via two oracles: sampling ($\textsf{samp}_p$), and query access (to the probability mass function), $\textsf{eval}_p$. In particular, the goal is, given parameters $\varepsilon$ and $\beta>1$, to output an $f(\varepsilon,\beta,n)$-factor approximation of $\operatorname{ess}_{\varepsilon'}(p)$, for some $\varepsilon' \in [\varepsilon,\beta\varepsilon]$.

In the aforementioned work, algorithms are obtained achieving (for constant $\beta>1$)

* query complexity $\operatorname{poly}(1/\varepsilon)$ and approximation factor $f = O(\log\log\log\log(n/\varepsilon))$, that is, any constant number of iterated logarithms;

* query complexity $\operatorname{poly}(\log^\ast n, 1/\varepsilon)$ even for approximation factor $f = O(1)$;

where $n \stackrel{\rm def}{=} \operatorname{ess}_\varepsilon(p)$. (As well as several other results interpolating between the two extremes.)

'''Question:''' Can one get the best of both worlds, and get rid of the $\log^\ast n$ to obtain query complexity $\operatorname{poly}(1/\varepsilon)$ ''and'' constant approximation factor?

Open Problems:99

2019-08-25T02:20:50Z

Krzysztof Onak:

{{Header
|title=Vertex-Distribution-Free Graph Testing
|source=wola19
|who=Oded Goldreich
}}
The graph query model where one gets to query vertices uniformly at random may seem unrealistic in some cases. Thus, one may advocate alternative models, especially in the context of graph property testing, akin to the “distribution-free” model of property testing (for functions) and the PAC model (for learning). In this ''Vertex-Distribution-Free'' (VDF) model of testing suggested in a recent paper {{Cite|Goldreich-19a}}<ref>This model was also briefly discussed in Section 10.1 of {{Cite|GoldreichGR-98}}.</ref>, one gets i.i.d. vertices sampled from an arbitrary distribution $\mathcal{D}$ over the vertex set, and the goal is to test w.r.t. to the (pseudo) distance induced by $\mathcal{D}$.

'''Question:''' Perform a systematic study of property testing, both in the bounded-degree and dense graph models, in this VDF setting.

'''Question:''' ''(Suggested by C. Seshadhri)'' Can one define, motivate, and prove non-trivial results in an ''Edge''-Distribution-Free model, analogous to the VDF one but with regard to sampling random edges?<ref>This type of variant was also briefly evoked in Section 10.1.4 of {{Cite|GoldreichGR-98}}, where it was shown that Bipartiteness is not testable in such an EDF model.</ref>

==Notes==
<references />

Open Problems:98

2019-08-25T02:05:38Z

Krzysztof Onak:

{{Header
|title=Estimating a Graph's Degree Distribution
|source=wola19
|who=C. Seshadhri
}}
The ''degree distribution'' of a graph $G=(V,E)$ is the histogram of the degree frequencies: i.e., letting $n(d)$ denote the number of degree-$d$ vertices, the histogram $(n(d))_{d\geq 0}$. Define the (complementary) cumulative distribution function as
\[
N(d) \stackrel{\rm def}{=} \sum_{d'\geq d} n(d'), \qquad d\geq 0\,.
\]
Assume one has access to the graph $G$ via the following (standard) three types of queries:

* sampling a vertex uniformly at random

* querying the degree of a given vertex

* sample a neighbor of a given vertex uniformly at random

and the goal is to obtain the following $(1\pm \varepsilon)$-“bicriteria” approximation $\hat{N}$ of the degree distribution: for all $d$,
\[
(1-\varepsilon)N( (1-\varepsilon)d) \leq \hat{N}(d) \leq (1+\varepsilon) N((1+\varepsilon)d)\,.
\]
Previous work of Eden, Jain, Pinar, Ron, and Seshadhri {{Cite|EdenJPRS-18}} shows an upper bound of
\[
\frac{n}{h} + \frac{m}{\min_d d\cdot N(d)}
\]
queries, where $h$ is the value s.t. $N(h)=h$ (where the complementary cdf intersects the diagonal).

'''Question:''' Can this upper bound be improved? Can one establish matching lower bounds?

And also, slightly less well-defined:

'''Question:''' Can one obtain better upper bounds when relaxing the goal to only learn the ''high-degree'' (tail) part of the distribution? What about testing properties of the degree distribution (e.g., “power-law-ness”) in this setting? And what about the first type of queries — can one relax it, or work with a different type of sampling than uniform (for instance, via random walks)?

Open Problems:96

2019-08-25T01:56:38Z

Krzysztof Onak:

{{Header
|title=Identity Testing Up to Coarsenings
|source=wola19
|who=Clément Canonne
}}
Given a distance parameter $\varepsilon\in(0,1]$, i.i.d. samples from an unknown distribution $p$, and a (known) reference distribution $q$, both over $[n] = \{1,\dots,n\}$, the identity testing question asks for the minimum number of samples sufficient to distinguish, with probability at least $2/3$, between (i) $p=q$ and (ii) $\operatorname{d}_{\rm TV}(p,q) > \varepsilon$. ($\operatorname{d}_{\rm TV}$ here denotes the total variation distance.) This question is by now fully resolved, with $\Theta(\sqrt{n}/\varepsilon^2)$ samples being necessary and sufficient {{Cite|Paninski-08|ValiantV-14}}.

However, consider the following variant: given a (fixed) family $\mathcal{F}$ of functions from $[n]$ to $[m]$, and a reference distribution $q$ over $[m]$, distinguish between (i) there exists $f\in \mathcal{F}$, $p = q\circ f$, and (ii) $\min_{f\in\mathcal{F}} \operatorname{d}_{\rm TV}(p,q\circ f) > \varepsilon$.

This ''$\mathcal{F}$-identity testing'' question includes the identity testing one as special case by setting $m=n$ and $\mathcal{F}$ to be the singleton containing the identity function. One can also take $m=n$ and $\mathcal{F}$ to be the class of all permutations, to test “identity up to relabeling” (a problem whose sample complexity is, from previous work of Valiant and Valiant, known to be $\Theta(n/(\varepsilon^2\log n))$ (see Corollary 11.30 of {{Cite|Goldreich-17}}).

'''Question:''' For a fixed $m$, and $\mathcal{F}$ the family of all partitions of $[n]$ into $m$ consecutive intervals, what is the sample complexity of $\mathcal{F}$-identity testing, as a function of $n$, $\varepsilon$, and $m$?

'''Note:''' This corresponds to testing whether $p$ is a ''refinement'' of the coarse distribution $q$; or, equivalently, if $p$ and $q$ are the same, up to the precision of the measurements.

Open Problems:95

2019-08-25T01:42:09Z

Krzysztof Onak:

Template:RandomUnsolved

2019-08-25T01:03:35Z

Krzysztof Onak: resolving a caching issue

<choose uncached>
<option>1</option>
<option>2</option>
<option>3</option>
<option>4</option>
<option>5</option>
<option>6</option>
<option>7</option>
<option>8</option>
<option>9</option>
<option>10</option>
<option>11</option>
<option>12</option>
<option>13</option>
<option>14</option>
<option>15</option>
<option>16</option>
<option>17</option>
<option>18</option>
<option>19</option>
<option>20</option>
<option>21</option>
<option>22</option>
<option>24</option>
<option>25</option>
<option>26</option>
<option>27</option>
<option>28</option>
<option>29</option>
<option>30</option>
<option>32</option>
<option>33</option>
<option>34</option>
<option>35</option>
<option>36</option>
<option>37</option>
<option>38</option>
<option>39</option>
<option>41</option>
<option>42</option>
<option>43</option>
<option>44</option>
<option>45</option>
<option>46</option>
<option>48</option>
<option>49</option>
<option>50</option>
<option>51</option>
<option>52</option>
<option>53</option>
<option>54</option>
<option>55</option>
<option>56</option>
<option>57</option>
<option>58</option>
<option>59</option>
<option>60</option>
<option>61</option>
<option>62</option>
<option>63</option>
<option>64</option>
<option>65</option>
<option>66</option>
<option>67</option>
<option>68</option>
<option>69</option>
<option>70</option>
<option>71</option>
<option>72</option>
<option>73</option>
<option>74</option>
<option>75</option>
<option>76</option>
<option>77</option>
<option>78</option>
<option>79</option>
<option>80</option>
<option>81</option>
<option>82</option>
<option>83</option>
<option>84</option>
<option>85</option>
<option>86</option>
<option>87</option>
<option>88</option>
<option>89</option>
<option>90</option>
<option>91</option>
<option>92</option>
<option>93</option>
<option>94</option>
<choicetemplate>ProblemLink</choicetemplate>
</choose>

Template:ProblemName

2019-08-25T00:57:42Z

Krzysztof Onak: Updating the capitalization of the new titles

{{#switch: {{{1}}}
| 1 = Fast $L_1$ Difference
| 2 = Quantiles
| 3 = $L_\infty$ Estimation
| 4 = Deterministic Summary Structures
| 5 = Characterizing Sketchable Distances
| 6 = Filtering Irrelevant Data
| 7 = Estimating Earth-Mover Distance
| 8 = Mixed Norms
| 9 = Open-Shortest-Path-First Routing
| 10 = Multi-Round Communication of Gap-Hamming Distance
| 11 = Counting Triangles
| 12 = Deterministic $CUR$-Type Decompositions
| 13 = Effects of Subsampling
| 14 = Graph Distances
| 15 = Semi-Random Streams
| 16 = Graph Matchings
| 17 = The Massive, Unordered, Distributed-Data Model
| 18 = Finite Cursor Machines
| 19 = Sketching vs. Streaming
| 20 = Relations between Streaming Models
| 21 = Deterministic Heavy-Hitters & Fast Matrix Algorithms
| 22 = Random Walks
| 23 = Approximate 2D Width
| 24 = “Ultimate” Deterministic Sparse Recovery
| 25 = Communication Complexity and Metric Spaces
| 26 = Equivalence of Two MapReduce Models
| 27 = Modeling of Distributed Computation
| 28 = Randomness of Partially Random Streams
| 29 = Strong Lower Bounds for Graph Problems
| 30 = Universal Sketching
| 31 = Gap-Hamming Information Cost
| 32 = The Value of a Reverse Pass
| 33 = Group Testing
| 34 = Linear Algebra Computation
| 35 = Maximal Complex Equiangular Tight Frames
| 36 = Learning an $f$-Transformed Product Distribution
| 37 = Testing Submodularity
| 38 = Query Complexity of Local Partitioning Oracles
| 39 = Approximating Maximum Matching Size
| 40 = Testing Monotonicity and the Lipschitz Property
| 41 = Testing Acyclicity
| 42 = Graph Frequency Vectors
| 43 = Rank Lower Bound
| 44 = Approximating LIS Length in the Streaming Model
| 45 = Streaming Max-Cut/Max-CSP
| 46 = Fast JL Transform for Sparse Vectors
| 47 = Annotated Streaming
| 48 = Sketching Shift Metrics
| 49 = Sketching Earth Mover Distance
| 50 = Sparse Recovery for Tree Models
| 51 = “For All” Guarantee for Computationally Bounded Adversaries
| 52 = TSP in the Streaming Model
| 53 = Homomorphic Hash Functions
| 54 = Faster JL Dimensionality Reduction
| 55 = Applications of Clifford Algebras in Graph Streams
| 56 = Efficient Measures of “Surprisingness” of Sequences
| 57 = Coding Theory in the Streaming Model
| 58 = Signatures for Set Equality
| 59 = Low Expansion Encoding of Edit Distance
| 60 = Single-Pass Unweighted Matchings
| 61 = RNA Folding
| 62 = Principal Component Analysis with Nonnegativity Constraints
| 63 = Submodular Matching Maximization
| 64 = Matchings in the Turnstile Model
| 65 = Communication Complexity of Connectivity
| 66 = Distinguishing Distributions with Conditional Samples
| 67 = Difficult Instance for Max-Cut in the Streaming Model
| 68 = Approximating Rank in the Bounded-Degree Model
| 69 = Correcting Independence of Distributions
| 70 = Open Problems in $L_p$-Testing
| 71 = Metric TSP Cost Approximation
| 72 = Communication Complexity of Approximating Set-Intersection Join
| 73 = Streaming Online Algorithms
| 74 = Succinct Representation for Functions on Graphs
| 75 = Data Structure Lower Bound in the Cell Probe Model
| 76 = External Information and Amortized Expected Communication
| 77 = Frontiers in Structural Communication Complexity
| 78 = Linear Sketching Over $F_2$
| 79 = Cryptogenography
| 80 = Merlin–Arthur Communication Complexity of Connectivity
| 81 = Rényi Entropy Estimation
| 82 = Beyond Identity Testing
| 83 = Instance-Specific Hellinger Testing
| 84 = Efficient Profile Maximum Likelihood Computation
| 85 = Sample Stretching
| 86 = Equivalence Testing Lower Bound via Communication Complexity
| 87 = Equivalence Testing with Conditional Samples
| 88 = Separating PDF and CDF Query Models
| 89 = AM vs. NP for Proofs of Proximity in Distribution Testing
| 90 = Dense Graph Property Testing “Tradeoffs”
| 91 = Cut-Sparsification of Hypergraphs
| 92 = Streaming Algorithms for Approximating the Number of $H$-Subgraphs
| 93 = Locally Private Heavy Hitters and Other Problems in Streaming
| 94 = Ads, Impressions, and Statistics
| 95 = Non-Adaptive Group Testing
| 96 = Identity Testing Up to Coarsenings
| 97 = Local Computation Algorithm for MIS
| 98 = Estimating a Graph's Degree Distribution
| 99 = Vertex-Distribution-Free Graph Testing
| 100 = Effective Support Size Estimation in the Dual Model
| 101 = Vertex Connectivity in the LOCAL Model
| 102 = Making Edges Happy in the LOCAL Model
| !!! ADD THE PROBLEM NAME TO Template:ProblemName !!!
}}

Template:ProblemName

2019-08-25T00:31:31Z

Krzysztof Onak: "Adding names of problems from the WOLA workshop"

{{#switch: {{{1}}}
| 1 = Fast $L_1$ Difference
| 2 = Quantiles
| 3 = $L_\infty$ Estimation
| 4 = Deterministic Summary Structures
| 5 = Characterizing Sketchable Distances
| 6 = Filtering Irrelevant Data
| 7 = Estimating Earth-Mover Distance
| 8 = Mixed Norms
| 9 = Open-Shortest-Path-First Routing
| 10 = Multi-Round Communication of Gap-Hamming Distance
| 11 = Counting Triangles
| 12 = Deterministic $CUR$-Type Decompositions
| 13 = Effects of Subsampling
| 14 = Graph Distances
| 15 = Semi-Random Streams
| 16 = Graph Matchings
| 17 = The Massive, Unordered, Distributed-Data Model
| 18 = Finite Cursor Machines
| 19 = Sketching vs. Streaming
| 20 = Relations between Streaming Models
| 21 = Deterministic Heavy-Hitters & Fast Matrix Algorithms
| 22 = Random Walks
| 23 = Approximate 2D Width
| 24 = “Ultimate” Deterministic Sparse Recovery
| 25 = Communication Complexity and Metric Spaces
| 26 = Equivalence of Two MapReduce Models
| 27 = Modeling of Distributed Computation
| 28 = Randomness of Partially Random Streams
| 29 = Strong Lower Bounds for Graph Problems
| 30 = Universal Sketching
| 31 = Gap-Hamming Information Cost
| 32 = The Value of a Reverse Pass
| 33 = Group Testing
| 34 = Linear Algebra Computation
| 35 = Maximal Complex Equiangular Tight Frames
| 36 = Learning an $f$-Transformed Product Distribution
| 37 = Testing Submodularity
| 38 = Query Complexity of Local Partitioning Oracles
| 39 = Approximating Maximum Matching Size
| 40 = Testing Monotonicity and the Lipschitz Property
| 41 = Testing Acyclicity
| 42 = Graph Frequency Vectors
| 43 = Rank Lower Bound
| 44 = Approximating LIS Length in the Streaming Model
| 45 = Streaming Max-Cut/Max-CSP
| 46 = Fast JL Transform for Sparse Vectors
| 47 = Annotated Streaming
| 48 = Sketching Shift Metrics
| 49 = Sketching Earth Mover Distance
| 50 = Sparse Recovery for Tree Models
| 51 = “For All” Guarantee for Computationally Bounded Adversaries
| 52 = TSP in the Streaming Model
| 53 = Homomorphic Hash Functions
| 54 = Faster JL Dimensionality Reduction
| 55 = Applications of Clifford Algebras in Graph Streams
| 56 = Efficient Measures of “Surprisingness” of Sequences
| 57 = Coding Theory in the Streaming Model
| 58 = Signatures for Set Equality
| 59 = Low Expansion Encoding of Edit Distance
| 60 = Single-Pass Unweighted Matchings
| 61 = RNA Folding
| 62 = Principal Component Analysis with Nonnegativity Constraints
| 63 = Submodular Matching Maximization
| 64 = Matchings in the Turnstile Model
| 65 = Communication Complexity of Connectivity
| 66 = Distinguishing Distributions with Conditional Samples
| 67 = Difficult Instance for Max-Cut in the Streaming Model
| 68 = Approximating Rank in the Bounded-Degree Model
| 69 = Correcting Independence of Distributions
| 70 = Open Problems in $L_p$-Testing
| 71 = Metric TSP Cost Approximation
| 72 = Communication Complexity of Approximating Set-Intersection Join
| 73 = Streaming Online Algorithms
| 74 = Succinct Representation for Functions on Graphs
| 75 = Data Structure Lower Bound in the Cell Probe Model
| 76 = External Information and Amortized Expected Communication
| 77 = Frontiers in Structural Communication Complexity
| 78 = Linear Sketching Over $F_2$
| 79 = Cryptogenography
| 80 = Merlin–Arthur Communication Complexity of Connectivity
| 81 = Rényi Entropy Estimation
| 82 = Beyond Identity Testing
| 83 = Instance-Specific Hellinger Testing
| 84 = Efficient Profile Maximum Likelihood Computation
| 85 = Sample Stretching
| 86 = Equivalence Testing Lower Bound via Communication Complexity
| 87 = Equivalence Testing with Conditional Samples
| 88 = Separating PDF and CDF Query Models
| 89 = AM vs. NP for Proofs of Proximity in Distribution Testing
| 90 = Dense Graph Property Testing “Tradeoffs”
| 91 = Cut-Sparsification of Hypergraphs
| 92 = Streaming Algorithms for Approximating the Number of $H$-Subgraphs
| 93 = Locally Private Heavy Hitters and Other Problems in Streaming
| 94 = Ads, Impressions, and Statistics
| 95 = Non-Adaptive Group Testing
| 96 = Identity Testing Up to Coarsenings
| 97 = Local Computation Algorithm for MIS
| 98 = Estimating a Graph's Degree Distribution
| 99 = Vertex-Distribution-Free Graph Testing
| 100 = Effective Support Size Estimation in the Dual Model
| 101 = Vertex connectivity in the LOCAL model
| 102 = Making edges happy in the LOCAL model
| !!! ADD THE PROBLEM NAME TO Template:ProblemName !!!
}}

Waiting

2019-08-20T04:29:39Z

Krzysztof Onak: removing processed Warwick problems

{{DISPLAYTITLE:Waiting Room}}
Submitting a new problem:
# Make sure your problem is not yet on [[Open_Problems:By_Number|the list]].
# Edit this page to add <code><nowiki>*[[Waiting:Your Problem Name|]]</nowiki></code> at the bottom. This will create a link to a page for your new problem.
# Copy the content of [[Waiting:Sample Problem]] and use it as a starting point.
# Take your time editing the problem. See also [[Editing| the page with editing guidelines]].
# Once you are satisfied with the quality of the writeup, send an email to [mailto:admin@sublinear.info admin@sublinear.info].

== Problems in Preparation ==

*[[Waiting:Sample Problem|Sample Problem]] ← Please do not remove or edit!

WoLA'19:
*[[Waiting:Non-Adaptive Group Testing]]
*[[Waiting:Identity Testing Up to Coarsenings]]
*[[Waiting:Local Computation Algorithm for MIS]]
*[[Waiting:Estimating a Graph's Degree Distribution]]
*[[Waiting:Vertex-Distribution-Free Graph Testing]]
*[[Waiting:Effective Support Size Estimation in the Dual Model]]
*[[Waiting:Vertex connectivity in the LOCAL model]]
*[[Waiting:Making edges happy in the LOCAL model]]

Workshops

2019-08-20T04:22:12Z

Krzysztof Onak:

Template:RandomUnsolved

2019-08-20T04:16:13Z

Krzysztof Onak: Adding new problems

<choose>
<option>1</option>
<option>2</option>
<option>3</option>
<option>4</option>
<option>5</option>
<option>6</option>
<option>7</option>
<option>8</option>
<option>9</option>
<option>10</option>
<option>11</option>
<option>12</option>
<option>13</option>
<option>14</option>
<option>15</option>
<option>16</option>
<option>17</option>
<option>18</option>
<option>19</option>
<option>20</option>
<option>21</option>
<option>22</option>
<option>24</option>
<option>25</option>
<option>26</option>
<option>27</option>
<option>28</option>
<option>29</option>
<option>30</option>
<option>32</option>
<option>33</option>
<option>34</option>
<option>35</option>
<option>36</option>
<option>37</option>
<option>38</option>
<option>39</option>
<option>41</option>
<option>42</option>
<option>43</option>
<option>44</option>
<option>45</option>
<option>46</option>
<option>48</option>
<option>49</option>
<option>50</option>
<option>51</option>
<option>52</option>
<option>53</option>
<option>54</option>
<option>55</option>
<option>56</option>
<option>57</option>
<option>58</option>
<option>59</option>
<option>60</option>
<option>61</option>
<option>62</option>
<option>63</option>
<option>64</option>
<option>65</option>
<option>66</option>
<option>67</option>
<option>68</option>
<option>69</option>
<option>70</option>
<option>71</option>
<option>72</option>
<option>73</option>
<option>74</option>
<option>75</option>
<option>76</option>
<option>77</option>
<option>78</option>
<option>79</option>
<option>80</option>
<option>81</option>
<option>82</option>
<option>83</option>
<option>84</option>
<option>85</option>
<option>86</option>
<option>87</option>
<option>88</option>
<option>89</option>
<option>90</option>
<option>91</option>
<option>92</option>
<option>93</option>
<option>94</option>
<choicetemplate>ProblemLink</choicetemplate>
</choose>

Workshops:Warwick 2018

2019-08-20T04:14:58Z

Krzysztof Onak: Created page with "{{DISPLAYTITLE:Workshop on Data Summarization at the University of Warwick in 2018}} The Workshop on Data Summarization was held at the University of Warwick in March 2018. Th..."

{{DISPLAYTITLE:Workshop on Data Summarization at the University of Warwick in 2018}}
The Workshop on Data Summarization was held at the University of Warwick in March 2018. This list contains open problems suggested by participants during the open problems session. More information about the workshop can be found at [https://warwick.ac.uk/fac/sci/dcs/research/focs/conf2017/ the workshop webpage].

== Links ==
* [https://warwick.ac.uk/fac/sci/dcs/research/focs/conf2017/ Workshop webpage]

== Open Problems ==
*{{ProblemLink|90}}
*{{ProblemLink|91}}
*{{ProblemLink|92}}
*{{ProblemLink|93}}
*{{ProblemLink|94}}

Open Problems:By Number

2019-08-20T04:01:41Z

Krzysztof Onak: Adding the problems from the workshop in Warwick in 208

Waiting

2019-08-20T03:53:36Z

Krzysztof Onak:

{{DISPLAYTITLE:Waiting Room}}
Submitting a new problem:
# Make sure your problem is not yet on [[Open_Problems:By_Number|the list]].
# Edit this page to add <code><nowiki>*[[Waiting:Your Problem Name|]]</nowiki></code> at the bottom. This will create a link to a page for your new problem.
# Copy the content of [[Waiting:Sample Problem]] and use it as a starting point.
# Take your time editing the problem. See also [[Editing| the page with editing guidelines]].
# Once you are satisfied with the quality of the writeup, send an email to [mailto:admin@sublinear.info admin@sublinear.info].

== Problems in Preparation ==

*[[Waiting:Sample Problem|Sample Problem]] ← Please do not remove or edit!

The Warwick workshop:

*[[Open_Problems:90]]
*[[Open_Problems:91]]
*[[Open_Problems:92]]
*[[Open_Problems:93]]
*[[Open_Problems:94]]

WoLA'19:
*[[Waiting:Non-Adaptive Group Testing]]
*[[Waiting:Identity Testing Up to Coarsenings]]
*[[Waiting:Local Computation Algorithm for MIS]]
*[[Waiting:Estimating a Graph's Degree Distribution]]
*[[Waiting:Vertex-Distribution-Free Graph Testing]]
*[[Waiting:Effective Support Size Estimation in the Dual Model]]
*[[Waiting:Vertex connectivity in the LOCAL model]]
*[[Waiting:Making edges happy in the LOCAL model]]

Open Problems:94

2019-08-20T03:53:24Z

Krzysztof Onak: Krzysztof Onak moved page Waiting:Ads Impressions and Statistics to Open Problems:94 without leaving a redirect

{{Header
|source=warwick18
}}
1. Consider the problem of reporting statistics about online ads to the advertisers that pay for them. Advertisers may wish to know how many unique people matching some demographic conditions have seen an ad at a particular time range. There are many ads and many demographic conditions and time ranges; and the service provider should be able to accurately answer any possible query over ads, demographics, and time. In other words, it’s an [https://en.wikipedia.org/wiki/OLAP_cube OLAP cube] problem where the aggregate is ''distinct count'' rather than ''sum''. How can one construct a sketch that will provide estimates with "good" errors that solves this with, say, $O(1)$ time complexity per query? Loosely speaking, "good" here means every query for an ad (without demographic conditions) has good relative error and any query that has a high count should have good relative error.

2. Suppose a company tracks an important high level metric ''(e.g., total network traffic)'' that is the sum of a metric over many discrete categories ''(e.g., country, device, network provider, etc.)''. When that metric changes in an unexpected way, it wishes to figure out what combinations of categories are driving that change. How can one find a small set of combination of categories that explains most of the change and can be described succinctly? Can this be done in real-time so that a streaming sketch can keep track of the appropriate approximate aggregates and the search for a succinct description of category can be done in "reasonable" time?

Open Problems:94

2019-08-20T03:53:10Z

Krzysztof Onak: Updating the header

{{Header
|source=warwick18
}}
1. Consider the problem of reporting statistics about online ads to the advertisers that pay for them. Advertisers may wish to know how many unique people matching some demographic conditions have seen an ad at a particular time range. There are many ads and many demographic conditions and time ranges; and the service provider should be able to accurately answer any possible query over ads, demographics, and time. In other words, it’s an [https://en.wikipedia.org/wiki/OLAP_cube OLAP cube] problem where the aggregate is ''distinct count'' rather than ''sum''. How can one construct a sketch that will provide estimates with "good" errors that solves this with, say, $O(1)$ time complexity per query? Loosely speaking, "good" here means every query for an ad (without demographic conditions) has good relative error and any query that has a high count should have good relative error.

2. Suppose a company tracks an important high level metric ''(e.g., total network traffic)'' that is the sum of a metric over many discrete categories ''(e.g., country, device, network provider, etc.)''. When that metric changes in an unexpected way, it wishes to figure out what combinations of categories are driving that change. How can one find a small set of combination of categories that explains most of the change and can be described succinctly? Can this be done in real-time so that a streaming sketch can keep track of the appropriate approximate aggregates and the search for a succinct description of category can be done in "reasonable" time?