Difference between revisions of "Open Problems:68"

From Open Problems in Sublinear Algorithms
Jump to: navigation, search
m (Krzysztof Onak moved page Waiting:Yuichi Yoshida to Open Problems:68)
 
(3 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
{{Header
 
{{Header
|title=Approximating Rank in the Bounded-Degree Model
+
|source=bertinoro14
|source=online
 
 
|who=Yuichi Yoshida
 
|who=Yuichi Yoshida
 
}}
 
}}
 
Let $A:\mathbb{F}_p^{m \times n}$ be a matrix such that each row and column has a constant number of non-zero entries (hence, $m = O(n)$).
 
Let $A:\mathbb{F}_p^{m \times n}$ be a matrix such that each row and column has a constant number of non-zero entries (hence, $m = O(n)$).
The matrix $A$ is given as a query access:
+
The matrix $A$ can be accessed via the following types of queries.
 
If we specify the $i$-th row, then we obtain the indices $j$ for which $A_{i,j} \neq 0$.
 
If we specify the $i$-th row, then we obtain the indices $j$ for which $A_{i,j} \neq 0$.
 
Similarly, if we specify the $j$-th column, then we obtain the indices $i$ for which $A_{i,j}\neq 0$.
 
Similarly, if we specify the $j$-th column, then we obtain the indices $i$ for which $A_{i,j}\neq 0$.
For a parameter $\epsilon > 0$, we want to approximate the rank of $A$ to whithin $\pm \epsilon n$.
+
For a parameter $\epsilon > 0$, we want to approximate the rank of $A$ to within $\pm \epsilon n$.
How many queries are needed for this task?
+
How many queries are needed to accomplish this task?
  
When $p = 2$ and each column has exactly two ones, $A$ can be seen as the incidence matrix of a graph,
+
When $p = 2$ and each row has exactly two ones, $A$ can be seen as the incidence matrix of a graph,
 
and its rank is equal to $n - c$, where $c$ is the number of connected components.
 
and its rank is equal to $n - c$, where $c$ is the number of connected components.
So, we can approximate the rank with $O(1/\epsilon^2)$ queries.
+
In this case, the rank can be approximated efficiently, with $\tilde O(1/\epsilon^2)$ queries, because we know how to efficiently approximate $c$ {{cite|ChazelleRT-05}}.
  
In general, the conjecture is $\Omega(n)$.
+
In general, we conjecture that $\Omega(n)$ queries are necessary.
The difficulty is that not so many techniques are known to show $\Omega(n)$ lower bound for the bounded-degree model.
+
The difficulty in showing this lower bound arises from the fact that few techniques for proving $\Omega(n)$ lower bounds for the bounded-degree model are known.
{{cite|BogdanovOT-02}} shows a lower bound of $\Omega(n)$ for the problem of testing the satisfiability of E3LIN2 instances in the bounded-degree model.
+
Bogdanov, Obata, and Trevisan {{cite|BogdanovOT-02}} show a lower bound of $\Omega(n)$ for the problem of testing the satisfiability of '''E3LIN-2''' instances in the bounded-degree model.
 
However, the lower bound is obtained by considering a distribution of instances of the form $Ax = b$, where $A$ is fixed and $b$ is random.
 
However, the lower bound is obtained by considering a distribution of instances of the form $Ax = b$, where $A$ is fixed and $b$ is random.
 
Hence, we cannot directly apply the construction to the rank problem as we only have $A$.
 
Hence, we cannot directly apply the construction to the rank problem as we only have $A$.

Latest revision as of 23:03, 13 June 2014

Suggested by Yuichi Yoshida
Source Bertinoro 2014
Short link https://sublinear.info/68

Let $A:\mathbb{F}_p^{m \times n}$ be a matrix such that each row and column has a constant number of non-zero entries (hence, $m = O(n)$). The matrix $A$ can be accessed via the following types of queries. If we specify the $i$-th row, then we obtain the indices $j$ for which $A_{i,j} \neq 0$. Similarly, if we specify the $j$-th column, then we obtain the indices $i$ for which $A_{i,j}\neq 0$. For a parameter $\epsilon > 0$, we want to approximate the rank of $A$ to within $\pm \epsilon n$. How many queries are needed to accomplish this task?

When $p = 2$ and each row has exactly two ones, $A$ can be seen as the incidence matrix of a graph, and its rank is equal to $n - c$, where $c$ is the number of connected components. In this case, the rank can be approximated efficiently, with $\tilde O(1/\epsilon^2)$ queries, because we know how to efficiently approximate $c$ [ChazelleRT-05].

In general, we conjecture that $\Omega(n)$ queries are necessary. The difficulty in showing this lower bound arises from the fact that few techniques for proving $\Omega(n)$ lower bounds for the bounded-degree model are known. Bogdanov, Obata, and Trevisan [BogdanovOT-02] show a lower bound of $\Omega(n)$ for the problem of testing the satisfiability of E3LIN-2 instances in the bounded-degree model. However, the lower bound is obtained by considering a distribution of instances of the form $Ax = b$, where $A$ is fixed and $b$ is random. Hence, we cannot directly apply the construction to the rank problem as we only have $A$.