ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usMon, 05 Jun 2023 08:39:55 +0300TR23-085 | Average-Case PAC-Learning from Nisan's Natural Proofs |
Ari Karchmer
https://eccc.weizmann.ac.il/report/2023/085Carmosino et al. (2016) demonstrated that natural proofs of circuit lower bounds imply algorithms for learning circuits with membership queries over the uniform distribution. Indeed, they exercised this implication to obtain a quasi-polynomial time learning algorithm for ${AC}^0[p]$ circuits, for any prime $p$, by leveraging the existing natural proofs from Razborov (1987) and Smolensky (1987). This achievement raises a logical question: can existing natural proofs be adapted into learning algorithms that utilize random examples and learn over unknown, arbitrary example distributions?
In this work, we show that natural circuit lower bounds proven by specific communication complexity arguments (e.g., Nisan (1994)) witness a ``yes'' answer to this question, under the one limitation of average-case learning. Our primary technical contribution demonstrates a connection between the complexity of learning a concept class in the average-case, and the randomized communication complexity of an evaluation game associated with the class. We apply this finding to derive polynomial time average-case PAC-learning algorithms that use only random examples from arbitrary and unknown distributions, for any concept class that may be evaluated by (for instance) a majority vote of linear threshold functions.
Additionally, our work contributes to a better understanding of the optimal parameters in XOR lemmas for communication complexity. We address a question posed by Viola and Wigderson (2007) by demonstrating that certain enhancements of parameters in their XOR lemmas are false, assuming the existence of one-way functions.
Mon, 05 Jun 2023 08:39:55 +0300https://eccc.weizmann.ac.il/report/2023/085TR23-084 | Time-Space Lower Bounds for Bounded-Error Computation in the Random-Query Model |
Itai Dinur
https://eccc.weizmann.ac.il/report/2023/084The random-query model was introduced by Raz and Zhan at ITCS 2020 as a new model of space-bounded computation. In this model, a branching program of length $T$ and width $2^{S}$ attempts to compute a function $f:\{0,1\}^n \rightarrow \{0,1 \}$. However, instead of receiving direct access to the input bits $(x_1,\ldots,x_n)$, the input is given in pairs of the form $(i_j, x_{i_j}) \in \{1,\ldots,n\} \times \{0,1\}$ for $j = 1,2,\ldots,T$, where the indices $i_1,\ldots,i_T$ are chosen at random from a pre-fixed distribution.
Raz and Zhan proved that any branching program in the random-query model with the independent distribution (where $\{i_j\}_{j = 1,\ldots,T}$ are uniform and independent) that computes a function $f$ with sensitivity $k$ satisfies $T \cdot (S + \log n) \geq \Omega(n \cdot k)$.
This gives a quadratic time-space lower bound for many natural functions which have sensitivity $\Omega(n)$, such as XOR and Majority. The bound was proved in the zero-error regime, where for each input, the branching program is required to output a value with high probability, and given that a value is output, it must be correct with probability $1$.
Furthermore, Raz and Zhan conjectured that (up to logarithmic factors in $n$) a quadratic time-space lower bound still holds for the XOR function in the more conventional bounded-error regime, where for each input, the output must be correct with high probability.
In this paper, we prove this conjecture. More generally, let $f:\{0,1\}^n \rightarrow \{0,1 \}$ have average sensitivity (or total influence) $\mathrm{I}[f]$. We prove that any branching program in the random-query model with the independent distribution that computes $f$ in the bounded-error regime satisfies $T \cdot S \geq \tilde{\Omega}(n) \cdot \mathrm{I}[f]$ (where $\tilde{\Omega}$ hides logarithmic factors in $n$). Moreover, we prove a quadratic time-space lower bound for the Majority function, even though its total influence is $\Theta(\sqrt{n})$.
Our proof is based on a reduction from a communication complexity problem.Sun, 04 Jun 2023 05:29:40 +0300https://eccc.weizmann.ac.il/report/2023/084TR23-083 | Trade-offs between Entanglement and Communication |
Srinivasan A,
Uma Girish
https://eccc.weizmann.ac.il/report/2023/083We study the advantages of quantum communication models over classical communication models that are equipped with a limited number of qubits of entanglement. In this direction, we give explicit partial functions on $n$ bits for which reducing the entanglement increases the classical communication complexity exponentially. Our separations are as follows. For every $k\ge 1$:
$Q\|^*$ versus $R2^*$: We show that quantum simultaneous protocols with $\tilde{\Theta}(k^5 \log^3 n)$ qubits of entanglement can exponentially outperform two-way randomized protocols with $O(k)$ qubits of entanglement. This resolves an open problem from [Gav08] and improves the state-of-the-art separations between quantum simultaneous protocols with entanglement and two-way randomized protocols without entanglement [Gav19, GRT22].
$R\|^*$ versus $Q\|^*$: We show that classical simultaneous protocols with $\tilde{\Theta}(k \log n)$ qubits of entanglement can exponentially outperform quantum simultaneous protocols with $O(k)$ qubits of entanglement, resolving an open question from [GKRW06, Gav19]. The best result prior to our work was a relational separation against protocols without entanglement [GKRW06].
$R\|^*$ versus $R1^*$: We show that classical simultaneous protocols with $\tilde{\Theta}(k\log n)$ qubits of entanglement can exponentially outperform randomized one-way protocols with $O(k)$ qubits of entanglement. Prior to our work, only a relational separation was known [Gav08].Sun, 04 Jun 2023 05:27:27 +0300https://eccc.weizmann.ac.il/report/2023/083TR23-082 | Self-Improvement for Circuit-Analysis Problems |
Ryan Williams
https://eccc.weizmann.ac.il/report/2023/082Many results in fine-grained complexity reveal intriguing consequences from solving various SAT problems even slightly faster than exhaustive search. We prove a ``self-improving'' (or ``bootstrapping'') theorem for Circuit-SAT, $\#$Circuit-SAT, and its fully-quantified version: solving one of these problems faster for ``large'' circuit sizes implies a significant speed-up for ``smaller'' circuit sizes. Our general arguments work for a variety of models solving circuit-analysis problems, including non-uniform circuits and randomized models of computation.
We derive striking consequences for the complexities of these problems. For example, we show that certain fine-grained improvements on the runtime exponents of polynomial-time versions of Circuit-SAT would imply *subexponential-time* algorithms for Circuit-SAT on $2^{o(n)}$-size circuits, refuting the Exponential Time Hypothesis. We also show how slightly faster $\#$Circuit-SAT algorithms on large circuits can be used to prove lower bounds against uniform circuits with symmetric gates for functions in deterministic linear time. Our result suggests an ``algorithmic method'' approach for uniform circuit lower bounds, which trades non-uniformity for a substantial reduction in the complexity of the hard function.Thu, 01 Jun 2023 17:41:12 +0300https://eccc.weizmann.ac.il/report/2023/082TR23-081 | Constant-Round Arguments from One-Way Functions |
Noga Amit,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2023/081We study the following question: what cryptographic assumptions are needed for obtaining constant-round computationally-sound argument systems? We focus on argument systems with almost-linear verification time for subclasses of $\mathbf{P}$, such as depth-bounded computations.
Kilian's celebrated work [STOC 1992] provides such 4-message arguments for $\mathbf{P}$ (actually, for $\mathbf{NP}$) using collision-resistant hash functions.
We show that $one$-$way\ functions$ suffice for obtaining constant-round arguments of almost-linear verification time for languages in $\mathbf{P}$ that have log-space uniform circuits of linear depth and polynomial size. More generally, the complexity of the verifier scales with the circuit depth. Furthermore, our argument systems (like Kilian's) are doubly-efficient; that is, the honest prover strategy can be implemented in polynomial-time.
Unconditionally sound interactive proofs for this class of computations do not rely on any cryptographic assumptions, but they require a linear number of rounds [Goldwasser, Kalai and Rothblum, STOC 2008]. Constant-round interactive proof systems of linear verification complexity are not known even for $\mathbf{NC}$ (indeed, even for $\mathbf{AC}^1$).Thu, 01 Jun 2023 08:42:37 +0300https://eccc.weizmann.ac.il/report/2023/081TR23-080 | Improved Learning from Kolmogorov Complexity |
Valentine Kabanets,
Halley Goldberg
https://eccc.weizmann.ac.il/report/2023/080Carmosino, Impagliazzo, Kabanets, and Kolokolova (CCC, 2016) showed that the existence of natural properties in the sense of Razborov and Rudich (JCSS, 1997) implies PAC learning algorithms in the sense of Valiant (Comm. ACM, 1984), for boolean functions in $\P/\poly$, under the uniform distribution and with membership queries. It is still an open problem to get from natural properties learning algorithms that do not rely on membership queries but rather use randomly drawn labeled examples.
Natural properties may be understood as an average-case version of MCSP, the problem of deciding the minimum size of a circuit computing a given truth-table. Problems related to MCSP include those concerning time-bounded Kolmogorov complexity. MKTP, for example, asks for the KT-complexity of a given string. KT-complexity is a relaxation of circuit size, as it does away with the requirement that a short description of a string be interpreted as a boolean circuit.
In this work, under assumptions of MKTP and the related problem $\mktp$ being easy on average, we get learning algorithms for boolean functions in $\P/\poly$ that
\begin{itemize}
\item work over any distribution $D$ samplable by a family of polynomial-size circuits (given explicitly in the case of $\MKTP$),
\item only use randomly drawn labeled examples from $D$, and
\item are agnostic (do not require the target function to belong to the hypothesis class).
\end{itemize}
Our results build upon the recent work of Hirahara and Nanashima (FOCS, 2021) who showed similar learning consequences but under a stronger assumption that $\NP$ is easy on average.Thu, 01 Jun 2023 03:07:23 +0300https://eccc.weizmann.ac.il/report/2023/080TR23-079 | Mutual Empowerment between Circuit Obfuscation and Circuit Minimization |
Russell Impagliazzo,
Valentine Kabanets,
Ilya Volkovich
https://eccc.weizmann.ac.il/report/2023/079We study close connections between Indistinguishability Obfuscation ($IO$) and the Minimum Circuit Size Problem ($MCSP$), and argue that algorithms for one of $MCSP$ or $IO$ would empower the other one. Some of our main results are:
\begin{itemize}
\item If there exists a perfect (imperfect) $IO$ that is computationally secure against nonuniform polynomial-size circuits, then for all $k \in \mathbb{N}$: $NP \cap ZPP^{MCSP} \not \subseteq SIZE[n^k]$ ($MA \cap ZPP^{MCSP} \not \subseteq SIZE[n^k]$).
\item In addition, if there exists a perfect $IO$ that is computationally secure against nonuniform polynomial-size circuits, then $NEXP \cap ZPEXP^{MCSP} \not \subseteq P/poly.$
\item If $MCSP \in BPP$, then statistical security and computational security for $IO$ are equivalent.
\item If computationally-secure perfect $IO$ exists, then $MCSP \in BPP$ iff $NP = ZPP$.
\item If computationally-secure perfect $IO$ exists, then $ZPEXP \neq BPP$.
\end{itemize}
To the best of our knowledge, this is the first consequence of strong circuit lower bounds from the existence of an $IO$. The results are obtained via a construction of an optimal \emph{universal distinguisher}, computable in randomized polynomial time with access to the $MCSP$ oracle, that will distinguish any two circuit-samplable distributions with the advantage that is the statistical distance between these two distributions minus some negligible error term. This is our main technical contribution. As another immediate application, we get a simple proof of the result by Allender and Das (Inf. Comput., 2017) that $SZK \subseteq BPP^{MCSP}$.Thu, 01 Jun 2023 03:00:41 +0300https://eccc.weizmann.ac.il/report/2023/079TR23-078 | Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition |
Or Meir
https://eccc.weizmann.ac.il/report/2023/078One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq \mathbf{NC}^{1}$). Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4), 1995) suggested to approach this problem by proving that depth complexity of a composition of functions $f \diamond g$ is roughly the sum of the depth complexities of $f$ and $g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{NC}^{1}$.
The intuition that underlies the KRW conjecture is that the composition $f \diamond g$ should behave like a "direct-sum problem", in a certain sense, and therefore the depth complexity of $f \diamond g$ should be the sum of the individual depth complexities. Nevertheless, there are two obstacles toward turning this intuition into a proof: first, we do not know how to prove that $f \diamond g$ must behave like a direct-sum problem; second, we do not know how to prove that the complexity of the latter direct-sum problem is indeed the sum of the individual complexities.
In this work, we focus on the second obstacle. To this end, we study a notion called ``strong composition'', which is the same as $f \diamond g$ except that it is forced to behave like a direct-sum problem. We prove a variant of the KRW conjecture for strong composition, thus overcoming the above second obstacle. This result demonstrates that the first obstacle above is the crucial barrier toward resolving the KRW conjecture. Along the way, we develop some general techniques that might be of independent interest.
Tue, 30 May 2023 18:41:38 +0300https://eccc.weizmann.ac.il/report/2023/078TR23-077 | Batch Proofs are Statistically Hiding |
Nir Bitansky,
Chethan Kamath,
Omer Paneth,
Ron Rothblum,
Prashant Nalini Vasudevan
https://eccc.weizmann.ac.il/report/2023/077Batch proofs are proof systems that convince a verifier that $x_1,\dots, x_t \in L$, for some $NP$ language $L$, with communication that is much shorter than sending the $t$ witnesses. In the case of statistical soundness (where the cheating prover is unbounded but honest prover is efficient), interactive batch proofs are known for $UP$, the class of unique witness $NP$ languages. In the case of computational soundness (aka arguments, where both honest and dishonest provers are efficient), non-interactive solutions are now known for all of $NP$, assuming standard cryptographic assumptions. We study the necessary conditions for the existence of batch proofs in these two settings. Our main results are as follows.
1. Statistical Soundness: the existence of a statistically-sound batch proof for $L$ implies that $L$ has a statistically witness indistinguishable ($SWI$) proof, with inverse polynomial $SWI$ error, and a non-uniform honest prover. The implication is unconditional for public-coin protocols and relies on one-way functions in the private-coin case.
This poses a barrier for achieving batch proofs beyond $UP$ (where witness indistinguishability is trivial). In particular, assuming that $NP$ does not have $SWI$ proofs, batch proofs for all of $NP$ do not exist. This motivates further study of the complexity class $SWI$, which, in contrast to the related class $SZK$, has been largely left unexplored.
2. Computational Soundness: the existence of batch arguments ($BARG$s) for $NP$, together with one-way functions, implies the existence of statistical zero-knowledge ($SZK$) arguments for $NP$ with roughly the same number of rounds, an inverse polynomial zero-knowledge error, and non-uniform honest prover.
Thus, constant-round interactive $BARG$s from one-way functions would yield constant-round $SZK$ arguments from one-way functions. This would be surprising as $SZK$ arguments are currently only known assuming constant-round statistically-hiding commitments (which in turn are unlikely to follow from one-way functions).
3. Non-interactive: the existence of non-interactive $BARG$s for $NP$ and one-way functions, implies non-interactive statistical zero-knowledge arguments ($NISZKA$) for $NP$, with negligible soundness error, inverse polynomial zero-knowledge error, and non-uniform honest prover. Assuming also lossy public-key encryption, the statistical zero-knowledge error can be made negligible. We further show that $BARG$s satisfying a notion of honest somewhere extractability imply lossy public key encryption.
All of our results stem from a common framework showing how to transform a batch protocol for a language $L$ into an $SWI$ protocol for $L$.Sat, 27 May 2023 11:16:05 +0300https://eccc.weizmann.ac.il/report/2023/077TR23-076 | Polynomial-Time Pseudodeterministic Construction of Primes |
Lijie Chen,
Zhenjian Lu,
Igor Carboni Oliveira,
Hanlin Ren,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2023/076A randomized algorithm for a search problem is *pseudodeterministic* if it produces a fixed canonical solution to the search problem with high probability. In their seminal work on the topic, Gat and Goldwasser posed as their main open problem whether prime numbers can be pseudodeterministically constructed in polynomial time.
We provide a positive solution to this question in the infinitely-often regime. In more detail, we give an *unconditional* polynomial-time randomized algorithm $B$ such that, for infinitely many values of $n$, $B(1^n)$ outputs a canonical $n$-bit prime $p_n$ with high probability. More generally, we prove that for every dense property $Q$ of strings that can be decided in polynomial time, there is an infinitely-often pseudodeterministic polynomial-time construction of strings satisfying $Q$. This improves upon a subexponential-time construction of Oliveira and Santhanam.
Our construction uses several new ideas, including a novel bootstrapping technique for pseudodeterministic constructions, and a quantitative optimization of the uniform hardness-randomness framework of Chen and Tell, using a variant of the Shaltiel--Umans generator.Wed, 24 May 2023 16:56:30 +0300https://eccc.weizmann.ac.il/report/2023/076