Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProperty testing of the Boolean and binary rank
138
0
0.0
(
0
)
Added by
Michal Parnas
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present algorithms for testing if a $(0,1)$-matrix $M$ has Boolean/binary rank at most $d$, or is $epsilon$-far from Boolean/binary rank $d$ (i.e., at least an $epsilon$-fraction of the entries in $M$ must be modified so that it has rank at most $d$). The query complexity of our testing algorithm for the Boolean rank is $tilde{O}left(d^4/ epsilon^6right)$. For the binary rank we present a testing algorithm whose query complexity is $O(2^{2d}/epsilon)$. Both algorithms are $1$-sided error algorithms that always accept $M$ if it has Boolean/binary rank at most $d$, and reject with probability at least $2/3$ if $M$ is $epsilon$-far from Boolean/binary rank $d$.
rate research
Read More
We define the Augmentation property for binary matrices with respect to different rank functions. A matrix $A$ has the Augmentation property for a given rank function, if for any subset of column vectors $x_1,...,x_t$ for for which the rank of $A$ does not increase when augmented separately with each of the vectors $x_i$, $1leq i leq t$, it also holds that the rank does not increase when augmenting $A$ with all vectors $x_1,...,x_t$ simultaneously. This property holds trivially for the usual linear rank over the reals, but as we show, things change significantly when considering the binary and boolean rank of a matrix. We prove a necessary and sufficient condition for this property to hold under the binary and boolean rank of binary matrices. Namely, a matrix has the Augmentation property for these rank functions if and only if it has a unique base that spans all other bases of the matrix with respect to the given rank function. For the binary rank, we also present a concrete characterization of a family of matrices that has the Augmentation property. This characterization is based on the possible types of linear dependencies between rows of $V$, in optimal binary decompositions of the matrix as $A=Ucdot V$. Furthermore, we use the Augmentation property to construct simple families of matrices, for which there is a gap between their real and binary rank and between their real and boolean rank.
In the subgraph-freeness problem, we are given a constant-size graph $H$, and wish to determine whether the network contains $H$ as a subgraph or not. The emph{property-testing} relaxation of the problem only requires us to distinguish graphs that are $H$-free from graphs that are $epsilon$-far from $H$-free, meaning an $epsilon$-fraction of their edges must be removed to obtain an $H$-free graph. Recently, Censor-Hillel et. al. and Fraigniaud et al. showed that in the property-testing regime it is possible to test $H$-freeness for any graph $H$ of size 4 in constant time, $O(1/epsilon^2)$ rounds, regardless of the network size. However, Fraigniaud et. al. also showed that their techniques for graphs $H$ of size 4 cannot test $5$-cycle-freeness in constant time. In this paper we revisit the subgraph-freeness problem and show that $5$-cycle-freeness, and indeed $H$-freeness for many other graphs $H$ comprising more than 4 vertices, can be tested in constant time. We show that $C_k$-freeness can be tested in $O(1/epsilon)$ rounds for any cycle $C_k$, improving on the running time of $O(1/epsilon^2)$ of the previous algorithms for triangle-freeness and $C_4$-freeness. In the special case of triangles, we show that triangle-freeness can be solved in $O(1)$ rounds independently of $epsilon$, when $epsilon$ is not too small with respect to the number of nodes and edges. We also show that $T$-freeness for any constant-size tree $T$ can be tested in $O(1)$ rounds, even without the property-testing relaxation. Building on these results, we define a general class of graphs for which we can test subgraph-freeness in $O(1/epsilon)$ rounds. This class includes all graphs over 5 vertices except the 5-clique, $K_5$. For cliques $K_s$ over $s geq 3$ nodes, we show that $K_s$-freeness can be tested in $O(m^{1/2-1/(s-2)}/epsilon^{1/2+1/(s-2)})$ rounds, where $m$ is the number of edges.
We provide a number of algorithmic results for the following family of problems: For a given binary mtimes n matrix A and integer k, decide whether there is a simple binary matrix B which differs from A in at most k entries. For an integer r, the simplicity of B is characterized as follows. - Binary r-Means: Matrix B has at most r different columns. This problem is known to be NP-complete already for r=2. We show that the problem is solvable in time 2^{O(klog k)}cdot(nm)^{O(1)} and thus is fixed-parameter tractable parameterized by k. We prove that the problem admits a polynomial kernel when parameterized by r and k but it has no polynomial kernel when parameterized by k only unless NPsubseteq coNP/poly. We also complement these result by showing that when being parameterized by r and k, the problem admits an algorithm of running time 2^{O(rcdot sqrt{klog{(k+r)}})}(nm)^{O(1)}, which is subexponential in k for rin O(k^{1/2 -epsilon}) for any epsilon>0. - Low GF(2)-Rank Approximation: Matrix B is of GF(2)-rank at most r. This problem is known to be NP-complete already for r=1. It also known to be W[1]-hard when parameterized by k. Interestingly, when parameterized by r and k, the problem is not only fixed-parameter tractable, but it is solvable in time 2^{O(r^{ 3/2}cdot sqrt{klog{k}})}(nm)^{O(1)}, which is subexponential in k. - Low Boolean-Rank Approximation: Matrix B is of Boolean rank at most r. The problem is known to be NP-complete for k=0 as well as for r=1. We show that it is solvable in subexponential in k time 2^{O(r2^rcdot sqrt{klog k})}(nm)^{O(1)}.
We study space-pass tradeoffs in graph streaming algorithms for parameter estimation and property testing problems such as estimating the size of maximum matchings and maximum cuts, weight of minimum spanning trees, or testing if a graph is connected or cycle-free versus being far from these properties. We develop a new lower bound technique that proves that for many problems of interest, including all the above, obtaining a $(1+epsilon)$-approximation requires either $n^{Omega(1)}$ space or $Omega(1/epsilon)$ passes, even on highly restricted families of graphs such as bounded-degree planar graphs. For multiple of these problems, this bound matches those of existing algorithms and is thus (asymptotically) optimal. Our results considerably strengthen prior lower bounds even for arbitrary graphs: starting from the influential work of [Verbin, Yu; SODA 2011], there has been a plethora of lower bounds for single-pass algorithms for these problems; however, the only multi-pass lower bounds proven very recently in [Assadi, Kol, Saxena, Yu; FOCS 2020] rules out sublinear-space algorithms with exponentially smaller $o(log{(1/epsilon)})$ passes for these problems. One key ingredient of our proofs is a simple streaming XOR Lemma, a generic hardness amplification result, that we prove: informally speaking, if a $p$-pass $s$-space streaming algorithm can only solve a decision problem with advantage $delta > 0$ over random guessing, then it cannot solve XOR of $ell$ independent copies of the problem with advantage much better than $delta^{ell}$. This result can be of independent interest and useful for other streaming lower bounds as well.
We consider $ell_1$-Rank-$r$ Approximation over GF(2), where for a binary $mtimes n$ matrix ${bf A}$ and a positive integer $r$, one seeks a binary matrix ${bf B}$ of rank at most $r$, minimizing the column-sum norm $||{bf A} -{bf B}||_1$. We show that for every $varepsilonin (0, 1)$, there is a randomized $(1+varepsilon)$-approximation algorithm for $ell_1$-Rank-$r$ Approximation over GF(2) of running time $m^{O(1)}n^{O(2^{4r}cdot varepsilon^{-4})}$. This is the first polynomial time approximation scheme (PTAS) for this problem.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
