Open Problems in Sublinear Algorithms - User contributions [en]

Open Problems:67

2014-05-29T14:12:14Z

Geomblog:

{{Header
|title=Difficult Instance for MaxCut in the Streaming Model
|source=bertinoro14
|who=Robert Krauthgamer
}}

Let $G$ be a graph consisting of a cycle of length $n$ and a random matching. It is known that this graph is
* an expander
* not bipartite

Let $G'$ be a graph consisting of a cycle of length $n$ and a random matching, with the constraint that the matching must consist only of "even chords": these are chords that are an even number of vertices apart on the cycle. It is easy to see now that this graph is bipartite.

We can say two more things about $G$ and $G'$.

# $G$ is very far from being bipartite:
# $G$ has a max cut of size $n$ and $G'$ does not have a max cut bigger than (say) $0.99n$.

How much space is required to distinguish between these two graphs in a streaming setting ?

Open Problems:66

2014-05-29T14:05:05Z

Geomblog:

{{Header
|title=Distinguishing Distributions with Conditional Samples
|source=bertinoro14
|who=Eldar Fischer
}}

Suppose we're given access to two distributions $P$ and $Q$ over $[1 \ldots n]$ and wish to test if they are the same or are at least $\epsilon$ apart under the $\ell_1$ distance. Assume that we have access to ''conditional samples'': in other words, a query consists of a set $S \subset [1..n]$ and the output is a sample drawn from the conditional distribution on $A$. In other words, a conditional sample on $P$ given $S$ is drawn from the distribution where

$$ \text{Pr}(j) = \begin{cases} \frac{p_j}{\sum_{i \in A} p_i} & j \in A \\ 0 & \text{otherwise} \end{cases} $$

It is known that if one of the distributions is fixed, then a constant ($f(1/\epsilon)$) number of queries suffice to test the distributions.

What can we say if both distributions are unknown ?

Open Problems:66

2014-05-29T14:04:36Z

Geomblog:

{{Header
|title=Distinguishing Distributions with Conditional Samples
|source=bertinoro14
|who=Eldar Fischer
}}

Suppose we're given access to two distributions $P$ and $Q$ over $[1 \ldots n]$ and wish to test if they are the same or are at least $\epsilon$ apart under the $\ell_1$ distance. Assume that we have access to ''conditional samples'': in other words, a query consists of a set $S \subset [1..n]$ and the output is a sample drawn from the conditional distribution on $A$. In other words, a conditional sample on $P$ given $S$ is drawn from the distribution where

$$ \text{Pr}(j) = \begin{cases} p_j / \sum_{i \in A} p_i & j \in A \\ 0 & \text{otherwise} \end{cases} $$

It is known that if one of the distributions is fixed, then a constant ($f(1/\epsilon)$) number of queries suffice to test the distributions.

What can we say if both distributions are unknown ?

Open Problems:66

2014-05-29T14:03:06Z

Geomblog:

{{Header
|title=Distinguishing Distributions with Conditional Samples
|source=bertinoro14
|who=Eldar Fischer
}}

Suppose we're given access to two distributions $P$ and $Q$ over $[1 \ldots n]$ and wish to test if they are the same or are at least $\epsilon$ apart under the $\ell_1$ distance. Assume that we have access to ''conditional samples'': in other words, a query consists of a set $S \subset [1..n]$ and the output is a sample drawn from the conditional distribution on $A$. In other words, a conditional sample on $P$ given $S$ is drawn from the distribution where

$$ \text{Pr}(j) = \begin{array} p_j / \sum_{i \in A} p_i & j \in A \\ 0 & \text{otherwise} \end{array} $$

It is known that if one of the distributions is fixed, then a constant ($f(1/\epsilon)$) number of queries suffice to test the distributions.

What can we say if both distributions are unknown ?

Open Problems:66

2014-05-29T12:41:46Z

Geomblog:

{{Header
|title=Distinguishing Distributions with Conditional Samples
|source=bertinoro14
|who=Eldar Fischer
}}

