ECCC - Reportshttps://example.com/Latest Reports published at https://eccc.weizmann.ac.ilen-usMon, 01 May 2017 01:58:52 +0300TR17-079 | Optimal Interactive Coding for Insertions, Deletions, and Substitutions |
Alexander A. Sherstov,
Pei Wu
https://eccc.weizmann.ac.il/report/2017/079Interactive coding, pioneered by Schulman (FOCS 1992, STOC 1993), is concerned with making communication protocols resilient to adversarial noise. The canonical model allows the adversary to alter a small constant fraction of symbols, chosen at the adversary's discretion, as they pass through the communication channel. Braverman, Gelles, Mao, and Ostrovsky (2015) proposed a far-reaching generalization of this model, whereby the adversary can additionally manipulate the channel by removing and inserting symbols. For any $\epsilon>0,$ they showed how to faithfully simulate any protocol in this model with corruption rate up to $1/18-\epsilon,$ using a constant-size alphabet and a constant-factor overhead in communication.
We give an optimal simulation of any protocol in this generalized model of substitutions, insertions, and deletions, tolerating a corruption rate up to $1/4-\epsilon$ while keeping the alphabet to a constant size and the communication overhead to a constant factor. Our corruption tolerance matches an impossibility result for corruption rate $1/4$ which holds even for substitutions alone (Braverman and Rao, STOC 2011).Mon, 01 May 2017 01:58:52 +0300https://eccc.weizmann.ac.il/report/2017/079TR17-078 | Information Theoretic Continuously Non-Malleable Codes in the Constant Split-State Model |
Jesper Buus Nielsen,
Nico Döttling,
Maceij Obremski
https://eccc.weizmann.ac.il/report/2017/078We present an information-theoretically secure continuously non-malleable code in the constant split-state model, where there is a self-destruct mechanism which ensures that the adversary loses access to tampering after the first failed decoding. Prior to our result only codes with computational security were known for this model, and it has been an open problem to construct such a code with information theoretic security. As a conceptual contribution we also introduce the notion of a one-way non-malleable code, which is the main new ingredient in our construction. In this notion, the tampering adversary's goal is to recover the encoded message rather than to distinguish the encodings of two messages. Our technical contribution is two-fold.
1) We show how to construct a full fledged continuously non-malleable code from a one-way continuously non-malleable code while only increasing the number of states by a constant factor.
2) We construct a one-way continuously non-malleable code in the constant split state model with information theoretic security.
Mon, 01 May 2017 00:47:59 +0300https://eccc.weizmann.ac.il/report/2017/078TR17-077 | Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees |
Guillaume Lagarde,
Nutan Limaye,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2017/077We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $\mathbb{F}\langle x_1,\dots,x_N \rangle$, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse trees that appear in the circuit. Such restrictions capture essentially all non-commutative circuit models for which lower bounds are known. We prove several results about such circuits.
1. We show explicit exponential lower bounds for circuits with up to an exponential number of parse trees, strengthening the work of Lagarde, Malod, and Perifel (ECCC 2016), who prove such a result for Unique Parse Tree (UPT) circuits which have a single parse tree.
2. We show explicit exponential lower bounds for circuits whose parse trees are rotations of a single tree. This simultaneously generalizes recent lower bounds of Limaye, Malod, and Srinivasan (Theory of Computing 2016) and the above lower bounds of Lagarde et al., which are known to be incomparable.
3. We make progress on a question of Nisan (STOC 1991) regarding separating the power of Algebraic Branching Programs (ABPs) and Formulas in the non-commutative setting by showing a tight lower bound of $n^{\Omega(\log d)}$ for any UPT formula computing the product of $d$ $n\times n$ matrices.
When $d\leq \log n$, we can also prove superpolynomial lower bounds for formulas with up to $2^{o(d)}$ many parse trees (for computing the same polynomial). Improving this bound to allow for $2^{O(d)}$ trees would yield an unconditional separation between ABPs and Formulas.
4. We give deterministic white-box PIT algorithms for UPT circuits over any field (strengthening a result of Lagarde et al. (2016)) and also for sums of a constant number of UPT circuits with different parse trees.Sun, 30 Apr 2017 20:30:49 +0300https://eccc.weizmann.ac.il/report/2017/077TR17-076 | New Protocols for Conditional Disclosure of Secrets (and More) |
Tianren Liu,
Vinod Vaikuntanathan,
Hoeteck Wee
https://eccc.weizmann.ac.il/report/2017/076We present new protocols for conditional disclosure of secrets (CDS),
where two parties want to disclose a secret to a third party if and
only if their respective inputs satisfy some predicate.
- For general predicates $\text{pred} : [N] \times [N] \rightarrow \{0,1\}$,
we present two protocols that achieve $o(N^{1/2})$ communication: the
first achieves $O(N^{1/3})$ communication and the second achieves
sub-polynomial $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$
communication.
- As a corollary, we obtain improved share complexity for
forbidden graph access structures. Namely, for every graph on $N$
vertices, there is a secret-sharing scheme for $N$ parties in which
each pair of parties can reconstruct the secret if and only if the
corresponding vertices in $G$ are connected, and where each party gets
a share of size $2^{O(\sqrt{\log N \log\log N})} = N^{o(1)}$.
Prior to this work, the best protocols for both primitives required
communication complexity $\tilde{O}(N^{1/2})$.
Indeed, this is essentially the best that all prior techniques could
hope to achieve as they were limited to so-called ``linear reconstruction''.
This is the first work to break this $O(N^{1/2})$ ``linear reconstruction''
barrier in settings related to secret sharing. To obtain these results,
we draw upon techniques for non-linear reconstruction developed in the
context of information-theoretic private information retrieval.
We further extend our results to the setting of private simultaneous
messages (PSM), and provide applications such as an improved attribute-based
encryption (ABE) for quadratic polynomials.Sun, 30 Apr 2017 13:01:43 +0300https://eccc.weizmann.ac.il/report/2017/076TR17-075 | Fourier-Based Testing for Families of Distributions |
Clement Canonne,
Ilias Diakonikolas,
Alistair Stewart
https://eccc.weizmann.ac.il/report/2017/075We study the general problem of testing whether an unknown discrete distribution belongs to a given family of distributions. More specifically, given a class of distributions $\mathcal{P}$ and sample access to an unknown distribution $\mathbf{P}$, we want to distinguish (with high probability) between the case that $\mathbf{P} \in \mathcal{P}$ and the case that $\mathbf{P}$ is $\epsilon$-far, in total variation distance, from every distribution in $\mathcal{P}$. This is the prototypical hypothesis testing problem that has received significant attention in statistics and,
more recently, in theoretical computer science.
The sample complexity of this general problem depends on the underlying family $\mathcal{P}$. We are interested in designing sample-optimal and computationally efficient algorithms for this task. The main contribution of this work is a new and simple testing technique that is applicable to distribution families whose Fourier spectrum approximately satisfies a certain sparsity property. As the main applications of our Fourier-based testing technique, we obtain the first non-trivial testers for two fundamental families of discrete distributions: Sums of Independent Integer Random Variables (SIIRVs) and Poisson Multinomial Distributions (PMDs). Our testers for these families are nearly sample-optimal and computationally efficient. We also obtain a tester with improved sample complexity for discrete log-concave distributions. To the best of our knowledge, ours is the first use of the Fourier transform in the context of distribution testing.Sat, 29 Apr 2017 21:31:23 +0300https://eccc.weizmann.ac.il/report/2017/075TR17-074 | Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings |
Vikraman Arvind,
Rajit Datta,
Partha Mukhopadhyay,
Raja S
https://eccc.weizmann.ac.il/report/2017/074In this paper we study arithmetic computations over non-associative, and non-commutative free polynomials ring $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. Prior to this work, the non-associative arithmetic model of computation was considered by Hrubes, Wigderson, and Yehudayoff [HWY10]. They were interested in completeness and explicit lower bound results.
We focus on two main problems in algebraic complexity theory: Polynomial Identity Testing (PIT) and polynomial factorization over $\mathbb{F}\{x_1,x_2,\ldots,x_n\}$. We show the following results.
(1) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $f\in \mathbb{F} \{x_1,x_2,\ldots,x_n\}$
of degree $d$, we give a deterministic $poly(n,s,d)$ algorithm to decide if $f$ is identically zero polynomial or not.
Our result is obtained by a suitable adaptation of the PIT algorithm of Raz-Shpilka [RS05] for non-commutative ABPs.
(2) Given an arithmetic circuit $C$ of size $s$ computing a polynomial $f\in \mathbb{F}\{x_1,x_2,\ldots,x_n\}$ of degree $d$, we give an efficient deterministic algorithm to compute the circuits for the irreducible factors of $f$ in time $poly(n,s,d)$ when $\mathbb{F}=\mathbb{Q}$.
Over finite fields of characteristic $p$, our lgorithm runs in time $poly(n,s,d,p)$.Sat, 29 Apr 2017 15:21:37 +0300https://eccc.weizmann.ac.il/report/2017/074TR17-073 | New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems |
Eric Allender,
Shuichi Hirahara
https://eccc.weizmann.ac.il/report/2017/073The Minimum Circuit Size Problem (MCSP) and a related problem (MKTP) that deals with time-bounded Kolmogorov complexity are prominent candidates for NP-intermediate status. We show that, under very modest cryptographic assumptions (such as the existence of one-way functions), the problem of approximating the minimum circuit size (or time-bounded Kolmogorov complexity) within a factor of $n^{1 - o(1)}$ is indeed NP-intermediate. To the best of our knowledge, these problems are the first natural NP-intermediate problems under the existence of an arbitrary one-way function.
We also prove that MKTP is hard for the complexity class DET under non-uniform NC$^0$ reductions. This is surprising, since prior work on MCSP and MKTP had highlighted weaknesses of "local" reductions (such as NC$^0$ reductions).
We exploit this local reduction to obtain several new consequences:
* MKTP is not in AC$^0[p]$.
* Circuit size lower bounds are equivalent to hardness of a relativized version MKTP$^A$ of MKTP under a class of uniform AC$^0$ reductions, for a large class of sets A.
* Hardness of MCSP$^A$ implies hardness of MKTP$^A$ for a wide class of sets A. This is the first result directly relating the complexity of MCSP$^A$ and MKTP$^A$, for any A.Fri, 28 Apr 2017 04:49:40 +0300https://eccc.weizmann.ac.il/report/2017/073TR17-072 | Better Complexity Bounds for Cost Register Machines |
Eric Allender,
Pierre McKenzie,
Andreas Krebs
https://eccc.weizmann.ac.il/report/2017/072Cost register automata (CRA) are one-way finite automata whose transitions have the side effect that a register is set to the result of applying a state-dependent semiring operation to a pair of registers. Here it is shown that CRAs over the semiring (N,min,+) can simulate polynomial time computation, proving along the way that a naturally defined width-k circuit value problem over the tropical semiring is P-complete. Then the copyless variant of the CRA, requiring that semiring operations be applied to distinct registers, is shown no more powerful than NC1 when the semiring is (Z,+,×) or (?*,max,?). This relates questions left open in recent work on the complexity of CRA-computable functions to long-standing class separation conjectures in complexity theory, such as NC versus P and NC1 versus GapNC1.Tue, 25 Apr 2017 17:07:16 +0300https://eccc.weizmann.ac.il/report/2017/072TR17-071 | Bounds for the Communication Complexity of Two-Player Approximate Correlated Equilibria |
Young Kun Ko,
Arial Schvartzman
https://eccc.weizmann.ac.il/report/2017/071In the recent paper of~\cite{BR16}, the authors show that, for any constant $10^{-15} > \varepsilon > 0$ the communication complexity of $\varepsilon$-approximate Nash equilibria in $2$-player $n \times n$ games is $n^{\Omega(\varepsilon)}$, resolving the long open problem of whether or not there exists a polylogarithmic communication protocol. In this paper we address an open question they pose regarding the communication complexity of $2$-player $\varepsilon$-approximate correlated equilibria.
For our upper bounds, we provide a communication protocol that outputs a $\varepsilon$-approximate correlated equilibrium after exchanging $\tilde{O}(n \varepsilon^{-2})$ bits, saving over the naive protocol which requires $O(n^2)$-bits. This is in sharp contrast to Nash equilibria where for sufficiently small constant $\varepsilon$, no $o(n^2)$-communication protocol is known. In the $m$-player, $n$-action setting, our protocol can be extended to a $\tilde{O}(nm)$-bit protocol.
For our lower bounds, we exhibit a simple two player game that has a logarithmic information lower bound: for any constant $\varepsilon < \frac{1}{8}$ the two players need to communicate $\Omega(\log n)$-bits of information to compute any $\varepsilon$-correlated equilibrium in the game. For the $m$-players, $2$-action setting we show a lower bound of $\Omega(m)$ bits, which matches the upper bound we provide up to polylogarithmic terms and shows that the dependence on the number of players is unavoidable.Sun, 23 Apr 2017 19:09:59 +0300https://eccc.weizmann.ac.il/report/2017/071TR17-070 | Probabilistic Existence of Large Sets of Designs |
Shachar Lovett,
Sankeerth Rao,
Alex Vardy
https://eccc.weizmann.ac.il/report/2017/070A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been introduced by Kuperberg, Lovett, and Peled (STOC 2012). Using this technique, it can be shown that under certain conditions, a randomly chosen structure has the required properties of a $t-(n,k,?)$ combinatorial design with tiny, yet positive, probability.
Herein, we strengthen both the method and the result of Kuperberg, Lovett, and Peled as follows.
We modify the random choice and the analysis to show that, under the same conditions, not only does a $t- (n,k,?)$ design exist but, in fact, with positive probability there exists a large set of such designs —that is, a partition of the set of $k$-subsets of $[n]$ into $t-(n,k,?)$ designs. Specifically, using the probabilistic approach derived herein, we prove that for all sufficiently large $n$, large sets of $t-(n,k,?)$ designs exist whenever $k > 9t$ and the necessary divisibility conditions are satisied. This resolves the existence conjecture for large sets of designs for all $k > 9t$.Sun, 23 Apr 2017 10:01:19 +0300https://eccc.weizmann.ac.il/report/2017/070