Difference between revisions of "Open Problems:68"
(Created page with "{{Header |title=Approximating Rank in the Bounded-Degree Model |source=online |who=Yuichi Yoshida }} Let $A:\mathbb{F}_p^{m \times n}$ be a matrix such that each row and colum...") |
|||
| Line 13: | Line 13: | ||
When $p = 2$ and each column has exactly two ones, $A$ can be seen as an incidence matrix, | When $p = 2$ and each column has exactly two ones, $A$ can be seen as an incidence matrix, | ||
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 general, the conjecture is $\Omega(n)$. | In general, the conjecture is $\Omega(n)$. | ||
Revision as of 20:59, 3 June 2014
| Suggested by | Yuichi Yoshida |
|---|---|
| Source | submitted online |
| 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$ is given as a query access: 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 whithin $\pm \epsilon$. How many queries are needed for this task?
When $p = 2$ and each column has exactly two ones, $A$ can be seen as an incidence matrix, 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 general, the conjecture is $\Omega(n)$. The difficulty is that not so many techniques are known to show $\Omega(n)$ lower bound for the bounded-degree model. [BogdanovOT-02] shows a lower bound of $\Omega(n)$ for the problem of solving E3LIN2 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 use the construction for the rank problem as we only have $A$.
