ﻻ يوجد ملخص باللغة العربية
Hr{a}stad showed that any De Morgan formula (composed of AND, OR and NOT gates) shrinks by a factor of $O(p^{2})$ under a random restriction that leaves each variable alive independently with probability $p$ [SICOMP, 1998]. Using this result, he gave an $widetilde{Omega}(n^{3})$ formula size lower bound for the Andreev function, which, up to lower order improvements, remains the state-of-the-art lower bound for any explicit function. In this work, we extend the shrinkage result of Hr{a}stad to hold under a far wider family of random restrictions and their generalization -- random projections. Based on our shrinkage results, we obtain an $widetilde{Omega}(n^{3})$ formula size lower bound for an explicit function computed in $mathbf{AC}^0$. This improves upon the best known formula size lower bounds for $mathbf{AC}^0$, that were only quadratic prior to our work. In addition, we prove that the KRW conjecture [Karchmer et al., Computational Complexity 5(3/4), 1995] holds for inner functions for which the unweighted quantum adversary bound is tight. In particular, this holds for inner functions with a tight Khrapchenko bound. Our random projections are tailor-made to the functions structure so that the function maintains structure even under projection -- using such projections is necessary, as standard random restrictions simplify $mathbf{AC}^0$ circuits. In contrast, we show that any De Morgan formula shrinks by a quadratic factor under our random projections, allowing us to prove the cubic lower bound. Our proof techniques build on the proof of Hr{a}stad for the simpler case of balanced formulas. This allows for a significantly simpler proof at the cost of slightly worse parameters. As such, when specialized to the case of $p$-random restrictions, our proof can be used as an exposition of Hr{a}stads result.
We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions. We use this technique to prove an explicit lower bound by showing that any linear decision list com
We develop a notion of {em inner rank} as a tool for obtaining lower bounds on the rank of matrix multiplication tensors. We use it to give a short proof that the border rank (and therefore rank) of the tensor associated with $ntimes n$ matrix multip
We prove a query complexity lower bound for $mathsf{QMA}$ protocols that solve approximate counting: estimating the size of a set given a membership oracle. This gives rise to an oracle $A$ such that $mathsf{SBP}^A otsubset mathsf{QMA}^A$, resolving
Dawar and Wilsenach (ICALP 2020) introduce the model of symmetric arithmetic circuits and show an exponential separation between the sizes of symmetric circuits for computing the determinant and the permanent. The symmetry restriction is that the cir
In this paper we give lower bounds for the representation of real univariate polynomials as sums of powers of degree 1 polynomials. We present two families of polynomials of degree d such that the number of powers that are required in such a represen