ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usTue, 14 Sep 2021 19:42:45 +0300TR21-137 | Affine extractors and AC0-Parity |
Xuangui Huang,
Peter Ivanov,
Emanuele Viola
https://eccc.weizmann.ac.il/report/2021/137We study a simple and general template for constructing affine extractors by composing a linear transformation with resilient functions. Using this we show that good affine extractors can be computed by non-explicit circuits of various types, including AC0-Xor circuits: AC0 circuits with a layer of parity gates at the input. We also show that one-sided extractor can be computed by small DNF-Xor circuits, and separate these circuits from other well-studied classes. As a further motivation for studying DNF-Xor circuits we show that if they can approximate inner product then small AC0-Xor circuits can compute it exactly – a long-standing open problem.Tue, 14 Sep 2021 19:42:45 +0300https://eccc.weizmann.ac.il/report/2021/137TR21-136 | LCC and LDC: Tailor-made distance amplification and a refined separation |
Gil Cohen,
Tal Yankovitz
https://eccc.weizmann.ac.il/report/2021/136The Alon-Edmonds-Luby distance amplification procedure (FOCS 1995) is an algorithm that transforms a code with vanishing distance to a code with constant distance. AEL was invoked by Kopparty, Meir, Ron-Zewi, and Saraf (J. ACM 2017) for obtaining their state-of-the-art LDC, LCC and LTC. Cohen and Yankovitz (CCC 2021) devised a procedure that can amplify inverse-polynomial distances, exponentially extending the regime of distances that can be amplified by AEL. However, the improved procedure only works for LDC and assuming rate $1-\frac1{\mathrm{poly} \log n}$.
In this work we devise a distance amplification procedure for LCC with inverse-polynomial distances even for vanishing rate $\frac1{\mathrm{poly} \log\log n}$. For LDC, we obtain a more modest improvement and require rate $1-\frac1{\mathrm{poly} \log\log n}$. Thus, the tables have turned and it is now LCC that can be better amplified. Our key idea for accomplishing this, deviating from prior work, is to tailor the distance amplification procedure to the code at hand.
Our second result concerns the relation between linear LDC and LCC. We prove the existence of linear LDC that are not LCC, qualitatively extending a separation by Kaufman and Viderman (RANDOM 2010).
Mon, 13 Sep 2021 17:58:00 +0300https://eccc.weizmann.ac.il/report/2021/136TR21-135 | Strong (D)QBF Dependency Schemes via Implication-free Resolution Paths |
Tomáš Peitl,
Olaf Beyersdorff,
Joshua Blinkhorn
https://eccc.weizmann.ac.il/report/2021/135We suggest a general framework to study dependency schemes for dependency quantified Boolean formulas (DQBF). As our main contribution, we exhibit a new infinite collection of implication-free DQBF dependency schemes that generalise the reflexive resolution path dependency scheme. We establish soundness of all these schemes, implying that they can be used in any DQBF proof system. We further explore the power of QBF and DQBF resolution systems parameterised by implication-free dependency schemes and show that the hierarchical structure naturally present among the dependency schemes translates isomorphically to a hierarchical structure of parameterised proof systems with respect to p-simulation. As a special case, we demonstrate that our new schemes are exponentially stronger than the reflexive resolution path dependency scheme when used in Q-resolution, thus resulting in the strongest QBF dependency schemes known to date.Mon, 13 Sep 2021 13:56:05 +0300https://eccc.weizmann.ac.il/report/2021/135TR21-134 | A refinement of the Meyer-McCreight Union Theorem |
Siddharth Bhaskar
https://eccc.weizmann.ac.il/report/2021/134For a function $t : 2^\star \to 1^\star$, let $C_t$ be the set of problems decidable on input $x$ in time at most $t(x)$ almost everywhere. The Union Theorem of Meyer and McCreight asserts that any union $\bigcup_{i < \omega} C_{t_i}$ for a uniformly recursive sequence of bounds $t_i$ is equal to $C_L$ for some single recursive function $L$. In particular the class PTIME of polynomial-time relations can be expressed as $C_L$ for some total recursive function $L : 2^\star \to 1^\star$. By controlling the complexity of the construction, we show that in fact PTIME equals $C_L$ for some $L$ computable in quasi-polynomial time.Sun, 12 Sep 2021 15:21:11 +0300https://eccc.weizmann.ac.il/report/2021/134TR21-133 | Testing Distributions of Huge Objects |
Oded Goldreich,
Dana Ron
https://eccc.weizmann.ac.il/report/2021/133We initiate a study of a new model of property testing that is a hybrid of testing properties of distributions and testing properties of strings.
Specifically, the new model refers to testing properties of distributions, but these are distributions over huge objects (i.e., very long strings).
Accordingly, the model accounts for the total number of local probes into these objects (resp., queries to the strings)as well as for the distance between objects (resp., strings).
Specifically, the distance between distributions is defined as the earth mover's distance with respect to the relative Hamming distance between strings.
We study the query complexity of testing in this new model, focusing on three directions.
First, we try to relate the query complexity of testing properties in the new model to the sample complexity of testing these properties in the standard distribution testing model.
Second, we consider the complexity of testing properties that arise naturally in the new model (e.g., distributions that capture random variations of fixed strings).
Third, we consider the complexity of testing properties that were extensively studied in the standard distribution testing model: Two such cases are uniform distributions
and pairs of identical distributions, where we obtain the following results.
\begin{itemize}
\item
Testing whether a distribution over $n$-bit long strings is uniform on some set of size $m$ can be tested with query complexity ${\widetilde O}(m/\epsilon^3)$, where $\epsilon>(\log_2m)/n$ is the proximity parameter.
\item
Testing whether two distribution over $n$-bit long strings that have support size at most $m$ are identical can be tested with query complexity ${\widetilde O}(m^{2/3}/\epsilon^3)$.
\end{itemize}
Both upper bounds are pretty tight; that is, for $\epsilon=\Omega(1)$, the first task requires $\Omega(m^c)$ queries for any $c<1$ and $n=\omega(\log m)$, whereas the second task requires $\Omega(m^{2/3})$ queries.
Note that the query complexity of the first task is higher than the sample complexity of the corresponding task in the standard distribution testing model, whereas in the case of the second task the bounds almost match.Sun, 12 Sep 2021 14:24:05 +0300https://eccc.weizmann.ac.il/report/2021/133TR21-132 | Pseudo-random functions and uniform learnability |
Eric Binnendyk
https://eccc.weizmann.ac.il/report/2021/132Boolean circuits are a model of computation. A class of Boolean circuits is called a polynomial class if the number of nodes is bounded by a polynomial function of the number of input variables. A class $C_n[s(n)]$ of Boolean functions is called learnable if there are algorithms that can approximate functions in $C_n[s(n)]$ when given oracle access to the function. A distribution $D$ of functions is called pseudorandom against a circuit class $C[t(n)]$ if any oracle circuit $C^f$ from $C[t(n)]$ outputs 1 with the same probability if the oracle $f$ is chosen from $D$ as it would if the oracle were random. It is known that a polynomial class of circuits is learnable if and only if it contains no pseudorandom distributions of functions. However, there is no known algorithm to produce the learner given the number of inputs the circuits have (the learner is non-uniform). I investigate a uniform version of the min-max theorem as a possible tool to find an algorithm for such learners.
Sun, 12 Sep 2021 10:27:36 +0300https://eccc.weizmann.ac.il/report/2021/132TR21-131 | QCDCL with Cube Learning or Pure Literal Elimination - What is best? |
Benjamin Böhm,
Olaf Beyersdorff
https://eccc.weizmann.ac.il/report/2021/131Quantified conflict-driven clause learning (QCDCL) is one of the main approaches for solving quantified Boolean formulas (QBF). We formalise and investigate several versions of QCDCL that include cube learning and/or pure-literal elimination, and formally compare the resulting solving models via proof complexity techniques. Our results show that almost all of the QCDCL models are exponentially incomparable with respect to proof size (and hence solver running time), pointing towards different orthogonal ways how to practically implement QCDCL.Fri, 10 Sep 2021 20:29:36 +0300https://eccc.weizmann.ac.il/report/2021/131TR21-130 | Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case |
Srinivasan Arunachalam,
João F. Doriguello
https://eccc.weizmann.ac.il/report/2021/130Hypercontractive inequalities for real-valued functions over the Boolean cube play an important role in theoretical computer science. In this work, we prove a hypercontractive inequality for matrix-valued functions defined over large alphabets, generalizing the result of Ben-Aroya, Regev, de Wolf (FOCS'08) for the Boolean alphabet. To obtain our result we prove a generalization of the powerful $2$-uniform convexity inequality for trace norms of Ball, Carlen, Lieb (Inventiones Mathematicae'94). We give two applications of this hypercontractive inequality.
Locally decodable codes: we present a lower bound for locally decodable codes (LDC) over large alphabets. An LDC $C:\mathbb{Z}_r^n\to \mathbb{Z}_r^N$ is an encoding of $x\in \mathbb{Z}_r^n$ into a codeword $C(x)$ in such a way that one can recover an arbitrary $x_i\in \mathbb{Z}_r$ (with probability at least $1/r+\varepsilon$) by making only a few queries to a corrupted codeword. The main question in LDCs is the trade-off between $N$ and $n$. By using hypercontractivity, we give an exponential lower bound $N= 2^{\Omega(\varepsilon^4 n/r^4)}$ for $2$-query (possibly non-linear) LDCs over $\mathbb{Z}_r$. Previously exponential lower bounds were known for $r=2$ (Kerenidis and de Wolf (JCSS'04)) and for \emph{linear} codes (Dvir and Shpilka (SICOMP'07)).
Streaming algorithms: we present upper and lower bounds for the communication complexity of the Hidden Hypermatching problem when defined over large alphabets, which generalizes the well-known Boolean Hidden Matching problem. We then consider streaming algorithms for approximating the value of Unique Games on a $t$-hyperedge hypergraph: in this direction a simple edge-counting argument gives an $r$-approximation with $O(\log n)$ space. On the other hand, we use our communication lower bound to show that every streaming algorithm in the adversarial model achieving a $(r-\varepsilon)$-approximation of this value requires $\Omega(n^{1-1/t})$ classical space or $\Omega(n^{1-2/t})$ quantum space. In this setting, these results simplify and generalize the seminal work of Kapralov, Khanna and Sudan (SODA'15) and Kapravol and Krachun (STOC'19) for the case $r=2$.Thu, 09 Sep 2021 17:48:45 +0300https://eccc.weizmann.ac.il/report/2021/130TR21-129 | A Lower Bound on the Complexity of Testing Grained Distributions |
Oded Goldreich,
Dana Ron
https://eccc.weizmann.ac.il/report/2021/129A distribution is called $m$-grained if each element appears with probability that is an integer multiple of $1/m$.
We prove that, for any constant $c<1$, testing whether a distribution over $[\Theta(m)]$ is $m$-grained requires $\Omega(m^c)$ samples.
Mon, 06 Sep 2021 15:24:30 +0300https://eccc.weizmann.ac.il/report/2021/129TR21-128 | On the Complexity of Computing Markov Perfect Equilibrium in General-Sum Stochastic Games |
Xiaotie Deng,
Yuhao Li,
David Mguni,
Jun Wang,
Yaodong Yang
https://eccc.weizmann.ac.il/report/2021/128Similar to the role of Markov decision processes in reinforcement learning, Markov Games (also called Stochastic Games)lay down the foundation for the study of multi-agent reinforcement learning (MARL) and sequential agent interactions. In this paper, we introduce the solution concept, approximate Markov Perfect Equilibrium (MPE), to finite-state Stochastic Games repeated in the infinite horizon, and prove its $\mathbf{PPAD}$-completeness in computational complexity. Technically, we adopt a function with a polynomially bounded description in the strategy space to convert the MPE computation to a fixed-point problem, even though the stochastic game may demand an exponential number of pure strategies, in the number of states, for each agent. The completeness result follows the reduction of the fixed-point problem to \textsc{End of the Line}.
Past works on the stochastic games are mostly zero-sum MARL algorithms. A $P^{PPAD}$ algorithm for the general sum stochastic games in the finite horizon can be derived to establish an approximation algorithm for the general-sum stochastic games. That implies an approximate NE solution to the infinite-horizon setting. Such a possible extension suffers from three weaknesses: 1. the solution is time-dependent and hence not a perfect equilibrium; 2. the time-dependent solution suffers a weakness of noncredible threats; 3. the time complexity is not tight (lower bound $\mathbf{PPAD}$ and upper bound $P^{PPAD}$). Our result beats such a solution in all those three properties.
Sat, 04 Sep 2021 09:57:01 +0300https://eccc.weizmann.ac.il/report/2021/128