ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usTue, 18 Jan 2022 11:42:14 +0200TR22-009 | On Finer Separations between Subclasses of Read-once Oblivious ABPs |
C. Ramya,
Anamay Tengse
https://eccc.weizmann.ac.il/report/2022/009Read-once Oblivious Algebraic Branching Programs (ROABPs) compute polynomials as products of univariate polynomials that have matrices as coefficients. In an attempt to understand the landscape of algebraic complexity classes surrounding ROABPs, we study classes of ROABPs based on the algebraic structure of these coefficient matrices. We study connections between polynomials computed by these structured variants of ROABPs and other well-known classes of polynomials (such as depth-three powering circuits, tensor-rank and Waring rank of polynomials).
Our main result concerns commutative ROABPs, where all coefficient matrices commute with each other, and diagonal ROABPs, where all the coefficient matrices are just diagonal matrices. In particular, we show a somewhat surprising connection between these models and the model of depth-three powering circuits that is related to the Waring rank of polynomials. We show that if the dimension of partial derivatives captures Waring rank up to polynomial factors, then the model of diagonal ROABPs efficiently simulates the seemingly more expressive model of commutative ROABPs. Further, a commutative ROABP that cannot be efficiently simulated by a diagonal ROABP will give an explicit polynomial that gives a super-polynomial separation between dimension of partial derivatives and Waring rank.
Our proof of the above result builds on the results of Marinari, Möller and Mora (1993), and Möller and Stetter (1995), that characterise rings of commuting matrices in terms of polynomials that have small dimension of partial derivatives. The algebraic structure of the coefficient matrices of these ROABPs plays a crucial role in our proofs.Tue, 18 Jan 2022 11:42:14 +0200https://eccc.weizmann.ac.il/report/2022/009TR22-008 | Approximating Large Powers of Stochastic Matrices in Small Space |
Gil Cohen,
Dean Doron,
Ori Sberlo
https://eccc.weizmann.ac.il/report/2022/008We give a deterministic space-efficient algorithm for approximating powers of stochastic matrices. On input a $w \times w$ stochastic matrix $A$, our algorithm approximates $A^{n}$ in space $\widetilde{O}(\log n + \sqrt{\log n}\cdot \log w)$ to within high accuracy. This improves upon the seminal work by Saks and Zhou (FOCS'95), that requires $O(\log^{3/2}n + \sqrt{\log n} \cdot \log w)$ space, in the regime $n \gg w$.Fri, 14 Jan 2022 11:34:37 +0200https://eccc.weizmann.ac.il/report/2022/008TR22-007 | A Simpler Proof of the Worst-Case to Average-Case Reduction for Polynomial Hierarchy via Symmetry of Information |
Valentine Kabanets,
Halley Goldberg
https://eccc.weizmann.ac.il/report/2022/007We give a simplified proof of Hirahara's STOC'21 result showing that $DistPH \subseteq AvgP$ would imply $PH \subseteq DTIME[2^{O(n/\log n)}]$. The argument relies on a proof of the new result: Symmetry of Information for time-bounded Kolmogorov complexity under the assumption that $NP$ is easy on average, which is interesting in its own right and generalizes the ``weak'' Symmetry of Information theorem from the original paper by Hirahara.Fri, 14 Jan 2022 04:52:14 +0200https://eccc.weizmann.ac.il/report/2022/007TR22-006 | Secret Sharing, Slice Formulas, and Monotone Real Circuits |
Benny Applebaum,
Amos Beimel,
Oded Nir,
Naty Peter,
Toniann Pitassi
https://eccc.weizmann.ac.il/report/2022/006A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined ``authorized'' sets of parties can reconstruct the secret, and all other ``unauthorized'' sets learn nothing about $s$. For over 30 years, it was known that any (monotone) collection of authorized sets can be realized by a secret-sharing scheme whose shares are of size $2^{n-o(n)}$ and until recently no better scheme was known. In a recent breakthrough, Liu and Vaikuntanathan (STOC 2018) have reduced the share size to $2^{0.994n+o(n)}$, and this was further improved by several follow-ups accumulating in an upper bound of $1.5^{n+o(n)}$ (Applebaum and Nir, CRYPTO 2021). Following these advances, it is natural to ask whether these new approaches can lead to a truly sub-exponential upper-bound of $2^{n^{1-\epsilon}}$ for some constant $\epsilon>0$, or even all the way down to polynomial upper-bounds.
In this paper, we relate this question to the complexity of computing monotone Boolean functions by monotone real circuits (MRCs) -- a computational model that was introduced by Pudl\'{a}k (J. Symb. Log., 1997) in the context of proof complexity. We introduce a new notion of ``separable'' MRCs that lies between monotone real circuits and monotone real formulas (MRFs). As our main results, we show that recent constructions of general secret-sharing schemes implicitly give rise to separable MRCs for general monotone functions of similar complexity, and that some monotone functions (in monotone NP) cannot be computed by sub-exponential size separable MRCs. Interestingly, it seems that proving similar lower-bounds for general MRCs is beyond the reach of current techniques.
We use this connection to obtain lower-bounds against a natural family of secret-sharing schemes, as well as new non-trivial upper-bounds for MRCs. Specifically, we conclude that recent approaches for secret-sharing schemes cannot achieve sub-exponential share size and that every monotone function can be realized by an MRC (or even MRF) of complexity $1.5^{n+o(n)}$. To the best of our knowledge, this is the first improvement over the trivial $2^{n-o(n)}$ upper-bound. Along the way, we show that the recent constructions of general secret-sharing schemes implicitly give rise to Boolean formulas over slice functions and prove that such formulas can be simulated by separable MRCs of similar size. On a conceptual level, our paper continues the rich line of study that relates the share size of secret-sharing schemes to monotone complexity measures.Wed, 12 Jan 2022 17:39:53 +0200https://eccc.weizmann.ac.il/report/2022/006TR22-005 | Sunflowers: from soil to oil |
Anup Rao
https://eccc.weizmann.ac.il/report/2022/005A \emph{sunflower} is a collection of sets whose pairwise intersections are identical. In this article, we shall go sunflower-picking. We find sunflowers in several seemingly unrelated fields, before turning to discuss recent progress on the famous sunflower conjecture of Erd\H{o}s and Rado, made by Alweiss, Lovett, Wu and Zhang.Tue, 11 Jan 2022 21:30:19 +0200https://eccc.weizmann.ac.il/report/2022/005TR22-004 | Analyzing Ta-Shma’s Code via the Expander Mixing Lemma |
Silas Richelson,
Sourya Roy
https://eccc.weizmann.ac.il/report/2022/004Random walks in expander graphs and their various derandomizations (e.g., replacement/zigzag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used s-wide replacement walks in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma’s original analysis was entirely linear algebraic, and subsequent developments have inherited this viewpoint. In this work, we rederive Ta-Shma’s analysis from a combinatorial point of view using repeated application of the expander mixing lemma. We hope that this alternate perspective will yield a better understanding of Ta-Shma’s construction. As an additional application of our techniques, we give an alternate proof of the expander hitting set lemma.Sun, 09 Jan 2022 06:39:36 +0200https://eccc.weizmann.ac.il/report/2022/004TR22-003 | On Semi-Algebraic Proofs and Algorithms |
Robert Robere,
Noah Fleming,
Mika Göös,
Stefan Grosser
https://eccc.weizmann.ac.il/report/2022/003We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-$d$ Sherali-Adams refutation of an unsatisfiable CNF formula $C$ if and only if there is an $\varepsilon > 0$ and a degree-$d$ conical junta $J$ such that $viol_C(x) - \varepsilon = J$, where $viol_C(x)$ counts the number of falsified clauses of $C$ on an input $x$. Using this result we show that the linear separation complexity, a complexity measure recently studied by Hrubeš (and independently by de Oliveira Oliveira and Pudlák under the name of weak monotone linear programming gates), monotone feasibly interpolates Sherali-Adams proofs; this sharpens a recent feasible interpolation result due to Hakoniemi.
We then investigate separation results for $viol_C(x) - \varepsilon$. In particular, we give a family of unsatisfiable CNF formulas $C$ which have polynomial-size and small-width resolution proofs, but for which any representation of $viol_C(x) - 1$ by a conical junta requires degree $\Omega(n)$; this resolves an open question of Filmus, Mahajan, Sood, and Vinyals. Since Sherali-Adams can simulate resolution, this separates the non-negative degree of $viol_C(x) - 1$ and $viol_C(x) - \varepsilon$ for arbitrarily small $\varepsilon > 0$. Finally, by applying lifting theorems, we translate this lower bound into new separation results between extension complexity and monotone circuit complexity.
Tue, 04 Jan 2022 20:55:39 +0200https://eccc.weizmann.ac.il/report/2022/003TR22-002 | Extending Merge Resolution to a Family of Proof Systems |
Sravanthi Chede,
Anil Shukla
https://eccc.weizmann.ac.il/report/2022/002Merge Resolution (MRes [Beyersdorff et al. J. Autom. Reason.'2021]) is a recently introduced proof system for false QBFs. Unlike other known QBF proof systems, it builds winning strategies for the universal player within the proofs. Every line of this proof system consists of existential clauses along with countermodels. MRes stores the countermodels as merge maps. Merge maps are deterministic branching programs in which isomorphism checking is efficient as a result MRes is a polynomial time verifiable proof system.
In this paper, we introduce a family of proof systems MRes-$\mathcal{R}$ in which, the information of countermodels are stored in any pre-fixed complete representation $\mathcal{R}$, instead of merge maps. Hence corresponding to each possible complete representation $\mathcal{R}$, we have a sound and refutationally complete QBF-proof system in MRes-$\mathcal{R}$. To handle arbitrary representations for the strategies, we introduce consistency checking rules in MRes-$\mathcal{R}$ instead of isomorphism checking in MRes. As a result these proof systems are not polynomial time verifiable. Consequently, the paper shows that using merge maps is too restrictive and can be replaced with arbitrary representations leading to several interesting proof systems.
The paper also studies proof theoretic properties of the family of new proof systems MRes-$\mathcal{R}$. We show that eFrege+$\forall$red simulates all valid refutations from proof systems in MRes-$\mathcal{R}$. Since proof systems in MRes-$\mathcal{R}$ may use arbitrary representations, in order to simulate them, we first represent the steps used by the proof systems as a new simple complete structure. As a consequence, the corresponding proof system belonging to MRes-$\mathcal{R}$ is able to simulate all proof systems in MRes-$\mathcal{R}$. Finally, we simulate this proof system via eFrege+$\forall$red using the ideas from [Chew et al. ECCC.'2021].
On the lower bound side, we lift the lower bound result of regular MRes ([Beyersdorff et al. FSTTCS.'2020]) for all regular proof systems in MRes-$\mathcal{R}$. To be precise, we show that the completion principle formulas from [Jonata et al. Theor. Comput. Sci.'2015] which are shown to be hard for regular MRes in [Beyersdorff et al. FSTTCS.'2020], are also hard for any regular proof system in MRes-$\mathcal{R}$. Thereby, the paper lifts the lower bound of regular MRes to an entire class of proof systems, which use some complete representation, including those undiscovered, instead of merge maps.Sun, 02 Jan 2022 14:33:31 +0200https://eccc.weizmann.ac.il/report/2022/002TR22-001 | On (Simple) Decision Tree Rank |
Yogesh Dahiya,
Meena Mahajan
https://eccc.weizmann.ac.il/report/2022/001In the decision tree computation model for Boolean functions, the depth corresponds to query complexity, and size corresponds to storage space. The depth measure is the most well-studied one, and is known to be polynomially related to several non-computational complexity measures of functions such as certificate complexity. The size measure is also studied, but to a lesser extent. Another decision tree measure that has received very little attention is the minimal rank of the decision tree, first introduced by Ehrenfeucht and Haussler in 1989. This measure is not polynomially related to depth, and hence it can reveal additional information about the complexity of a function. It is characterised by the value of a Prover-Delayer game first proposed by Pudl{\'a}k and Impagliazzo in the context of tree-like resolution proofs. In this paper we study this measure further. We obtain upper and lower bounds on rank in terms of (variants of) certificate complexity. We also obtain upper and lower bounds on the rank for composed functions in terms of the depth of the outer function and the rank of the inner function. We compute the rank exactly for several natural functions and use them to show that all the bounds we have obtained are tight. We also observe that the size-rank relationship for decision trees, obtained by Ehrenfeucht and Haussler, is tight upto constant factors.Sun, 02 Jan 2022 07:57:00 +0200https://eccc.weizmann.ac.il/report/2022/001TR21-182 | On the strength of Sherali-Adams and Nullstellensatz as propositional proof systems |
Ilario Bonacina,
Maria Luisa Bonet
https://eccc.weizmann.ac.il/report/2021/182The propositional proof system Sherali-Adams (SA) has polynomial-size proofs of the pigeonhole principle (PHP). Similarly, the Nullstellensatz (NS) proof system has polynomial size proofs of the bijective (i.e. both functional and onto) pigeonhole principle (ofPHP). We characterize the strength of these algebraic proof systems in terms of Boolean proof systems the following way. We show that SA (resp. NS over ${\bf Z}$) with unary coefficients lies strictly between tree-like resolution and tree-like depth-$1$ Frege + PHP (resp. ofPHP). We introduce weighted versions of PHP and ofPHP, resp. wtPHP and of-wtPHP and we show that SA (resp. NS over ${\bf Z}$) lies strictly between resolution and tree-like depth-$1$ Frege + wtPHP (resp. of-wtPHP). We also show analogue results for depth-$d$ versions of SA and NS.Thu, 30 Dec 2021 22:42:36 +0200https://eccc.weizmann.ac.il/report/2021/182