ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usTue, 20 Feb 2024 13:38:52 +0200TR24-029 | Quantum Automating $\mathbf{TC}^0$-Frege Is LWE-Hard |
Noel Arteche,
Gaia Carenini,
Matthew Gray
https://eccc.weizmann.ac.il/report/2024/029We prove the first hardness results against efficient proof search by quantum algorithms. We show that under Learning with Errors (LWE), the standard lattice-based cryptographic assumption, no quantum algorithm can weakly automate $\mathbf{TC}^0$-Frege. This extends the line of results of Kraí?ek and Pudlák (Information and Computation, 1998), Bonet, Pitassi, and Ray (FOCS, 1997), and Bonet et al. (Computational Complexity, 2004), who showed that Extended Frege, $\mathbf{TC}^0$-Frege and $\mathbf{AC}^0$-Frege, respectively, cannot be weakly automated by classical algorithms if either the RSA cryptosystem or the Diffie-Hellman key exchange protocol are secure. To the best of our knowledge, this is the first interaction between quantum computation and propositional proof search.Tue, 20 Feb 2024 13:38:52 +0200https://eccc.weizmann.ac.il/report/2024/029TR24-028 | Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields |
Ashish Dwivedi,
Zeyu Guo,
Ben Lee Volk
https://eccc.weizmann.ac.il/report/2024/028We construct explicit pseudorandom generators that fool $n$-variate polynomials of degree at most $d$ over a finite field $\mathbb{F}_q$. The seed length of our generators is $O(d \log n + \log q)$, over fields of size exponential in $d$ and characteristic at least $d(d-1)+1$. Previous constructions such as Bogdanov's (STOC 2005) and Derksen and Viola's (FOCS 2022) had either suboptimal seed length or required the field size to depend on $n$.
Our approach follows Bogdanov's paradigm while incorporating techniques from Lecerf's factorization algorithm (J. Symb. Comput. 2007) and insights from the construction of Derksen and Viola regarding the role of indecomposability of polynomials.Mon, 19 Feb 2024 18:31:34 +0200https://eccc.weizmann.ac.il/report/2024/028TR24-027 | Near Optimal Alphabet-Soundness Tradeoff PCPs |
Dor Minzer,
Kai Zhe Zheng
https://eccc.weizmann.ac.il/report/2024/027 We show that for all $\varepsilon>0$, for sufficiently large prime power $q\in\mathbb{N}$, for all $\delta>0$, it is NP-hard to distinguish whether a $2$-Prover-$1$-Round projection game with alphabet size $q$ has value at least $1-\delta$, or value at most $1/q^{1-\varepsilon}$. This establishes a nearly optimal alphabet-to-soundness tradeoff for $2$-query PCPs with alphabet size $q$, improving upon a result of Chan [Cha16]. Our result has the following implications:
1. Near optimal hardness for Quadratic Programming: it is NP-hard to approximate the value of a given Boolean Quadratic Program within factor $(\log n)^{1 - o(1)}$ under quasi-polynomial time reductions. This result improves a result of Khot and Safra [KS13] and nearly matches the performance of the best known approximation algorithm [Meg01, NRT99, CW04] that achieves a factor of $O(\log n)$.
2. Bounded degree $2$-CSP's: under randomized reductions, for sufficiently large $d>0$, it is NP-hard to approximate the value of $2$-CSPs in which each variable appears in at most $d$ constraints within factor $(1-o(1))\frac{d}{2}$, improving upon a recent result of Lee and Manurangsi [LM23].
3. Improved hardness results for connectivity problems: using results of Laekhanukit [Lae14] and Manurangsi [Man19], we deduce improved hardness results for the Rooted $k$-Connectivity Problem, the Vertex-Connectivity Survivable Network Design Problem and the Vertex-Connectivity $k$-Route Cut Problem.Sun, 18 Feb 2024 04:22:16 +0200https://eccc.weizmann.ac.il/report/2024/027TR24-026 | A subquadratic upper bound on sum-of-squares compostion formulas |
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2024/026For every $n$, we construct a sum-of-squares identitity
\[ (\sum_{i=1}^n x_i^2) (\sum_{j=1}^n y_j^2)= \sum_{k=1}^s f_k^2\,,\]
where $f_k$ are bilinear forms with complex coefficients and $s= O(n^{1.62})$. Previously, such a construction was known with $s=O(n^2/\log n)$.
The same bound holds over any field of positive characteristic.Thu, 15 Feb 2024 14:10:21 +0200https://eccc.weizmann.ac.il/report/2024/026TR24-025 | Nearest Neighbor Complexity and Boolean Circuits |
Mason DiCicco,
Vladimir Podolskii,
Daniel Reichman
https://eccc.weizmann.ac.il/report/2024/025A nearest neighbor representation of a Boolean function $f$ is a set of vectors (anchors) labeled by $0$ or $1$ such that $f(x) = 1$ if and only if the closest anchor to $x$ is labeled by $1$. This model was introduced by Hajnal, Liu, and Turán (2022), who studied bounds on the number of anchors required to represent Boolean functions under different choices of anchors (real vs. Boolean vectors) as well as the more expressive model of $k$-nearest neighbors.
We initiate the study of the representational power of nearest and $k$-nearest neighbors through Boolean circuit complexity. To this end, we establish a connection between Boolean functions with polynomial nearest neighbor complexity and those that can be efficiently represented by classes based on linear inequalities -- min-plus polynomial threshold functions -- previously studied in relation to threshold circuits. This extends an observation of Hajnal et al. (2022). We obtain exponential lower bounds on the $k$-nearest neighbors complexity of explicit $n$-variate functions, assuming $k \leq n^{1-\epsilon}$. Previously, no superlinear lower bound was known for any $k>1$.
Next, we further extend the connection between nearest neighbor representations and circuits to the $k$-nearest neighbors case. As a result, we show that proving superpolynomial lower bounds for the $k$-nearest neighbors complexity of an explicit function for arbitrary $k$ would require a breakthrough in circuit complexity. In addition, we prove an exponential separation between the nearest neighbor and $k$-nearest neighbors complexity (for unrestricted $k$) of an explicit function. These results address questions raised by Hajnal et al. (2022) of proving strong lower bounds for $k$-nearest neighbors and understanding the role of the parameter $k$. Finally, we devise new bounds on the nearest neighbor complexity for several explicit functions.Thu, 15 Feb 2024 10:27:34 +0200https://eccc.weizmann.ac.il/report/2024/025TR24-024 | Strong Batching for Non-Interactive Statistical Zero-Knowledge |
Ron Rothblum,
Changrui Mu,
Shafik Nassar,
Prashant Nalini Vasudevan
https://eccc.weizmann.ac.il/report/2024/024A zero-knowledge proof enables a prover to convince a verifier that $x \in S$, without revealing anything beyond this fact. By running a zero-knowledge proof $k$ times, it is possible to prove (still in zero-knowledge) that $k$ separate instances $x_1,\dots,x_k$ are all in $S$. However, this increases the communication by a factor of $k$. Can one do better? In other words, is (non-trivial) zero-knowledge batch verification for $S$ possible?
Recent works by Kaslasi et al. (TCC 2020, Eurocrypt 2021) show that any problem possessing a non-interactive statistical zero-knowledge proof (NISZK) has a non-trivial statistical zero-knowledge batch verification protocol. Their results had two major limitations: (1) to batch verify $k$ inputs of size $n$ each, the communication in their batch protocol is roughly $\textrm{poly}(n,\log{k})+O(k)$, which is better than the naive cost of $k \cdot \textrm{poly}(n)$ but still scales linearly with $k$, and, (2) the batch protocol requires $\Omega(k)$ rounds of interaction.
In this work we remove both of these limitations by showing that any problem in $NISZK$ has a non-interactive statistical zero-knowledge batch verification protocol with communication $\textrm{poly}(n,\log{k})$.Wed, 14 Feb 2024 14:09:04 +0200https://eccc.weizmann.ac.il/report/2024/024TR24-023 | Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems |
Shuichi Hirahara,
Naoto Ohsaka
https://eccc.weizmann.ac.il/report/2024/023Motivated by the inapproximability of reconfiguration problems, we present a new PCP-type characterization of PSPACE, which we call a probabilistically checkable reconfiguration proof (PCRP): Any PSPACE computation can be encoded into an exponentially long sequence of polynomially long proofs such that every adjacent pair of the proofs differs in at most one bit, and every proof can be probabilistically checked by reading a constant number of bits.
Using the new characterization, we prove PSPACE-completeness of approximate versions of many reconfiguration problems, such as the Maxmin $3$-SAT Reconfiguration problem. This resolves the open problem posed by Ito, Demaine, Harvey, Papadimitriou, Sideri, Uehara, and Uno (ISAAC 2008; Theor. Comput. Sci. 2011) as well as the Reconfiguration Inapproximability Hypothesis by Ohsaka (STACS 2023) affirmatively. We also present PSPACE-completeness of approximating the Maxmin Clique Reconfiguration problem to within a factor of $n^\epsilon$ for some constant $\epsilon > 0$.Sun, 11 Feb 2024 07:50:41 +0200https://eccc.weizmann.ac.il/report/2024/023TR24-022 | Exponential Separation Between Powers of Regular and General Resolution Over Parities |
Arkadev Chattopadhyay,
Sreejata Bhattacharya,
Pavel Dvorak
https://eccc.weizmann.ac.il/report/2024/022Proving super-polynomial lower bounds on the size of proofs of unsatisfiability of Boolean formulas using resolution over parities, is an outstanding problem that has received a lot of attention after its introduction by Raz and Tzamaret (2008). Very recently, Efremenko, Garlik and Itsykson (2023) proved the first exponential lower bounds on the size of ResLin proofs that were additionally restricted to be bottom-regular. We show that there are formulas for which such regular ResLin proofs of unsatisfiability continue to have exponential size even though there exists short proofs of their unsatisfiability in ordinary, non-regular resolution. This is the first super-polynomial separation between the power of general ResLin and and that of regular ResLin for any natural notion of regularity.
Our argument, while building upon the work of Efremenko et al, uses additional ideas from the literature on lifting theorems.Fri, 09 Feb 2024 17:59:26 +0200https://eccc.weizmann.ac.il/report/2024/022TR24-021 | On the closures of monotone algebraic classes and variants of the determinant |
Prasad Chaugule,
Nutan Limaye
https://eccc.weizmann.ac.il/report/2024/021In this paper we prove the following two results.
* We show that for any $C \in {mVF, mVP, mVNP}$, $C = \overline{C}$. Here, $mVF, mVP$, and $mVNP$ are monotone variants of $VF, VP$, and $VNP$, respectively. For an algebraic complexity class $C$, $\overline{C}$ denotes the closure of $C$. For $mVBP$ a similar result was shown. Here we extend their result by adapting their proof.
* We define polynomial families $\{\mathcal{P}(k)_n\}_{n \geq 0}$, such that $\{\mathcal{P}(0)_n\}_{n \geq 0}$ equals the Determinant polynomial. We show that $\{\mathcal{P}(k)_n\}_{n \geq 0}$ is $VBP$ complete for $k=1$ and becomes $VNP$ complete when $k \geq 2$. In particular, $\{\mathcal{P}(k)_n\}$ is $Det^{\neq k}_n(X)$, a polynomial obtained by summing over all signed cycle covers that avoid length $k$ cycles. We show that $Det^{\neq 1}_n(X)$ is complete for $VBP$ and $Det^{\neq k}_n(X)$ is complete for $VNP$ for all $k \geq 2$ over any field $\mathbb{F}$.
Sun, 04 Feb 2024 09:42:17 +0200https://eccc.weizmann.ac.il/report/2024/021TR24-020 | Constant Degree Direct Product Testers with Small Soundness |
Mitali Bafna,
Noam Lifshitz,
Dor Minzer
https://eccc.weizmann.ac.il/report/2024/020Let $X$ be a $d$-dimensional simplicial complex. A function $F\colon X(k)\to \{0,1\}^k$ is said to be a direct product function if there exists a function $f\colon X(1)\to \{0,1\}$ such that $F(\sigma) = (f(\sigma_1), \ldots, f(\sigma_k))$ for each $k$-face $\sigma$. In an effort to simplify components of the PCP theorem, Goldreich and Safra introduced the problem of direct product testing, which asks whether one can test if $F\colon X(k)\to \{0,1\}^k$ is correlated with a direct product function by querying $F$ on only $2$ inputs. Dinur and Kaufman conjectured that there exist bounded degree complexes with a direct product test in the small soundness regime. We resolve their conjecture by showing that for all $\delta>0$, there exists a family of high-dimensional expanders with degree
$O_{\delta}(1)$ and a $2$-query direct product tester with soundness $\delta$.
We use the characterization given by Bafna and Minzer and independently by Dikstein and Dinur, who showed that some form of non-Abelian coboundary expansion (which they called ``Unique-Games coboundary expansion'') is a necessary and sufficient condition for a complex to admit such direct product testers. Our main technical contribution is a general technique for showing coboundary expansion of complexes with coefficients in a non-Abelian group. This allows us to prove that the high dimensional expanders constructed by Chapman and Lubotzky satisfies the conditions of Bafna and Minzer, thus admitting a 2-query direct product tester with small soundness.
Fri, 02 Feb 2024 03:29:41 +0200https://eccc.weizmann.ac.il/report/2024/020