Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSharper bounds on the Fourier concentration of DNFs
77
0
0.0
(
0
)
Added by
Victor Lecomte
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In 1992 Mansour proved that every size-$s$ DNF formula is Fourier-concentrated on $s^{O(loglog s)}$ coefficients. We improve this to $s^{O(loglog k)}$ where $k$ is the read number of the DNF. Since $k$ is always at most $s$, our bound matches Mansours for all DNFs and strengthens it for small-read ones. The previous best bound for read-$k$ DNFs was $s^{O(k^{3/2})}$. For $k$ up to $tilde{Theta}(loglog s)$, we further improve our bound to the optimal $mathrm{poly}(s)$; previously no such bound was known for any $k = omega_s(1)$. Our techniques involve new connections between the term structure of a DNF, viewed as a set system, and its Fourier spectrum.
rate research
Read More
Given a Boolean function $f:{-1,1}^nto {-1,1}$, the Fourier distribution assigns probability $widehat{f}(S)^2$ to $Ssubseteq [n]$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai asks if there exist a universal constant C>0 such that $H(hat{f}^2)leq C Inf(f)$, where $H(hat{f}^2)$ is the Shannon entropy of the Fourier distribution of $f$ and $Inf(f)$ is the total influence of $f$. 1) We consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture. This asks if $H_{infty}(hat{f}^2)leq C Inf(f)$, where $H_{infty}(hat{f}^2)$ is the min-entropy of the Fourier distribution. We show $H_{infty}(hat{f}^2)leq 2C_{min}^oplus(f)$, where $C_{min}^oplus(f)$ is the minimum parity certificate complexity of $f$. We also show that for every $epsilongeq 0$, we have $H_{infty}(hat{f}^2)leq 2log (|hat{f}|_{1,epsilon}/(1-epsilon))$, where $|hat{f}|_{1,epsilon}$ is the approximate spectral norm of $f$. As a corollary, we verify the FMEI conjecture for the class of read-$k$ $DNF$s (for constant $k$). 2) We show that $H(hat{f}^2)leq 2 aUC^oplus(f)$, where $aUC^oplus(f)$ is the average unambiguous parity certificate complexity of $f$. This improves upon Chakraborty et al. An important consequence of the FEI conjecture is the long-standing Mansours conjecture. We show that a weaker version of FEI already implies Mansours conjecture: is $H(hat{f}^2)leq C min{C^0(f),C^1(f)}$?, where $C^0(f), C^1(f)$ are the 0- and 1-certificate complexities of $f$, respectively. 3) We study what FEI implies about the structure of polynomials that 1/3-approximate a Boolean function. We pose a conjecture (which is implied by FEI): no flat degree-$d$ polynomial of sparsity $2^{omega(d)}$ can 1/3-approximate a Boolean function. We prove this conjecture unconditionally for a particular class of polynomials.
The problem of constructing pseudorandom generators that fool halfspaces has been studied intensively in recent times. For fooling halfspaces over the hypercube with polynomially small error, the best construction known requires seed-length O(log^2 n) (MekaZ13). Getting the seed-length down to O(log(n)) is a natural challenge in its own right, which needs to be overcome in order to derandomize RL. In this work we make progress towards this goal by obtaining near-optimal generators for two important special cases: 1) We give a near optimal derandomization of the Chernoff bound for independent, uniformly random bits. Specifically, we show how to generate a x in {1,-1}^n using $tilde{O}(log (n/epsilon))$ random bits such that for any unit vector u, <u,x> matches the sub-Gaussian tail behaviour predicted by the Chernoff bound up to error eps. 2) We construct a generator which fools halfspaces with {0,1,-1} coefficients with error eps with a seed-length of $tilde{O}(log(n/epsilon))$. This includes the important special case of majorities. In both cases, the best previous results required seed-length of $O(log n + log^2(1/epsilon))$. Technically, our work combines new Fourier-analytic tools with the iterative dimension reduction techniques and the gradually increasing independence paradigm of previous works (KaneMN11, CelisRSW13, GopalanMRTV12).
We exhibit an unambiguous k-DNF formula that requires CNF width $tilde{Omega}(k^2)$, which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon--Saks--Seymour problem in graph theory (posed in 1991), which asks: How large a gap can there be between the chromatic number of a graph and its biclique partition number? Our result is also known to imply several other improved separations in query and communication complexity.
Finding cliques in random graphs and the closely related planted clique variant, where a clique of size t is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for t = Theta(sqrt(n)). Here we show that beating sqrt(n) would require substantially new algorithmic ideas, by proving a lower bound for the problem in the sum-of-squares (or Lasserre) hierarchy, the most powerful class of semi-definite programming algorithms we know of: r rounds of the sum-of-squares hierarchy can only solve the planted clique for t > sqrt(n)/(C log n)^(r^2). Previously, no nontrivial lower bounds were known. Our proof is formulated as a degree lower bound in the Positivstellensatz algebraic proof system, which is equivalent to the sum-of-squares hierarchy. The heart of our (average-case) lower bound is a proof that a certain random matrix derived from the input graph is (with high probability) positive semidefinite. Two ingredients play an important role in this proof. The first is the classical theory of association schemes, applied to the average and variance of that random matrix. The second is a new large deviation inequality for matrix-valued polynomials. Our new tail estimate seems to be of independent interest and may find other applications, as it generalizes both the estimates on real-valued polynomials and on sums of independent random matrices.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
