Open Problems:68 - Revision history

Krzysztof Onak: Krzysztof Onak moved page Waiting:Yuichi Yoshida to Open Problems:68

2014-06-13T23:03:23Z

Krzysztof Onak moved page Waiting:Yuichi Yoshida to Open Problems:68

Krzysztof Onak at 23:03, 13 June 2014

2014-06-13T23:03:07Z

Krzysztof Onak at 03:04, 8 June 2014

2014-06-08T03:04:15Z

119.72.194.61 at 15:29, 7 June 2014

2014-06-07T15:29:18Z

119.72.199.237 at 06:28, 7 June 2014

2014-06-07T06:28:56Z

119.72.199.237 at 06:27, 7 June 2014

2014-06-07T06:27:43Z

119.72.199.237 at 06:27, 7 June 2014

2014-06-07T06:27:17Z

126.205.211.124 at 21:01, 3 June 2014

2014-06-03T21:01:13Z

126.205.211.124 at 20:59, 3 June 2014

2014-06-03T20:59:45Z

126.205.211.124: 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..."

2014-06-03T20:58:25Z

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..."

New page

{{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 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.
Hence, we can approximate the rank with $O(1/\epsilon)$ 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.
{{cite|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$.

@@ Line 1: / Line 1: @@
 {{Header
 |title=Approximating Rank in the Bounded-Degree Model
-|source=online
+|source=bertinoro14
 |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)$).
-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$.
 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 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.
-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.
 Hence, we cannot directly apply the construction to the rank problem as we only have $A$.

@@ Line 11: / Line 11: @@
 How many queries are needed for 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.
 So, we can approximate the rank with $O(1/\epsilon^2)$ queries.

@@ Line 19: / Line 19: @@
 {{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.
 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$.
+Hence, we cannot directly apply the construction to the rank problem as we only have $A$.

← Older revision	Revision as of 23:03, 13 June 2014
(No difference)