ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usThu, 17 Jan 2019 18:40:39 +0200TR19-007 | Lower Bounds for Linear Decision Lists |
Arkadev Chattopadhyay,
Meena Mahajan,
Nikhil Mande,
Nitin Saurabh
https://eccc.weizmann.ac.il/report/2019/007We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions.
We use this technique to prove an explicit lower bound by showing that any linear decision list computing the function $MAJ \circ XOR$ requires size $2^{0.18 n}$. This completely answers an open question of Tur{\'a}n and Vatan [FoCM'97]. We also show that the spectral classes $PL_1, PL_\infty$, and the polynomial threshold function classes $\widehat{PT}_1, PT_1$, are incomparable to linear decision lists.
Thu, 17 Jan 2019 18:40:39 +0200https://eccc.weizmann.ac.il/report/2019/007TR19-006 | Upper Bounds on Communication in terms of Approximate Rank |
Anna Gal,
Ridwan Syed
https://eccc.weizmann.ac.il/report/2019/006We show that any Boolean function with approximate rank $r$ can be computed by bounded error quantum protocols without prior entanglement of complexity $O( \sqrt{r} \log r)$. In addition, we show that any Boolean function with approximate rank $r$ and discrepancy $\delta$ can be computed by deterministic protocols of complexity $O(r)$, and private coin bounded error randomized protocols of complexity $O((\frac{1}{\delta})^2 + \log r)$. Our results yield lower bounds on approximate rank. We also obtain a strengthening of Newman's theorem with respect to approximate rank.
Thu, 17 Jan 2019 00:58:33 +0200https://eccc.weizmann.ac.il/report/2019/006TR19-005 | An Exponential Lower Bound on the Sub-Packetization of MSR Codes |
Omar Alrabiah,
Venkatesan Guruswami
https://eccc.weizmann.ac.il/report/2019/005An $(n,k,\ell)$-vector MDS code is a $\mathbb{F}$-linear subspace of $(\mathbb{F}^\ell)^n$ (for some field $\mathbb{F}$) of dimension $k\ell$, such that any $k$ (vector) symbols of the codeword suffice to determine the remaining $r=n-k$ (vector) symbols. The length $\ell$ of each codeword symbol is called the sub-packetization of the code. Such a code is called minimum storage regenerating (MSR), if any single symbol of a codeword can be recovered by downloading $\ell/r$ field elements (which is known to be the least possible) from each of the other symbols.
MSR codes are attractive for use in distributed storage systems, and by now a variety of ingenious constructions of MSR codes are available. However, they all suffer from exponentially large sub-packetization of at least $r^{k/r}$. Our main result is an almost tight lower bound showing that for an MSR code, one must have $\ell \ge \exp(\Omega(k/r))$. Previously, a lower bound of $\approx \exp(\sqrt{k/r})$, and a tight lower bound for a restricted class of optimal access MSR codes, were known. Our work settles a key question concerning MSR codes that has received much attention, with a short proof hinging on one key definition that is somewhat inspired by Galois theory.Wed, 16 Jan 2019 20:36:24 +0200https://eccc.weizmann.ac.il/report/2019/005TR19-004 | UG-hardness to NP-hardness by Losing Half |
Amey Bhangale,
Subhash Khot
https://eccc.weizmann.ac.il/report/2019/004The $2$-to-$2$ Games Theorem of [KMS-1, DKKMS-1, DKKMS-2, KMS-2] implies that it is NP-hard to distinguish between Unique Games instances with assignment satisfying at least $(\frac{1}{2}-\varepsilon)$ fraction of the constraints $vs.$ no assignment satisfying more than $\varepsilon$ fraction of the constraints, for every constant $\varepsilon>0$. We show that the reduction can be transformed in a non-trivial way to give a stronger guarantee in the completeness case: For at least $(\frac{1}{2}-\varepsilon)$ fraction of the vertices on one side, all the constraints associated with them in the Unique Games instance can be satisfied.
We use this guarantee to convert the known UG-hardness results to NP-hardness. We show:
1. Tight inapproximability of approximating independent sets in a degree $d$ graphs within a factor of $\Omega\left(\frac{d}{\log^2 d}\right)$, where $d$ is a constant.
2. NP-hardness of approximate Maximum Acyclic Subgraph problem within a factor of $\frac{2}{3}+\varepsilon$, improving the previous ratio of $\frac{14}{15}+\varepsilon$ by Austrin et al.[AMW15].
3. For any predicate $P^{-1}(1) \subseteq [q]^k$ supporting balanced pairwise independent distribution, given a $P$-CSP instance with value at least $\frac{1}{2}-\varepsilon$, it is NP-hard to satisfy more than $\frac{|P^{-1}(1)|}{q^k}+\varepsilon$ fraction of constraints.
Sun, 13 Jan 2019 09:45:37 +0200https://eccc.weizmann.ac.il/report/2019/004TR19-003 | Near-Optimal Lower Bounds on the Threshold Degree and Sign-Rank of AC^0 |
Alexander A. Sherstov,
Pei Wu
https://eccc.weizmann.ac.il/report/2019/003The threshold degree of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign: $\mathrm{sgn}\; p(x)=(-1)^{f(x)}.$ A related notion is sign-rank, defined for a Boolean matrix $F=[F_{ij}]$ as the minimum rank of a real matrix $M$ with $\mathrm{sgn}\; M_{ij}=(-1)^{F_{ij}}$. Determining the maximum threshold degree and sign-rank achievable by constant-depth circuits ($\text{AC}^{0}$) is a well-known and extensively studied open problem, with complexity-theoretic and algorithmic applications.
We give an essentially optimal solution to this problem. For any $\epsilon>0,$ we construct an $\text{AC}^{0}$ circuit in $n$ variables that has threshold degree $\Omega(n^{1-\epsilon})$ and sign-rank $\exp(\Omega(n^{1-\epsilon})),$ improving on the previous best lower bounds of $\Omega(\sqrt{n})$ and $\exp(\tilde{\Omega}(\sqrt{n}))$, respectively. Our results subsume all previous lower bounds on the threshold degree and sign-rank of $\text{AC}^{0}$ circuits of any given depth, with a strict improvement starting at depth $4$. As a corollary, we also obtain near-optimal bounds on the discrepancy, threshold weight, and threshold density of $\text{AC}^{0}$, strictly subsuming previous work on these quantities. Our work gives some of the strongest lower bounds to date on the communication complexity of $\text{AC}^{0}$.Sun, 06 Jan 2019 10:28:49 +0200https://eccc.weizmann.ac.il/report/2019/003TR19-002 | Complexity of Linear Operators |
Alexander Kulikov,
Ivan Mikhailin,
Vladimir Podolskii,
Andrey Mokhov
https://eccc.weizmann.ac.il/report/2019/002Let $A \in \{0,1\}^{n \times n}$ be a matrix with $z$ zeroes and $u$ ones and $x$ be an $n$-dimensional vector of formal variables over a semigroup $(S, \circ)$. How many semigroup operations are required to compute the linear operator $Ax$?
As we observe in this paper, this problem contains as a special case the well-known range queries problem and has a rich variety of applications in such areas as graph algorithms, functional programming, circuit complexity, and others. It is easy to compute $Ax$ using $O(u)$ semigroup operations. The main question studied in this paper is: can $Ax$ be computed using $O(z)$ semigroup operations? We prove that in general this is not possible: there exists a matrix $A \in \{0,1\}^{n \times n}$ with exactly two zeroes in every row (hence $z=2n$) whose complexity is $\Theta(n\alpha(n))$ where $\alpha(n)$ is the inverse Ackermann function. However, for the case when the semigroup is commutative, we give a constructive proof of an $O(z)$ upper bound. This implies that in commutative settings, complements of sparse matrices can be processed as efficiently as sparse matrices (though the corresponding algorithms are more involved). Note that this covers the cases of Boolean and tropical semirings that have numerous applications, e.g., in graph theory.
As a simple application of the presented linear-size construction, we show how to multiply two $n\times n$ matrices over an arbitrary semiring in $O(n^2)$ time if one of these matrices is a 0/1-matrix with $O(n)$ zeroes (i.e., a complement of a sparse matrix).Sun, 06 Jan 2019 07:55:08 +0200https://eccc.weizmann.ac.il/report/2019/002TR19-001 | On OBDD-based algorithms and proof systems that dynamically change order of variables |
Alexander Knop,
Dmitry Itsykson,
Dmitry Sokolov,
Andrei Romashchenko
https://eccc.weizmann.ac.il/report/2019/001In 2004 Atserias, Kolaitis and Vardi proposed OBDD-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of identically false OBDD from OBDDs representing clauses of the initial formula. All OBDDs in such proofs have the same order of variables. We initiate the study of OBDD based proof systems that additionally contain a rule that allows changing the order in OBDDs. At first, we consider a proof system OBDD($\land$, reordering) that uses the conjunction (join) rule and the rule that allows changing the order. We exponentially separate this proof system from OBDD($\land$) proof system that uses only the conjunction rule. We prove two exponential lower bounds on the size of OBDD($\land$, reordering) refutations of Tseitin formulas and the pigeonhole principle. The first lower bound was previously unknown even for OBDD($\land$) proofs and the second one extends the result of Tveretina et al. from OBDD($\land$) to OBDD($\land$, reordering).
In 2004 Pan and Vardi proposed an approach to the propositional satisfiability problem based on OBDDs and symbolic quantifier elimination (we denote algorithms based on this approach as OBDD($\land$, $\exists$) algorithms). An instance of the propositional satisfiability problem is considered as an existential quantified propositional formula. The algorithm chooses an order on variables and creates an ordered binary decision diagram (OBDD) $D$ that initially represents the constant $1$ function. Then the algorithm downloads to $D$ clauses of the CNF one by one, and applies to $D$ the elimination of the existential quantifier for variable $x$ if all clauses that contain $x$ are already downloaded. We augment these algorithms with the operation of reordering of variables and call the new scheme OBDD($\land$, $\exists$, reordering) algorithms. We notice that there exists an OBDD($\land$, $\exists$) algorithm that solves satisfiable and unsatisfiable Tseitin formulas in polynomial time. In contrast, we show that there exist formulas representing systems of linear equations over $\mathbb{F}_2$ that are hard for OBDD($\land$, $\exists$, reordering) algorithms. Our hard instances are satisfiable formulas representing systems of linear equations over $\mathbb{F}_2$ that
correspond to some checksum matrices of error correcting codes.Sat, 05 Jan 2019 09:55:37 +0200https://eccc.weizmann.ac.il/report/2019/001TR18-213 | The Power of Distributed Verifiers in Interactive Proofs |
Eylon Yogev,
Moni Naor,
Merav Parter
https://eccc.weizmann.ac.il/report/2018/213We explore the power of interactive proofs with a distributed verifier. In this setting, the verifier consists of $n$ nodes and a graph $G$ that defines their communication pattern. The prover is a single entity that communicates with all nodes by short messages. The goal is to verify that the graph $G$ belongs to some language in a small number of rounds, and with small communication bound, i.e., the proof size.
This interactive model was introduced by Kol, Oshman and Saxena (PODC 2018) as a generalization of non-interactive distributed proofs. They demonstrated the power of interaction in this setting by constructing protocols for problems as Graph Symmetry and Graph Non-Isomorphism -- both of which require proofs of $\Omega(n^2)$-bits without interaction.
In this work, we provide a new general framework for distributed interactive proofs that allows one to translate standard interactive protocols (i.e., with a centralized verifier) to ones where the verifier is distributed with a proof size that depends on the computational complexity of the verification algorithm run by the centralized verifier.
We show the following:
* Every (centralized) computation that can be performed in time $O(n)$ can be translated into three-round distributed interactive protocol with $O(\log n)$ proof size. This implies that many graph problems for sparse graphs have succinct proofs (e.g., testing planarity).
* Every (centralized) computation implemented by either a small space or by uniform NC circuit can be translated into a distributed protocol with $O(1)$ rounds and $O(\log n)$ bits proof size for the low space case and $polylog(n)$ many rounds and proof size for NC.
* We also demonstrate the power of our compilers for problems not captured by the above families. We show that for Graph Non-Isomorphism, one of the striking demonstrations of the power of interaction, there is a 4-round protocol with $O(\log n)$ proof size, improving upon the $O(n \log n)$ proof size of Kol et al.
* For many problems we show how to reduce proof size below the naturally seeming barrier of $\log n$. By employing our RAM compiler, we get a 5-round protocols with proof size $O(\log \log n)$ for a family of problems including Fixed Automorphism, Clique and Leader Election (for the later two problems we actually get $O(1)$ proof size).
* Finally we discuss how to make these proofs non-interactive arguments via random oracles.
Our compilers capture many natural problems and demonstrates the difficultly in showing lower bounds in these regimes. Fri, 28 Dec 2018 10:02:29 +0200https://eccc.weizmann.ac.il/report/2018/213TR18-212 | Constructing Faithful Homomorphisms over Fields of Finite Characteristic |
Prerona Chatterjee,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2018/212We study the question of algebraic rank or transcendence degree preserving homomorphisms over finite fields. This concept was first introduced by Beecken, Mittmann and Saxena (Information and Computing, 2013), and exploited by them, and Agrawal, Saha, Saptharishi and Saxena (Journal of Computing, 2016) to design algebraic independence based identity tests using the Jacobian criterion over characteristic zero fields. An analogue of such constructions over finite characteristic fields was unknown due to the failure of the Jacobian criterion over finite characteristic fields.
Building on a recent criterion of Pandey, Sinhababu and Saxena (MFCS, 2016), we construct explicit faithful maps for some natural classes of polynomials in the positive characteristic field setting, when a certain parameter called the inseparable degree of the underlying polynomials is bounded (this parameter is always 1 in fields of characteristic zero). This presents the first generalisation of some of the results of Beecken et al. and Agrawal et al. in the positive characteristic setting.Wed, 26 Dec 2018 16:56:28 +0200https://eccc.weizmann.ac.il/report/2018/212TR18-211 | Parametric Shortest Paths in Planar Graphs |
Kshitij Gajjar,
Jaikumar Radhakrishnan
https://eccc.weizmann.ac.il/report/2018/211We construct a family of planar graphs $(G_n: n\geq 4)$, where $G_n$ has $n$ vertices including a source vertex $s$ and a sink vertex $t$, and edge weights that change linearly with a parameter $\lambda$ such that, as $\lambda$ increases, the cost of the shortest path from $s$ to $t$ has $n^{\Omega(\log n)}$ break points. This shows that lower bounds obtained earlier by Carstensen (1983) and Mulmuley & Shah (2000) for general graphs also hold for planar graphs. A conjecture of Nikolova (2009) states that the number of break points in $n$-vertex planar graphs is bounded by a polynomial in $n$; our result refutes this conjecture.
Gusfield (1980) and Dean (2009) showed that the number of break points for an $n$-vertex graph is $n^{\log n + O(1)}$ assuming linear edge weights; we show that if the edge weights are allowed to vary as a polynomial of degree at most $d$, then the number of break points is $n^{\log n + O(\alpha(n)^d)}$, where $\alpha(n)$ is the slowly growing inverse Ackermann function. This upper bound arises from Davenport-Schinzel sequences.Wed, 12 Dec 2018 17:10:30 +0200https://eccc.weizmann.ac.il/report/2018/211