ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usMon, 20 May 2024 04:57:17 +0300- TR24-094 | Interactive Proofs for General Distribution Properties |
Tal Herman,
Guy Rothblum
https://eccc.weizmann.ac.il/report/2024/094Suppose Alice has collected a small number of samples from an unknown distribution, and would like to learn about the distribution. Bob, an untrusted data analyst, claims that he ran a sophisticated data analysis on the distribution, and makes assertions about its properties. Can Alice efficiently verify Bob's claims using fewer resources (say in terms of samples and computation) than would be needed to run the analysis herself?
We construct an interactive proof system for any distribution property that can be decided by uniform polynomial-size circuits of bounded depth: the circuit gets a complete description of the distribution and decides whether it has the property. Taking $N$ to be an upper bound on the size of the distribution's support, the verifier's sample complexity, running time, and the communication complexity are all sublinear in $N$: they are bounded by $\widetilde{O}( N^{1-\alpha} + D)$ for a constant $\alpha > 0$, where $D$ is a bound on the depth of the circuits that decide the property. The honest prover runs in $\text{poly}(N)$ time and has quasi-linear sample complexity. Moreover, the proof system is tolerant: it can be used to approximate the distribution's distance from the property. We show similar results for any distribution property that can be decided by a bounded-space Turing machine (that gets as input a complete description of the distribution).
We remark that even for simple properties, deciding the property without a prover requires quasi-linear sample complexity and running time. Prior work [Herman and Rothblum, FOCS 2023] demonstrated sublinear interactive proof systems, but only for the much more restricted class of label-invariant distribution properties. Mon, 20 May 2024 04:57:17 +0300https://eccc.weizmann.ac.il/report/2024/094
- TR24-093 | Low-Degree Polynomials Are Good Extractors |
Jesse Goodman,
Omar Alrabiah,
Joao Ribeiro,
Jonathan Mosheiff
https://eccc.weizmann.ac.il/report/2024/093We prove that random low-degree polynomials (over $\mathbb{F}_2$) are unbiased, in an extremely general sense. That is, we show that random low-degree polynomials are good randomness extractors for a wide class of distributions. Prior to our work, such results were only known for the small families of (1) uniform sources, (2) affine sources, and (3) local sources. We significantly generalize these results, and prove the following.
1. Low-degree polynomials extract from small families. We show that a random low-degree polynomial is a good low-error extractor for any small family of sources. In particular, we improve the positive result of Alrabiah, Chattopadhyay, Goodman, Li, and Ribeiro (ICALP 2022) for local sources, and give new results for polynomial sources and variety sources via a single unified approach.
2. Low-degree polynomials extract from sumset sources. We show that a random low-degree polynomial is a good extractor for sumset sources, which are the most general large family of sources (capturing independent sources, interleaved sources, small-space sources, and more). This extractor achieves polynomially small error, and its min-entropy requirement is tight up to a square.
Our results on sumset extractors imply new complexity separations for linear ROBPs, and the tools that go into its proof have further applications, as well. The two main tools we use are a new structural result on sumset-punctured Reed-Muller codes, paired with a novel type of reduction between randomness extractors. Using the first new tool, we strengthen and generalize the extractor impossibility results of Chattopadhyay, Goodman, and Gurumukhani (ITCS 2024). Using the second, we show the existence of sumset extractors for min-entropy $k=O(\log(n/\varepsilon))$, resolving an open problem of Chattopadhyay and Liao (STOC 2022).Fri, 17 May 2024 08:21:58 +0300https://eccc.weizmann.ac.il/report/2024/093
- TR24-092 | Hilbert Functions and Low-Degree Randomness Extractors |
Alexander Golovnev,
Zeyu Guo,
Pooya Hatami,
Satyajeet Nagargoje,
Chao Yan
https://eccc.weizmann.ac.il/report/2024/092For $S\subseteq \mathbb{F}^n$, consider the linear space of restrictions of degree-$d$ polynomials to $S$. The Hilbert function of $S$, denoted $\mathrm{h}_S(d,\mathbb{F})$, is the dimension of this space. We obtain a tight lower bound on the smallest value of the Hilbert function of subsets $S$ of arbitrary finite grids in $\mathbb{F}^n$ with a fixed size $|S|$. We achieve this by proving that this value coincides with a combinatorial quantity, namely the smallest number of low Hamming weight points in a down-closed set of size $|S|$.
Understanding the smallest values of Hilbert functions is closely related to the study of degree-$d$ closure of sets, a notion introduced by Nie and Wang (Journal of Combinatorial Theory, Series A, 2015). We use bounds on the Hilbert function to obtain a tight bound on the size of degree-$d$ closures of subsets of $\mathbb{F}_q^n$, which answers a question posed by Doron, Ta-Shma, and Tell (Computational Complexity, 2022).
We use the bounds on the Hilbert function and degree-$d$ closure of sets to prove that a random low-degree polynomial is an extractor for samplable randomness sources. Most notably, we prove the existence of low-degree extractors and dispersers for sources generated by constant degree polynomials and polynomial-size circuits. Until recently, even the existence of arbitrary deterministic extractors for such sources was not known.Fri, 17 May 2024 08:21:42 +0300https://eccc.weizmann.ac.il/report/2024/092
- TR24-091 | When Do Low-Rate Concatenated Codes Approach The Gilbert--Varshamov Bound? |
Dean Doron,
Mary Wootters,
Jonathan Mosheiff
https://eccc.weizmann.ac.il/report/2024/091The Gilbert--Varshamov (GV) bound is a classical existential result in coding theory. It implies that a random linear binary code of rate $\varepsilon^2$ has relative distance at least $\frac{1}{2} - O(\varepsilon)$ with high probability. However, it is a major challenge to construct explicit codes with similar parameters.
One hope to derandomize the Gilbert--Varshamov construction is with code concatenation: We begin with a (hopefully explicit) outer code $\mathcal{C}_{\mathrm{out}}$ over a large alphabet, and concatenate that with a small binary random linear code $\mathcal{C}_{\mathrm{in}}$. It is known that when we use independent small codes for each coordinate, then the result lies on the GV bound with high probability, but this still uses a lot of randomness. In this paper, we consider the question of whether code concatenation with a single random linear inner code $\mathcal{C}_{\mathrm{in}}$ can lie on the GV bound; and if so what conditions on $\mathcal{C}_{\mathrm{out}}$ are sufficient for this.
We show that first, there do exist linear outer codes $\mathcal{C}_{\mathrm{out}}$ that are ``good'' for concatenation in this sense (in fact, most linear codes codes are good). We also provide two sufficient conditions for $\mathcal{C}_{\mathrm{out}}$, so that if $\cout$ satisfies these, $\mathcal{C}_{\mathrm{out}}\circ \mathcal{C}_{\mathrm{in}}$ will likely lie on the GV bound. We hope that these conditions may inspire future work towards constructing explicit codes $\mathcal{C}_{\mathrm{out}}$.Tue, 14 May 2024 15:21:40 +0300https://eccc.weizmann.ac.il/report/2024/091
- TR24-090 | A Study of Error Reduction Polynomials |
Gil Cohen,
Dean Doron,
Tomer Manket,
Edward Pyne,
Yichuan Wang,
Tal Yankovitz
https://eccc.weizmann.ac.il/report/2024/090Error reduction procedures play a crucial role in constructing weighted PRGs [PV'21, CDRST'21], which are central to many recent advances in space-bounded derandomization. The fundamental method driving error reduction procedures is the Richardson iteration, which is adapted from the literature on fast Laplacian solvers. In the context of space-bounded derandomization, where time is not the primary concern, can additional insights from optimization theory lead to improved error reduction procedures?
The results of this paper reveal an inherent barrier for using optimization-based techniques for error reduction in the context of space-bounded derandomization. To this end, we develop an abstract framework for error reduction based on polynomials which in particular encompasses all optimization-based error reduction techniques, and consequently, puts a limit on constructing improved weighted PRGs based on current approaches. Our work also sheds light on the necessity of negative weights within existing methods.
From the technical viewpoint, we establish lower bounds on various important parameters of error reduction polynomials. This includes a lower bound on the degree $d$ of the polynomial, and an $n^{\Omega(d)}$ lower bound on $L_1$-norm of an $n$-variate polynomial. These lower bounds hold both when there are no "correlations" between different approximations and in the presence of such. A delicate use of these correlations has recently been exploited for constructing improved weighted PRGs for various restricted models [CHLTW'23].
Sun, 12 May 2024 19:30:31 +0300https://eccc.weizmann.ac.il/report/2024/090
- TR24-089 | Tight Bounds for the Zig-Zag Product |
Gil Cohen,
Gal Maor,
Itay Cohen
https://eccc.weizmann.ac.il/report/2024/089The Zig-Zag product of two graphs, $Z = G \circ H$, was introduced in the seminal work of Reingold, Vadhan, and Wigderson (Ann. of Math. 2002) and has since become a pivotal tool in theoretical computer science. The classical bound, which is used throughout, states that the spectral expansion of the Zig-Zag product can be bounded roughly by the sum of the spectral expansions of the individual graphs, $\omega_Z \le \omega_H + \omega_G$.
In this work we derive, for every (vertex-transitive) $c$-regular graph $H$ on $d$ vertices, a tight bound for $\omega_Z$ by taking into account the entire spectrum of $H$. Our work reveals that the bound, which holds for every graph $G$, is precisely the minimum value of the function
$$
\frac{x}{c^2}\cdot\sqrt{1-\frac{d\cdot h(x)}{x\cdot h'(x)}}
$$
in the domain $(c^2,\infty)$, where $h(x)$ is the characteristic polynomial of $H^2$. As a consequence, we establish that Zig-Zag products are indeed intrinsically quadratic away from being Ramanujan.
We further prove tight bounds for the spectral expansion of the more fundamental replacement product. Our lower bounds are based on results from analytic combinatorics, and we make use of finite free probability to prove their tightness. In a broader context, our work uncovers intriguing links between the two fields and these well-studied graph operators.Wed, 08 May 2024 23:03:01 +0300https://eccc.weizmann.ac.il/report/2024/089
- TR24-088 | Locally Testable Tree Codes |
Tamer Mour,
Alon Rosen,
Ron Rothblum
https://eccc.weizmann.ac.il/report/2024/088Tree codes, introduced in the seminal works of Schulman (STOC 93', IEEE Transactions on Information Theory 96') are codes designed for interactive communication. Encoding in a tree code is done in an online manner: the $i$-th codeword symbol depends only on the first $i$ message symbols. Codewords should have good tree distance meaning that for any two codewords, starting at the first point of divergence, they should have large Hamming distance.
We investigate whether tree codes can be made to be locally testable. That is, can a tester, which is given oracle access to an alleged codeword $w$ of the tree code, decide whether $w$ is indeed a codeword or far from such, while only reading a sub-linear number of symbols from $w$.
As the main result of this work, we construct, for any $r\geq 3$, a probabilistic tree code that is locally testable using $\tilde{O}(n^{2/r})$ queries. The tester accepts any codeword with probability $1$ and rejects strings that are $\delta_r$-far from the code with high probability, where $\delta_r < 1$ degrades with $r$. Our probabilistic notion of a tree code is a relaxation of the standard notion and allows the encoder to toss random coins. We require that encoded messages are far (in tree distance) from any possible encoding of any other message.Sun, 05 May 2024 07:56:01 +0300https://eccc.weizmann.ac.il/report/2024/088
- TR24-087 | Directed Isoperimetry and Monotonicity Testing: A Dynamical Approach |
Renato Ferreira Pinto Jr.
https://eccc.weizmann.ac.il/report/2024/087This paper explores the connection between classical isoperimetric inequalities, their directed analogues, and monotonicity testing. We study the setting of real-valued functions $f : [0,1]^d \to \mathbb{R}$ on the solid unit cube, where the goal is to test with respect to the $L^p$ distance. Our goals are twofold: to further understand the relationship between classical and directed isoperimetry, and to give a monotonicity tester with sublinear query complexity in this setting.
Our main results are 1) an $L^2$ monotonicity tester for $M$-Lipschitz functions with query complexity $\widetilde O(\sqrt{d} M^2 / \epsilon^2)$ and, behind this result, 2) the directed PoincarĂ© inequality $\text{dist}^{mono}_2(f)^2 \le C \mathbb{E}[|\nabla^- f|^2]$, where the "directed gradient" operator $\nabla^-$ measures the local violations of monotonicity of $f$.
To prove the second result, we introduce a partial differential equation (PDE), the directed heat equation, which takes a one-dimensional function $f$ into a monotone function $f^*$ over time and enjoys many desirable analytic properties. We obtain the directed PoincarĂ© inequality by combining convergence aspects of this PDE with the theory of optimal transport. Crucially for our conceptual motivation, this proof is in complete analogy with the mathematical physics perspective on the classical PoincarĂ© inequality, namely as characterizing the convergence of the standard heat equation toward equilibrium.
Sun, 05 May 2024 07:53:34 +0300https://eccc.weizmann.ac.il/report/2024/087
- TR24-086 | A nearly-$4\log n$ depth lower bound for formulas with restriction on top |
Hao Wu
https://eccc.weizmann.ac.il/report/2024/086One of the major open problems in complexity theory is to demonstrate an explicit function which requires super logarithmic depth, a.k.a, the $\mathbf{P}$ versus $\mathbf{NC^1}$ problem. The current best depth lower bound is $(3-o(1))\cdot \log n$, and it is widely open how to prove a super-$3\log n$ depth lower bound. Recently Mihajlin and Sofronova (CCC'22) show if considering formulas with restriction on top, we can break the $3\log n$ barrier. Formally, they prove there exist two functions $f:\{0,1\}^n \rightarrow \{0,1\},g:\{0,1\}^n \rightarrow \{0,1\}^n$, such that for any constant $0<\alpha<0.4$ and constant $0<\epsilon<\alpha/2$, their XOR composition $f(g(x)\oplus y)$ is not computable by an AND of $2^{(\alpha-\epsilon)n}$ formulas of size at most $2^{(1-\alpha/2-\epsilon)n}$. This implies a modified version of Andreev function is not computable by any circuit of depth $(3.2-\epsilon)\log n$ with the restriction on t top $0.4-\epsilon$ layers only consist of AND gates for any small constant $0<\epsilon$. They ask whether the parameter $\alpha$ can be push up to nearly $1$ thus implying a nearly-$3.5\log n$ depth lower bound.
In this paper, we provide a stronger answer to their question. We show there exist two functions $f:\{0,1\}^n \rightarrow \{0,1\},g:\{0,1\}^n \rightarrow \{0,1\}^n$, such that for any constant $0<\alpha<2-o(1)$, their XOR composition $f(g(x)\oplus y)$ is not computable by an AND of $2^{\alpha n}$ formulas of size at most $2^{(1-\alpha/2-o(1))n}$. This implies a $(4-o(1))\log n$ depth lower bound with the restriction that top $2-o(1)$ layers only consist of AND gates. We prove it by observing that one crucial component in Mihajlin and Sofronova's work, called the well-mixed set of functions, can be significantly simplified thus improved. Then with this observation and a more careful analysis, we obtain these nearly tight results.Tue, 30 Apr 2024 11:16:09 +0300https://eccc.weizmann.ac.il/report/2024/086
- TR24-085 | Impagliazzo's Worlds Through the Lens of Conditional Kolmogorov Complexity |
Zhenjian Lu,
Rahul Santhanam
https://eccc.weizmann.ac.il/report/2024/085We develop new characterizations of Impagliazzo's worlds Algorithmica, Heuristica and Pessiland by the intractability of conditional Kolmogorov complexity $\mathrm{K}$ and conditional probabilistic time-bounded Kolmogorov complexity $\mathrm{pK}^t$.
In our first set of results, we show that $\mathrm{NP} \subseteq \mathrm{BPP}$ iff $\mathrm{pK}^t(x \mid y)$ can be computed efficiently in the worst case when $t$ is sublinear in $|x| + |y|$; $\mathrm{DistNP} \subseteq \mathrm{HeurBPP}$ iff $\mathrm{pK}^t(x \mid y)$ can be computed efficiently over all polynomial-time samplable distributions when $t$ is sublinear in $|x| + |y|$; and infinitely-often one-way functions fail to exist iff $\mathrm{pK}^t(x \mid y)$ can be computed efficiently over all polynomial-time samplable distributions for $t$ a sufficiently large polynomial in $|x| + |y|$. These results characterize Impagliazzo's worlds Algorithmica, Heuristica and Pessiland purely in terms of the tractability of conditional $\mathrm{pK}^t$. Notably, the results imply that Pessiland fails to exist iff the average-case intractability of conditional $\mathrm{pK}^t$ is insensitive to the difference between sub-linear and polynomially bounded $t$. As a corollary, while we prove conditional $\mathrm{pK}^t$ to be $\mathrm{NP}$-hard for sublinear $t$, showing $\mathrm{NP}$-hardness for large enough polynomially bounded $t$ would eliminate Pessiland as a possible world of average-case complexity.
In our second set of results, we characterize Impagliazzo's worlds Algorithmica, Heuristica and Pessiland by the distributional tractability of a natural problem, i.e., approximating the conditional Kolmogorov complexity, that is provably intractable in the worst case. We show that $\mathrm{NP} \subseteq \mathrm{BPP}$ iff conditional Kolmogorov complexity can be approximated in the semi-worst case; and $\mathrm{DistNP} \subseteq \mathrm{HeurBPP}$ iff conditional Kolmogorov complexity can be approximated on average over all independent polynomial-time samplable distributions. It follows from a result by Ilango, Ren, and Santhanam (STOC 2022) that infinitely-often one-way functions fail to exist iff conditional Kolmogorov complexity can be approximated on average over all polynomial-time samplable distributions. Together, these results yield the claimed characterizations. Our techniques, combined with previous work, also yield a characterization of auxiliary-input one-way functions and equivalences between different average-case tractability assumptions for conditional Kolmogorov complexity and its variants. Our results suggest that novel average-case tractability assumptions such as tractability in the semi-worst case and over independent polynomial-time samplable distributions might be worthy of further study.Sun, 28 Apr 2024 18:49:33 +0300https://eccc.weizmann.ac.il/report/2024/085