Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe square root rank of the correlation polytope is exponential
248
0
0.0
(
0
)
Added by
Zhaohui Wei
Publication date
2014
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
The square root rank of a nonnegative matrix $A$ is the minimum rank of a matrix $B$ such that $A=B circ B$, where $circ$ denotes entrywise product. We show that the square root rank of the slack matrix of the correlation polytope is exponential. Our main technique is a way to lower bound the rank of certain matrices under arbitrary sign changes of the entries using properties of the roots of polynomials in number fields. The square root rank is an upper bound on the positive semidefinite rank of a matrix, and corresponds the special case where all matrices in the factorization are rank-one.
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.
We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on $n$-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than $2^{n^c}$, for some constant $c > 0$. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes. Our results follow from a general technique for proving lower bounds on the positive semidefinite rank of a matrix. To this end, we establish a close connection between arbitrary SDPs and those arising from the sum-of-squares SDP hierarchy. For approximating maximum constraint satisfaction problems, we prove that SDPs of polynomial-size are equivalent in power to those arising from degree-$O(1)$ sum-of-squares relaxations. This result implies, for instance, that no family of polynomial-size SDP relaxations can achieve better than a 7/8-approximation for MAX-3-SAT.
The problem of tolerant junta testing is a natural and challenging problem which asks if the property of a function having some specified correlation with a $k$-Junta is testable. In this paper we give an affirmative answer to this question: We show that given distance parameters $frac{1}{2} >c_u>c_{ell} ge 0$, there is a tester which given oracle access to $f:{-1,1}^n rightarrow {-1,1}$, with query complexity $ 2^k cdot mathsf{poly}(k,1/|c_u-c_{ell}|)$ and distinguishes between the following cases: $mathbf{1.}$ The distance of $f$ from any $k$-junta is at least $c_u$; $mathbf{2.}$ There is a $k$-junta $g$ which has distance at most $c_ell$ from $f$. This is the first non-trivial tester (i.e., query complexity is independent of $n$) which works for all $1/2 > c_u > c_ell ge 0$. The best previously known results by Blais emph{et~ al.}, required $c_u ge 16 c_ell$. In fact, with the same query complexity, we accomplish the stronger goal of identifying the most correlated $k$-junta, up to permutations of the coordinates. We can further improve the query complexity to $mathsf{poly}(k, 1/|c_u-c_{ell}|)$ for the (weaker) task of distinguishing between the following cases: $mathbf{1.}$ The distance of $f$ from any $k$-junta is at least $c_u$. $mathbf{2.}$ There is a $k$-junta $g$ which is at a distance at most $c_ell$ from $f$. Here $k=O(k^2/|c_u-c_ell|)$. Our main tools are Fourier analysis based algorithms that simulate oracle access to influential coordinates of functions.
Say that A is a Hadamard factorization of the identity I_n of size n if the entrywise product of A and the transpose of A is I_n. It can be easily seen that the rank of any Hadamard factorization of the identity must be at least sqrt{n}. Dietzfelbinger et al. raised the question if this bound can be achieved, and showed a boolean Hadamard factorization of the identity of rank n^{0.792}. More recently, Klauck and Wolf gave a construction of Hadamard factorizations of the identity of rank n^{0.613}. Over finite fields, Friesen and Theis resolved the question, showing for a prime p and r=p^t+1 a Hadamard factorization of the identity A of size r(r-1)+1 and rank r over F_p. Here we resolve the question for fields of zero characteristic, up to a constant factor, giving a construction of Hadamard factorizations of the identity of rank r and size (r+1)r/2. The matrices in our construction are blockwise Toeplitz, and have entries whose magnitudes are binomial coefficients.
We prove that for every $n$-vertex graph $G$, the extension complexity of the correlation polytope of $G$ is $2^{O(mathrm{tw}(G) + log n)}$, where $mathrm{tw}(G)$ is the treewidth of $G$. Our main result is that this bound is tight for graphs contained in minor-closed classes.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