Suppose we're given access to two distributions $P$ and $Q$ over $[1 \ldots n]$ and wish to test if they are the same or are at least $\epsilon$ apart under the $\ell_1$ distance. Assume that we have access to ''conditional samples'': in other words, a query consists of a set $S \subset [1..n]$ and the output is a sample drawn from the conditional distribution on $A$. In other words, a conditional sample on $P$ given $S$ is drawn from the distribution where

\[ \text{Pr}(j) = \begin{array} p_j / \sum_{i \in A} p_i & j \in A \\ 0 & \text{otherwise} \end{array} \]

It is known that if one of the distributions is fixed, then a constant ($f(1/\epsilon)$) number of queries suffice to test the distributions.

What can we say if both distributions are unknown ?

Open Problems:66

2014-05-29T12:41:20Z

Geomblog:

{{Header
|title=Distinguishing Distributions with Conditional Samples
|source=bertinoro14
|who=Eldar Fischer
}}

Suppose we're given access to two distributions $P$ and $Q$ over $[1 \ldots n]$ and wish to test if they are the same or are at least $\epsilon$ apart under the $\ell_1$ distance. Assume that we have access to ''conditional samples'': in other words, a query consists of a set $S \subset [1..n]$ and the output is a sample drawn from the conditional distribution on $A$. In other words, a conditional sample on $P$ given $S$ is drawn from the distribution where

\[ \text{Pr}(j) = \begin{array} \frac{p_j}{\sum_{i \in A} p_i} & j \in A \\ 0 & \text{otherwise} \end{array} \]

It is known that if one of the distributions is fixed, then a constant ($f(1/\epsilon)$) number of queries suffice to test the distributions.

What can we say if both distributions are unknown ?

Open Problems:65

2014-05-28T21:43:43Z

Geomblog:

{{Header
|title=Communication Complexity of Connectivity
|source=bertinoro14
|who=Andrew McGregor
}}
In the sketch-based algorithms for connectivity on a graph, the procedure works as follows. Each vertex prepares a $\log^3n$-sized sketch describing its neighborhood, and sends it to a controller. Each node has access to a public shared random source to compute this sketch.

Can we reduce the number of bits required by each node ? To $\log^2 n$ ? To $\log n$ ?

Open Problems:64

2014-05-28T21:41:43Z

Geomblog:

{{Header
|title=Matchings in the Turnstile Model
|source=bertinoro14
|who=Andrew McGregor
}}

