Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRank and fooling set size
265
0
0.0
(
0
)
Added by
Troy Lee
Publication date
2013
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We give a pseudorandom generator that fools $m$-facet polytopes over ${0,1}^n$ with seed length $mathrm{polylog}(m) cdot log n$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any ${0,1}$-integer program.
Let $f: {0,1}^n to {0, 1}$ be a boolean function, and let $f_land (x, y) = f(x land y)$ denote the AND-function of $f$, where $x land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_land$ and show that, up to a $log n$ factor, it is bounded by a polynomial in the logarithm of the real rank of the communication matrix of $f_land$. This comes within a $log n$ factor of establishing the log-rank conjecturefor AND-functions with no assumptions on $f$. Our result stands in contrast with previous results on special cases of the log-rank conjecture, which needed significant restrictions on $f$ such as monotonicity or low $mathbb{F}_2$-degree. Our techniques can also be used to prove (within a $log n$ factor) a lifting theorem for AND-functions, stating that the deterministic communication complexity of $f_land$ is polynomially-related to the AND-decision tree complexity of $f$. The results rely on a new structural result regarding boolean functions $f:{0, 1}^n to {0, 1}$ with a sparse polynomial representation, which may be of independent interest. We show that if the polynomial computing $f$ has few monomials then the set system of the monomials has a small hitting set, of size poly-logarithmic in its sparsity. We also establish extensions of this result to multi-linear polynomials $f:{0,1}^n to mathbb{R}$ with a larger range.
An $ntimes n$ matrix $M$ is called a textit{fooling-set matrix of size $n$} if its diagonal entries are nonzero and $M_{k,ell} M_{ell,k} = 0$ for every $k e ell$. Dietzfelbinger, Hromkovi{v{c}}, and Schnitger (1996) showed that $n le (mbox{rk} M)^2$, regardless of over which field the rank is computed, and asked whether the exponent on $mbox{rk} M$ can be improved. We settle this question. In characteristic zero, we construct an infinite family of rational fooling-set matrices with size $n = binom{mbox{rk} M+1}{2}$. In nonzero characteristic, we construct an infinite family of matrices with $n= (1+o(1))(mbox{rk} M)^2$.
Positive semidefinite rank (PSD-rank) is a relatively new quantity with applications to combinatorial optimization and communication complexity. We first study several basic properties of PSD-rank, and then develop new techniques for showing lower bounds on the PSD-rank. All of these bounds are based on viewing a positive semidefinite factorization of a matrix $M$ as a quantum communication protocol. These lower bounds depend on the entries of the matrix and not only on its support (the zero/nonzero pattern), overcoming a limitation of some previous techniques. We compare these new lower bounds with known bounds, and give examples where the new ones are better. As an application we determine the PSD-rank of (approximations of) some common matrices.
A $left(n,ell,gammaright)$-sharing set family of size $m$ is a family of sets $S_1,ldots,S_msubseteq [n]$ s.t. each set has size $ell$ and each pair of sets shares at most $gamma$ elements. We let $mleft(n,ell,gammaright)$ denote the maximum size of any such set family and we consider the following question: How large can $mleft(n,ell,gammaright)$ be? $left(n,ell,gammaright)$-sharing set families have a rich set of applications including the construction of pseudorandom number generators and usable and secure password management schemes. We analyze the explicit construction of Blocki et al using recent bounds on the value of the $t$th Ramanujan prime. We show that this explicit construction produces a $left(4ell^2ln 4ell,ell,gammaright)$-sharing set family of size $left(2 ell ln 2ellright)^{gamma+1}$ for any $ellgeq gamma$. We also show that the construction of Blocki et al can be used to obtain a weak $left(n,ell,gammaright)$-sharing set family of size $m$ for any $m >0$. These results are competitive with the inexplicit construction of Raz et al for weak $left(n,ell,gammaright)$-sharing families. We show that our explicit construction of weak $left(n,ell,gammaright)$-sharing set families can be used to obtain a parallelizable pseudorandom number generator with a low memory footprint by using the pseudorandom number generator of Nisan and Wigderson. We also prove that $mleft(n,n/c_1,c_2nright)$ must be a constant whenever $c_2 leq frac{2}{c_1^3+c_1^2}$. We show that this bound is nearly tight as $mleft(n,n/c_1,c_2nright)$ grows exponentially fast whenever $c_2 > c_1^{-2}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
