ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usMon, 18 Jan 2021 18:02:07 +0200TR21-007 | Almost Optimal Inapproximability of Multidimensional Packing Problems |
Sai Sandeep
https://eccc.weizmann.ac.il/report/2021/007Multidimensional packing problems generalize the classical packing problems such as Bin Packing, Multiprocessor Scheduling by allowing the jobs to be $d$-dimensional vectors. While the approximability of the scalar problems is well understood, there has been a significant gap between the approximation algorithms and the hardness results for the multidimensional variants. In this paper, we close this gap by giving almost tight hardness results for these problems.
1. We show that Vector Bin Packing has no $\Omega( \log d)$ factor asymptotic approximation algorithm when $d$ is a large constant, assuming $P \neq NP$. This matches the $\ln d + O(1)$ factor approximation algorithms (Chekuri, Khanna SICOMP 2004, Bansal, Caprara, Sviridenko SICOMP 2009, Bansal, Eliáš, Khan SODA 2016) upto constants.
2. We show that Vector Scheduling has no polynomial time algorithm with an approximation ratio of $\Omega\left( (\log d)^{1-\epsilon}\right)$ when $d$ is part of the input, assuming NP has no quasipolynomial time algorithms. This almost matches the $O\left( \frac{\log d}{\log \log d}\right)$ factor algorithms(Harris, Srinivasan JACM 2019, Im, Kell, Kulkarni, Panigrahi SICOMP 2019). We also show that the problem is NP-hard to approximate within $(\log \log d)^{\omega(1)}$.
3. We show that Vector Bin Covering is NP-hard to approximate within $\Omega\left( \frac{\log d}{\log \log d}\right)$ when $d$ is part of the input, almost matching the $O(\log d)$ factor algorithm (Alon et al., Algorithmica 1998).
Previously, no hardness results that grow with $d$ were known for Vector Scheduling and Vector Bin Covering when $d$ is part of the input and for Vector Bin Packing when $d$ is a fixed constant. Mon, 18 Jan 2021 18:02:07 +0200https://eccc.weizmann.ac.il/report/2021/007TR21-006 | How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity) |
Susanna de Rezende,
Jakob Nordström,
Marc Vinyals
https://eccc.weizmann.ac.il/report/2021/006We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large coefficients. These are also the first trade-offs to hold uniformly for resolution, polynomial calculus and cutting planes, thus capturing the main methods of reasoning used in current state-of-the-art SAT solvers.
We prove our results by a reduction to communication lower bounds in a round-efficient version of the real communication model of [Krají$\check{c}$ek '98], drawing on and extending techniques in [Raz and McKenzie '99] and [Göös et al. '15]. Such lower bounds are in turn established by a reduction to trade-offs between cost and number of rounds in the game of [Dymond and Tompa '85] played on directed acyclic graphs.
As a by-product of the techniques developed to show these proof complexity trade-off results, we also obtain a separation between $\textrm{monotone-AC}^{i-1}$ and $\textrm{monotone-NC}^{i}$, and an exponential separation between $\textrm{monotone-AC}^{i-1}$ and $\textrm{monotone-AC}^{i}$, improving exponentially over the superpolynomial separation in [Raz and McKenzie '99].Mon, 18 Jan 2021 17:55:43 +0200https://eccc.weizmann.ac.il/report/2021/006TR21-005 | Robust testing of low-dimensional functions |
Anindya De,
Elchanan Mossel,
Joe Neeman
https://eccc.weizmann.ac.il/report/2021/005A natural problem in high-dimensional inference is to decide if a classifier $f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of linear directions of its input data. Call a function $g: \mathbb{R}^n \rightarrow \{-1,1\}$, a linear $k$-junta if it is completely determined by some $k$-dimensional subspace of the input space. A recent work of the authors showed that linear $k$-juntas are testable. Thus there exists an algorithm to distinguish between:
1. $f: \mathbb{R}^n \rightarrow \{-1,1\}$ which is a linear $k$-junta with surface area $s$,
2. $f$ is $\epsilon$-far from any linear $k$-junta with surface area $(1+\epsilon)s$, where the query complexity of the algorithm is independent of the ambient dimension $n$.
Following the surge of interest in noise-tolerant property testing, in this paper we prove a noise-tolerant (or robust) version of this result. Namely, we give an algorithm which given any $c>0$, $\epsilon>0$, distinguishes between
1. $f: \mathbb{R}^n \rightarrow \{-1,1\}$ has correlation at least $c$ with some linear $k$-junta with surface area $s$.
2. $f$ has correlation at most $c-\epsilon$ with any linear $k$-junta with surface area at most $s$. The query complexity of our tester is $k^{\mathrm{poly}(s/\epsilon)}$.
Using our techniques, we also obtain a fully noise tolerant tester with the same query complexity for any class $\mathcal{C}$ of linear $k$-juntas with surface area bounded by $s$. As a consequence, we obtain a fully noise tolerant tester with query complexity $k^{O(\mathrm{poly}(\log k/\epsilon))}$ for the class of intersection of $k$-halfspaces (for constant $k$) over the Gaussian space. Our query complexity is independent of the ambient dimension $n$. Previously, no non-trivial noise tolerant testers were known even for a single halfspace.Wed, 13 Jan 2021 01:28:41 +0200https://eccc.weizmann.ac.il/report/2021/005TR21-004 | Junta Distance Approximation with Sub-Exponential Queries |
Vishnu Iyer,
Avishay Tal,
Michael Whitmeyer
https://eccc.weizmann.ac.il/report/2021/004Leveraging tools of De, Mossel, and Neeman [FOCS, 2019], we show two different results pertaining to the tolerant testing of juntas. Given black-box access to a Boolean function $f:\{\pm1\}^{n} \to \{\pm1\}$ we give a poly$(k, \frac{1}{\varepsilon})$ query algorithm that distinguishes between functions that are $\gamma$-close to $k$-juntas and $(\gamma+\varepsilon)$-far from $k'$-juntas, where $k' = O(\frac{k}{\varepsilon^2})$. In the non-relaxed setting, we extend our ideas to give a $2^{\tilde{O}(\sqrt{k}/\varepsilon)}$ (adaptive) query algorithm that distinguishes between functions that are $\gamma$-close to $k$-juntas and $(\gamma+\varepsilon)$-far from $k$-juntas. To the best of our knowledge, this is the first subexponential-in-$k$ query algorithm for approximating the distance of $f$ to being a $k$-junta (previous results of Blais, Canonne, Eden, Levi, and Ron [SODA, 2018] and De, Mossel, and Neeman [FOCS, 2019] required exponentially many queries in $k$). Our techniques are Fourier analytical and introduce the new notion of "normalized influences'' that might be of independent interest.Sun, 10 Jan 2021 18:21:56 +0200https://eccc.weizmann.ac.il/report/2021/004TR21-003 | Inverse-Exponential Correlation Bounds and Extremely Rigid Matrices from a New Derandomized XOR Lemma |
Lijie Chen,
Xin Lyu
https://eccc.weizmann.ac.il/report/2021/003
In this work we prove that there is a function $f \in \textrm{E}^\textrm{NP}$ such that, for every sufficiently large $n$ and $d = \sqrt{n}/\log n$, $f_n$ ($f$ restricted to $n$-bit inputs) cannot be $(1/2 + 2^{-d})$-approximated by $\textrm{F}_2$-polynomials of degree $d$. We also observe that a minor improvement (e.g., improving $d$ to $n^{1/2+\varepsilon}$ for any $\varepsilon > 0$) over our result will imply $\textrm{E}^\textrm{NP}$ cannot be computed by depth-$3$ $\textrm{AC}^0$-circuits of $2^{n^{1/2 + \varepsilon}}$ size, which is a notoriously hard open question in complexity theory.
Using the same proof techniques, we are also able to construct extremely rigid matrices over $\textrm{F}_2$ in $\textrm{P}^\textrm{NP}$. More specifically, we show that for every constant $\varepsilon \in (0,1)$, there is a $\textrm{P}^\textrm{NP}$ algorithm which on input $1^n$ outputs an $n\times n$ $\textrm{F}_2$-matrix $H_n$ satisfying $\mathcal{R}_{H_n}(2^{\log^{1 - \varepsilon} n}) \ge (1/2 - \exp(-\log^{2/3 \cdot \varepsilon} n) ) \cdot n^2$, for every sufficiently large $n$. This improves the recent $\textrm{P}^\textrm{NP}$ constructions of rigid matrices in [Alman and Chen, FOCS 2019] and [Bhangale et al., FOCS 2020], which only gives $\Omega(n^2)$ rigidity.
The key ingredient in the proof of our new results is a new derandomized XOR lemma based on approximate linear sums, which roughly says that given an $n$-input function $f$ which cannot be $0.99$-approximated by certain linear sum of $s$ many functions in $\mathcal{F}$ within $\ell_1$-distance, one can construct a new function $\textrm{Amp}^f$ with $\widetilde{O}(n)$ input bits, which cannot be $(1/2+s^{\Omega(1)})$-approximated by $\mathcal{F}$-functions. Taking $\mathcal{F}$ to be a function collection containing low-degree $\textrm{F}_2$-polynomials or low-rank $\textrm{F}_2$-matrices, our results are then obtained by first using the algorithmic method to construct a function which is weakly hard against linear sums of $\mathcal{F}$ in the above sense, and then apply the derandomized XOR lemma to $f$.
We obtain our new derandomized XOR lemma by giving a generalization of the famous hardcore lemma by Impagliazzo. Our generalization in some sense constructs a non-Boolean hardcore of a weakly hard function $f$ with respect to $\mathcal{F}$-functions, from the weak inapproximability of $f$ by any linear sum of $\mathcal{F}$ with bounded $\ell_p$-norm. This generalization recovers the original hardcore lemma by considering the $\ell_{\infty}$-norm. Surprisingly, when we switch to the $\ell_1$-norm, we immediately rediscover Levin's proof of Yao's XOR Lemma. That is, these first two proofs of Yao's XOR Lemma can be unified with our new perspective. For proving the correlation bounds, our new derandomized XOR lemma indeed works with the $\ell_{4/3}$-norm.Fri, 08 Jan 2021 23:03:46 +0200https://eccc.weizmann.ac.il/report/2021/003TR21-002 | Fooling Constant-Depth Threshold Circuits |
Pooya Hatami,
William Hoza,
Avishay Tal,
Roei Tell
https://eccc.weizmann.ac.il/report/2021/002We present new constructions of pseudorandom generators (PRGs) for two of the most widely-studied non-uniform circuit classes in complexity theory. Our main result is a construction of the first non-trivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and super-linear size. This PRG fools circuits with depth $d\in\mathbb{N}$ and $n^{1+\delta}$ wires, where $\delta = 2^{-O(d)}$, using seed length $O(n^{1-\delta})$ and with error $2^{-n^{\delta}}$. This tightly matches the best known lower bounds for this circuit class. As a consequence of our result, all the known hardness for LTF circuits has now effectively been translated into pseudorandomness. This brings the extensive effort in the last decade to construct PRGs and deterministic circuit-analysis algorithms for this class to the point where any subsequent improvement would yield breakthrough lower bounds.
Our second contribution is a PRG for De Morgan formulas of size $s$ whose seed length is $s^{1/3+o(1)} \cdot \mathrm{polylog}(1/\epsilon)$ for error $\epsilon$. In particular, our PRG can fool formulas of sub-cubic size $s=n^{3-\Omega(1)}$ with an exponentially small error $\epsilon=\exp({-n^{\Omega(1)}})$. This significantly improves the inverse-polynomial error of the previous state-of-the-art for such formulas by Impagliazzo, Meka, and Zuckerman (FOCS 2012), and again tightly matches the best currently-known lower bounds for this class.
In both settings, a key ingredient in our constructions is a pseudorandom restriction procedure that has tiny failure probability, but simplifies the function to a non-natural "hybrid computational model" that combines several computational models. As part of our proofs we also construct "extremely low-error" PRGs for related circuit classes; for example, we construct a PRG for the class of functions computable by an arbitrary function of $s$ linear threshold functions that can handle even the extreme setting of parameters $s=n/\mathrm{polylog}(n)$ and $\epsilon=2^{-n/\mathrm{polylog}(n)}$.Fri, 08 Jan 2021 23:01:25 +0200https://eccc.weizmann.ac.il/report/2021/002TR21-001 | Computation Over the Noisy Broadcast Channel with Malicious Parties |
Raghuvansh Saxena,
Gillat Kol,
Klim Efremenko,
Dmitry Paramonov
https://eccc.weizmann.ac.il/report/2021/001We study the $n$-party noisy broadcast channel with a constant fraction of malicious parties. Specifically, we assume that each non-malicious party holds an input bit, and communicates with the others in order to learn the input bits of all non-malicious parties. In each communication round, one of the parties broadcasts a bit to all other parties, and the bit received by each party is flipped with a fixed constant probability (independently for each recipient). How many rounds are needed?
Assuming there are no malicious parties, Gallager gave an $\mathcal{O}(n \log \log n)$-round protocol for the above problem, which was later shown to be optimal. This protocol, however, inherently breaks down in the presence of malicious parties.
We present a novel $n \cdot \tilde{\mathcal{O}}\left(\sqrt{\log n}\right)$-round protocol, that solves this problem even when almost half of the parties are malicious. Our protocol uses a new type of error correcting code, which we call a locality sensitive code and which may be of independent interest. Roughly speaking, these codes map "close" messages to "close" codewords, while messages that are not close are mapped to codewords that are very far apart.
We view our result as a first step towards a theory of property preserving interactive coding, i.e., interactive codes that preserve useful properties of the protocol being encoded. In our case, the naive protocol over the noiseless broadcast channel, where all the parties broadcast their input bit and output all the bits received, works even in the presence of malicious parties. Our simulation of this protocol, unlike Gallager's, preserves this property of the original protocol.Sun, 03 Jan 2021 23:04:23 +0200https://eccc.weizmann.ac.il/report/2021/001TR20-193 | Average-case rigidity lower bounds |
Xuangui Huang,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2020/193It is shown that there exists $f : \{0,1\}^{n/2} \times \{0,1\}^{n/2} \to \{0,1\}$ in E$^\mathbf{NP}$ such that for every $2^{n/2} \times 2^{n/2}$ matrix $M$ of rank $\le \rho$ we have $\P_{x,y}[f(x,y)\ne M_{x,y}] \ge 1/2-2^{-\Omega(k)}$, where $k \leq \Theta(\sqrt{n})$ and $\log \rho \leq \delta n/k(\log n + k)$ for a sufficiently small $\delta > 0$.
This generalizes recent results which bound below the probability by $1/2-\Omega(1)$ or apply to constant-depth circuits.
The result is a step towards obtaining data-structure lower bounds for E$^\mathbf{NP}$: they would follow from a better trade-off between the probability bound and $\rho$.
Tue, 29 Dec 2020 18:17:22 +0200https://eccc.weizmann.ac.il/report/2020/193TR20-192 | Constructing Large Families of Pairwise Far Permutations: Good Permutation Codes Based on the Shuffle-Exchange Network |
Oded Goldreich,
Avi Wigderson
https://eccc.weizmann.ac.il/report/2020/192
We consider the problem of efficiently constructing an as large as possible family of permutations such that each pair of permutations are far part (i.e., disagree on a constant fraction of their inputs).
Specifically, for every $n\in\N$, we present a collection of $N=N(n)=(n!)^{\Omega(1)}$ pairwise far apart permutations $\{\pi_i:[n]\to[n]\}_{i\in[N]}$ and a polynomial-time algorithm that on input $i\in[N]$ outputs an explicit description of $\pi_i$.
From a coding theoretic perspective, we construct permutation codes of constant relative distance and constant rate along with efficient encoding (and decoding) algorithms.
This construction is easily extended to produce codes on smaller alphabets in which every codeword is balanced; namely, each symbol appears the same number of times.
Our construction combines routing on the Shuffle-Exchange network with any good binary error correcting code.
Specifically, we uses codewords of a good binary code in order to determine the switching instructions in the Shuffle-Exchange network.
Sun, 27 Dec 2020 16:50:02 +0200https://eccc.weizmann.ac.il/report/2020/192TR20-191 | Negations Provide Strongly Exponential Savings |
Arkadev Chattopadhyay,
Rajit Datta,
Partha Mukhopadhyay
https://eccc.weizmann.ac.il/report/2020/191We show that there is a family of monotone multilinear polynomials over $n$ variables in VP, such that any monotone arithmetic circuit for it would be of size $2^{\Omega(n)}$. Before our result, strongly exponential lower bounds on the size of monotone circuits were known only for computing explicit polynomials in VNP. The family of polynomials we prescribe are the spanning tree polynomials, also considered by Jerrum and Snir (JACM,1982), but this time defined over constant-degree expander graphs. Sun, 27 Dec 2020 13:30:45 +0200https://eccc.weizmann.ac.il/report/2020/191