Suppose we are in a turnstile model for graph streaming: this means that the stream consists of a sequence of edge insertions and deletions (with no edge being deleted before it's inserted). In this setting, can we design an algorithm for computing a matching that takes space $o(n^2)$ and gets a constant approximation (or better ) ?

Open Problems:63

2014-05-28T21:39:23Z

Geomblog:

{{Header
|title=Submodular Matching Maximization
|source=bertinoro14
|who=Amit Chakrabarti
}}

Let $G = (V, E)$ be a graph. Fix a monotone submodular function $f : 2^E \rightarrow \mathbb{R}$. A maximum submodular matching $M$ is a subset of $E$ that forms a matching and maximizes $f(E)$.

Suppose the graph edges are streaming. It is known that we cannot compute a maximum weight matching in one pass and $n \text{poly}\log n$ space to a better approximation than $\frac{e}{e-1}$. Can we show a stronger lower bound for maximum ''submodular'' matchings ?

A conjecture is that it will be hard to get a better than 2-approximation in one pass with the same space constraints.

A related question (due to Deeparnab Chakrabarty): Is there an instance-wise gap between MWMs and MSMs in the stream setting ?

Waiting

2014-05-28T21:31:59Z

Geomblog: /* 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!

Bertinoro 2014 Problems:
*[[Waiting:Qin Zhang|RNA Folding]]
*[[Waiting:Andrea Montanari|PCAs with nonnegativity constraints]]
*[[Waiting:Amit Chakrabarti|Submodular Matching Maximization]]
*[[Waiting:Andrew McGregor|Matchings in the Turnstile Model]]
*[[Waiting:Andrew McGregor2|Communication Complexity of Connectivity]]
*[[Waiting:Ely Porat|???]]
*[[Waiting:Ely Porat2|???]]
*[[Waiting:Eldar Fischer|Distinguishing Distributions with Conditional Samples]]
*[[Waiting:Robert Krauthgamer|Difficult Instance for MaxCut in the Streaming Model]]

Open Problems:62

2014-05-28T21:30:51Z

Geomblog:

{{Header
|title=PCAs with nonnegativity constraints
|source=bertinoro14
|who=Andrea Montanari
}}

Given a symmetric matrix $A$, we can think of PCA as maximizing $x^\top A x$ subject to $\|x\|=1$. If we also add the condition $x \ge 0$, this problem becomes NP-hard.
We can define a convex relaxation:

\[ \max Tr(WA) \ \text{s.t}\ Tr(W) = 1, W \ge 0, W \succeq 0 \]

Suppose that $A$ is a random matrix: in particular, set $A_{ij}$ to be i.i.d $N(0,1)$. Then empirical results show that the resulting $W$ is a rank-1 matrix, which means that we recover the optimal $x$ exactly.

Is this true in general ? Note that we can prove that the solution is rank 1 if $A = v v^T + $ small amounts of noise.

Open Problems:62

2014-05-28T21:30:08Z

Geomblog:

{{Header
|title=PCAs
|source=bertinoro14
|who=Andrea Montanari
}}

Given a symmetric matrix $A$, we can think of PCA as maximizing $x^\top A x$ subject to $\|x\|=1$. If we also add the condition $x \ge 0$, this problem becomes NP-hard.
We can define a convex relaxation:

\[ \max Tr(WA) \ \text{s.t}\ Tr(W) = 1, W \ge 0, W \succeq 0 \]

Suppose that $A$ is a random matrix: in particular, set $A_{ij}$ to be i.i.d $N(0,1)$. Then empirical results show that the resulting $W$ is a rank-1 matrix, which means that we recover the optimal $x$ exactly.

Is this true in general ? Note that we can prove that the solution is rank 1 if $A = v v^T + $ small amounts of noise.

Open Problems:62

2014-05-28T21:29:17Z

Geomblog:

{{Header
|title=PCAs
|source=bertinoro14
|who=Andrea Montanari
}}

Given a symmetric matrix $A$, we can think of PCA as maximizing $x^\top A x$ subject to $\|x\|=1$. If we also add the condition $x \ge 0$, this problem becomes NP-hard.
We can define a convex relaxation:

\[ \max Tr(WA) \text{\ s.t\ } Tr(W) = 1, W \ge 0, W \succeq 0 \]

Suppose that $A$ is a random matrix: in particular, set $A_{ij} to be i.i.d $N(0,1)$. Then empirical results show that the resulting $W$ is a rank-1 matrix, which means that we recover the optimal $x$ exactly.

Is this true in general ? Note that we can prove that the solution is rank 1 if $A = v v^T + $ small amounts of noise.

Open Problems:62

2014-05-28T21:27:29Z

Geomblog:

Open Problems:61

2014-05-28T17:21:38Z

Geomblog:

{{Header
|title=RNA Folding
|source=bertinoro14
|who=Qin Zhang
}}

An RNA sequence is a string of letters from the alphabet {A, C, G, U}, where A-U and C-G form pairings. A set of pairings in such a string is said to be non-crossing if there are no pairs of the form $(i, j), (k, l)$ where $i < k < j$.

A maximum non-crossing matching is a pairing of A-U and C-G of maximum cardinality that is non-crossing. Given a string, such a matching can be computed in $n^2$ space and $n^3$ time via dynamic programming.

Note that there is a trivial 2-approximation to the optimal matching. Find the optimal matchings on the A, U and C, G subsequences, and take the larger one. This can be computed in a stream.

Is there a streaming algorithm that yields a factor better than 2 ?

Workshops:Bertinoro 2014

2014-05-28T15:23:42Z

Geomblog: /* Open Problems */

{{DISPLAYTITLE:Bertinoro Workshop on Sublinear Algorithms 2014}}
The workshop was held in Bertinoro in May 2014. Many open problems and research directions were discussed at the workshop or were posed during presentations.  The original list of open problems was scribed by Alexandr Andoni and Suresh Venkatasubramanian. Further information can be found at [http://www.wisdom.weizmann.ac.il/~robi/Bertinoro2014_SublinearAlgorithms/ the workshop webpage].

== Links ==
* [http://www.wisdom.weizmann.ac.il/~robi/Bertinoro2014_SublinearAlgorithms/ Workshop webpage]

== Open Problems ==
''this is a temporary dump of the open problems.''

== Workshop Participants ==

* Alexandr Andoni
* Vladimir Braverman
* Amit Chakrabarti
* Deeparnab Chakrabarty
* Venkat Chandrasekaran
* Moses Charikar
* Shiri Chechik
* Graham Cormode
* Artur Czumaj
* Mark Davenport
* Danny Feldman
* Eldar Fischer
* Elena Grigorescu
* Venkat Guruswami
* Piotr Indyk
* Valerie King
* Robert Krauthgamer
* Edo Liberty
* Michael Mahoney
* Claire Mathieu
* Andrew McGregor
* Andrea Montanari
* Jelani Nelson
* Ilan Newman
* Ryan O'Donnell
* Krzysztof Onak
* Ely Porat
* Eric Price
* Sofya Raskhodnikova
* Philippe Rigollet
* Ronitt Rubinfeld
* Shubhangi Saraf
* Christian Sohler
* Greg Valiant
* Paul Valiant
* Suresh Venkatasubramanian
* Rachel Ward
* David Woodruff
* Yuichi Yoshida
* Qin Zhang

Workshops:Bertinoro 2014

2014-05-28T15:21:53Z

Geomblog:

{{DISPLAYTITLE:Bertinoro Workshop on Sublinear Algorithms 2014}}
The workshop was held in Bertinoro in May 2014. Many open problems and research directions were discussed at the workshop or were posed during presentations.  The original list of open problems was scribed by Alexandr Andoni and Suresh Venkatasubramanian. Further information can be found at [http://www.wisdom.weizmann.ac.il/~robi/Bertinoro2014_SublinearAlgorithms/ the workshop webpage].

== Links ==
* [http://www.wisdom.weizmann.ac.il/~robi/Bertinoro2014_SublinearAlgorithms/ Workshop webpage]

== Open Problems ==
**this is a temporary dump of the open problems**

== Workshop Participants ==

* Alexandr Andoni
* Vladimir Braverman
* Amit Chakrabarti
* Deeparnab Chakrabarty
* Venkat Chandrasekaran
* Moses Charikar
* Shiri Chechik
* Graham Cormode
* Artur Czumaj
* Mark Davenport
* Danny Feldman
* Eldar Fischer
* Elena Grigorescu
* Venkat Guruswami
* Piotr Indyk
* Valerie King
* Robert Krauthgamer
* Edo Liberty
* Michael Mahoney
* Claire Mathieu
* Andrew McGregor
* Andrea Montanari
* Jelani Nelson
* Ilan Newman
* Ryan O'Donnell
* Krzysztof Onak
* Ely Porat
* Eric Price
* Sofya Raskhodnikova
* Philippe Rigollet
* Ronitt Rubinfeld
* Shubhangi Saraf
* Christian Sohler
* Greg Valiant
* Paul Valiant
* Suresh Venkatasubramanian
* Rachel Ward
* David Woodruff
* Yuichi Yoshida
* Qin Zhang

Workshops:Bertinoro 2014

2014-05-28T14:07:25Z

Geomblog:

{{DISPLAYTITLE:Bertinoro Workshop on Sublinear Algorithms 2014}}
The workshop was held in Bertinoro in May 2014. Many open problems and research directions were discussed at the workshop or were posed during presentations.  The original list of open problems was scribed by Alexandr Andoni and Suresh Venkatasubramanian. Further information can be found at [http://www.wisdom.weizmann.ac.il/~robi/Bertinoro2014_SublinearAlgorithms/ the workshop webpage].

== Links ==
* [http://www.wisdom.weizmann.ac.il/~robi/Bertinoro2014_SublinearAlgorithms/ Workshop webpage]

== Open Problems ==

== Workshop Speakers ==

* Alexandr Andoni
* Vladimir Braverman
* Amit Chakrabarti
* Deeparnab Chakrabarty
* Venkat Chandrasekaran
* Moses Charikar
* Shiri Chechik
* Graham Cormode
* Artur Czumaj
* Mark Davenport
* Danny Feldman
* Eldar Fischer
* Elena Grigorescu
* Venkat Guruswami
* Piotr Indyk
* Valerie King
* Robert Krauthgamer
* Edo Liberty
* Michael Mahoney
* Claire Mathieu
* Andrew McGregor
* Andrea Montanari
* Jelani Nelson
* Ilan Newman
* Ryan O'Donnell
* Krzysztof Onak
* Ely Porat
* Eric Price
* Sofya Raskhodnikova
* Philippe Rigollet
* Ronitt Rubinfeld
* Shubhangi Saraf
* Christian Sohler
* Greg Valiant
* Paul Valiant
* Suresh Venkatasubramanian
* Rachel Ward
* David Woodruff
* Yuichi Yoshida
* Qin Zhang

Workshops:Bertinoro 2014

2014-05-28T14:07:02Z

Geomblog: /* Workshop Speakers */

{{DISPLAYTITLE:Bertinoro Workshop on Sublinear algorithms 2014}}
The workshop was held in Bertinoro in May 2014. Many open problems and research directions were discussed at the workshop or were posed during presentations.  The original list of open problems was scribed by Alexandr Andoni and Suresh Venkatasubramanian. Further information can be found at [http://www.wisdom.weizmann.ac.il/~robi/Bertinoro2014_SublinearAlgorithms/ the workshop webpage].

== Links ==
* [http://www.wisdom.weizmann.ac.il/~robi/Bertinoro2014_SublinearAlgorithms/ Workshop webpage]

== Open Problems ==

== Workshop Speakers ==

* Alexandr Andoni
* Vladimir Braverman
* Amit Chakrabarti
* Deeparnab Chakrabarty
* Venkat Chandrasekaran
* Moses Charikar
* Shiri Chechik
* Graham Cormode
* Artur Czumaj
* Mark Davenport
* Danny Feldman
* Eldar Fischer
* Elena Grigorescu
* Venkat Guruswami
* Piotr Indyk
* Valerie King
* Robert Krauthgamer
* Edo Liberty
* Michael Mahoney
* Claire Mathieu
* Andrew McGregor
* Andrea Montanari
* Jelani Nelson
* Ilan Newman
* Ryan O'Donnell
* Krzysztof Onak
* Ely Porat
* Eric Price
* Sofya Raskhodnikova
* Philippe Rigollet
* Ronitt Rubinfeld
* Shubhangi Saraf
* Christian Sohler
* Greg Valiant
* Paul Valiant
* Suresh Venkatasubramanian
* Rachel Ward
* David Woodruff
* Yuichi Yoshida
* Qin Zhang

Workshops:Bertinoro 2014

2014-05-28T14:05:27Z

Geomblog:

Workshops:Bertinoro 2014

2014-05-28T14:04:41Z

Geomblog:

Workshops:Bertinoro 2014

2014-05-28T14:01:52Z

Geomblog: Created page with "{{DISPLAYTITLE:Bertinoro Workshop on Sublinear algorithms 2014}} The workshop was held in Bertinoro in May 2014. Many open problems and research directions were discussed at t..."