Open Problems in Sublinear Algorithms - User contributions [en]

Waiting

2021-09-16T21:48:39Z

Szhou: /* Problems in Preparation */

{{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!
*[[Waiting:Cyclic Hash Functions for Edit Distance|Cyclic Hash Functions for Edit Distance]]
*[[Waiting:Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing|Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing]]
*[[Waiting:Estimating Arboricity on Data Streams|Estimating Arboricity on Data Streams]]

Waiting

2021-09-16T21:48:16Z

Szhou: /* Problems in Preparation */

{{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!
*[[Waiting:Streaming Algorithms for Geometric Steiner Forest|Streaming Algorithms for Geometric Steiner Forest]]
*[[Waiting:Cyclic Hash Functions for Edit Distance|Cyclic Hash Functions for Edit Distance]]
*[[Waiting:Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing|Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing]]
*[[Waiting:Estimating Arboricity on Data Streams|Estimating Arboricity on Data Streams]]

Waiting

2021-09-16T21:39:15Z

Szhou: /* Problems in Preparation */

{{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!
*[[Waiting:Streaming Algorithms for Geometric Steiner Forest|Streaming Algorithms for Geometric Steiner Forest]]
*[[Waiting:Cyclic Hash Functions for Edit Distance|Cyclic Hash Functions for Edit Distance]]
*[[Waiting:Multi-pass Space Complexity for Max-CUT|Multi-pass Space Complexity for Max-CUT]]
*[[Waiting:Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing|Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing]]
*[[Waiting:Estimating Arboricity on Data Streams|Estimating Arboricity on Data Streams]]

Waiting

2021-09-16T21:35:36Z

Szhou: /* Problems in Preparation */

{{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!
*[[Waiting:Cyclic Hash Functions for Edit Distance|Cyclic Hash Functions for Edit Distance]]
*[[Waiting:Multi-pass Space Complexity for Max-CUT|Multi-pass Space Complexity for Max-CUT]]
*[[Waiting:Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing|Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing]]
*[[Waiting:Estimating Arboricity on Data Streams|Estimating Arboricity on Data Streams]]

Waiting:Dimensionality Reduction for Clustering on the Hamming Cube

2021-09-16T21:33:50Z

Szhou: Blanked the page

Waiting:Estimating Arboricity on Data Streams

2021-09-16T21:03:54Z

Szhou: Created page with "{{Header |title=Estimating Arboricity on Data Streams |source=WALDO 2021 |who=Talya Eden }} Is the number of primes infinite? Note that if the answer is positive, the proof ha..."

{{Header
|title=Estimating Arboricity on Data Streams
|source=WALDO 2021
|who=Talya Eden
}}
Is the number of primes infinite? Note that if the answer is positive, the proof has to be of length ''sublinear'' in the number of primes.

Waiting

2021-09-16T21:03:29Z

Szhou: /* Problems in Preparation */

{{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!
*[[Waiting:Cyclic Hash Functions for Edit Distance|Cyclic Hash Functions for Edit Distance]]
*[[Waiting:Multi-pass Space Complexity for Max-CUT|Multi-pass Space Complexity for Max-CUT]]
*[[Waiting:Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing|Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing]]
*[[Waiting:Dimensionality Reduction for Clustering on the Hamming Cube|Dimensionality Reduction for Clustering on the Hamming Cube]]
*[[Waiting:Estimating Arboricity on Data Streams|Estimating Arboricity on Data Streams]]

Waiting:Dimensionality Reduction for Clustering on the Hamming Cube

2021-09-16T20:57:56Z

Szhou: Created page with "{{Header |title=Dimensionality Reduction for Clustering on the Hamming Cube |source=WALDO 2021 |who=Erik Waingarten }} Is the number of primes infinite? Note that if the answe..."

{{Header
|title=Dimensionality Reduction for Clustering on the Hamming Cube
|source=WALDO 2021
|who=Erik Waingarten
}}
Is the number of primes infinite? Note that if the answer is positive, the proof has to be of length ''sublinear'' in the number of primes.

Waiting:Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing

2021-09-16T20:56:49Z

Szhou: Created page with "{{Header |title=Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing |source=WALDO 2021 |who=Chen Wang }} Is the number of primes infinite? Note that if the ans..."

{{Header
|title=Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing
|source=WALDO 2021
|who=Chen Wang
}}
Is the number of primes infinite? Note that if the answer is positive, the proof has to be of length ''sublinear'' in the number of primes.

Waiting:Multi-pass Space Complexity for Max-CUT

2021-09-16T20:55:39Z

Szhou: Created page with "{{Header |title=Multi-pass Space Complexity for Max-CUT |source=WALDO 2021 |who=Santhoshini Velusamy }} Is the number of primes infinite? Note that if the answer is positive,..."

{{Header
|title=Multi-pass Space Complexity for Max-CUT
|source=WALDO 2021
|who=Santhoshini Velusamy
}}
Is the number of primes infinite? Note that if the answer is positive, the proof has to be of length ''sublinear'' in the number of primes.

Waiting:Cyclic Hash Functions for Edit Distance

2021-09-16T20:54:28Z

Szhou:

{{Header
|title=Cyclic Hash Functions for Edit Distance
|source=WALDO 2021
|who=Samson Zhou
}}
Is the number of primes infinite? Note that if the answer is positive, the proof has to be of length ''sublinear'' in the number of primes.

Waiting

2021-09-16T20:53:34Z

Szhou: /* Problems in Preparation */

{{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!
*[[Waiting:Cyclic Hash Functions for Edit Distance|Cyclic Hash Functions for Edit Distance]]
*[[Waiting:Multi-pass Space Complexity for Max-CUT|Multi-pass Space Complexity for Max-CUT]]
*[[Waiting:Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing|Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing]]
*[[Waiting:Dimensionality Reduction for Clustering on the Hamming Cube|Dimensionality Reduction for Clustering on the Hamming Cube]]

Waiting:Cyclic Hash Functions for Edit Distance

2021-09-16T20:52:33Z

Szhou:

Waiting

2021-09-16T20:51:45Z

Szhou: /* Problems in Preparation */

{{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!
*[[Waiting:Cyclic Hash Functions for Edit Distance|Cyclic Hash Functions for Edit Distance]]
*[[Waiting:Cyclic Hash Functions for Edit Distance|Multi-pass Space Complexity for Max-CUT]]
*[[Waiting:Cyclic Hash Functions for Edit Distance|Sample Complexity for Streaming Multi-Armed Bandit and Coin Tossing]]
*[[Waiting:Cyclic Hash Functions for Edit Distance|Dimensionality Reduction for Clustering on the Hamming Cube]]

Waiting:Sample Problem

2021-09-16T20:45:12Z

Szhou:

{{Header
|title=The Number of Primes
|source=online
|who=Euclid
}}
Is the number of primes infinite? Note that if the answer is positive, the proof has to be of length ''sublinear'' in the number of primes.

Waiting:Cyclic Hash Functions for Edit Distance

2021-09-16T20:43:43Z

Szhou: Created page with "{{Header |title=Cyclic Hash Functions for Edit Distance |source=WALDO 2021 |who=Samson Zhou }} Is the number of primes infinite? Note that if the answer is positive, the proof..."

Waiting

2021-09-16T20:43:22Z

Szhou: /* Problems in Preparation */

Waiting:Sample Problem

2021-09-16T20:41:50Z

Szhou: