ECCC - Reportshttps://eccc.weizmann.ac.il/Latest Reports published at https://eccc.weizmann.ac.ilen-usSun, 22 Jan 2023 10:29:45 +0200TR23-006 | Superpolynomial Lower Bounds for Learning Monotone Classes |
Nader Bshouty
https://eccc.weizmann.ac.il/report/2023/006Koch, Strassle, and Tan [SODA 2023], show that, under the randomized exponential time hypothesis, there is no distribution-free PAC-learning algorithm that runs in time $n^{\tilde O(\log\log s)}$ for the classes of $n$-variable size-$s$ DNF, size-$s$ Decision Tree, and $\log s$-Junta by DNF (that returns a DNF hypothesis). Assuming a natural conjecture on the hardness of set cover, they give the lower bound $n^{\Omega(\log s)}$. This matches the best known upper bound for $n$-variable size-$s$ Decision Tree, and $\log s$-Junta.
In this paper, we give the same lower bounds for PAC-learning of $n$-variable size-$s$ Monotone DNF, size-$s$ Monotone Decision Tree, and Monotone $\log s$-Junta by~DNF. This solves the open problem proposed by Koch, Strassle, and Tan and subsumes the above results.
The lower bound holds, even if the learner knows the distribution, can draw a sample according to the distribution in polynomial time, and can compute the target function on all the points of the support of the distribution in polynomial time.Sun, 22 Jan 2023 10:29:45 +0200https://eccc.weizmann.ac.il/report/2023/006TR23-005 | Cumulative Memory Lower Bounds for Randomized and Quantum Computation |
Paul Beame,
Niels Kornerup
https://eccc.weizmann.ac.il/report/2023/005Cumulative memory---the sum of space used over the steps of a computation---is a fine-grained measure of time-space complexity that is a more accurate measure of cost for algorithms with infrequent spikes in memory usage in the context of technologies such as cloud computing that allow dynamic allocation and de-allocation of resources during their execution. We give the first lower bounds on cumulative memory complexity that apply to general sequential classical algorithms. We also prove the first such bounds for bounded-error quantum circuits. Among many possible applications, we show that any classical sorting algorithm with success probability at least $1/\text{poly}(n)$ requires cumulative memory $\tilde \Omega(n^2)$, any classical matrix multiplication algorithm requires cumulative memory $\Omega(n^6/T)$, any quantum sorting circuit requires cumulative memory $\Omega(n^3/T)$, and any quantum circuit that finds $k$ disjoint collisions in a random function requires cumulative memory $\Omega(k^3n/T^2)$. More generally, we present theorems that can be used to convert a wide class of existing time-space tradeoff lower bounds to matching lower bounds on cumulative memory complexity.Fri, 13 Jan 2023 09:30:49 +0200https://eccc.weizmann.ac.il/report/2023/005TR23-004 | On linear-algebraic notions of expansion |
Yinan Li,
Youming Qiao,
Avi Wigderson,
Yuval Wigderson,
Chuanqi Zhang
https://eccc.weizmann.ac.il/report/2023/004A fundamental fact about bounded-degree graph expanders is that three notions of expansion---vertex expansion, edge expansion, and spectral expansion---are all equivalent. In this paper, we study to what extent such a statement is true for linear-algebraic notions of expansion.
There are two well-studied notions of linear-algebraic expansion, namely dimension expansion (defined in analogy to graph vertex expansion) and quantum expansion (defined in analogy to graph spectral expansion). Lubotzky and Zelmanov proved that the latter implies the former. We prove that the converse is false: there are dimension expanders which are not quantum expanders.
Moreover, this asymmetry is explained by the fact that there are two distinct linear-algebraic analogues of graph edge expansion. The first of these is quantum edge expansion, which was introduced by Hastings, and which he proved to be equivalent to quantum expansion. We introduce a new notion, termed dimension edge expansion, which we prove is equivalent to dimension expansion and which is implied by quantum edge expansion. Thus, the separation above is implied by a finer one: dimension edge expansion is strictly weaker than quantum edge expansion. This new notion also leads to a new, more modular proof of the Lubotzky--Zelmanov result that quantum expanders are dimension expanders.Fri, 13 Jan 2023 09:27:38 +0200https://eccc.weizmann.ac.il/report/2023/004TR23-003 | Streaming Lower Bounds and Asymmetric Set-Disjointness |
Jiapeng Zhang,
Shachar Lovett
https://eccc.weizmann.ac.il/report/2023/003Frequency estimation in data streams is one of the classical problems in streaming algorithms. Following much research, there are now almost matching upper and lower bounds for the trade-off needed between the number of samples and the space complexity of the algorithm, when the data streams are adversarial. However, in the case where the data stream is given in a random order, or is stochastic, only weaker lower bounds exist. In this work we close this gap, up to logarithmic factors.
In order to do so we consider the needle problem, which is a natural hard problem for frequency estimation studied in (Andoni et al. 2008, Crouch et al. 2016). Here, the goal is to distinguish between two distributions over data streams with $t$ samples. The first is uniform over a large enough domain. The second is a planted model; a secret ''needle'' is uniformly chosen, and then each element in the stream equals the needle with probability $p$, and otherwise is uniformly chosen from the domain. It is simple to design streaming algorithms that distinguish the distributions using space $s \approx 1/(p^2 t)$. It was unclear if this is tight, as the existing lower bounds are weaker. We close this gap and show that the trade-off is near optimal, up to a logarithmic factor.
Our proof builds and extends classical connections between streaming algorithms and communication complexity, concretely multi-party unique set-disjointness. We introduce two new ingredients that allow us to prove sharp bounds. The first is a lower bound for an asymmetric version of multi-party unique set-disjointness, where players receive input sets of different sizes, and where the communication of each player is normalized relative to their input length. The second is a combinatorial technique that allows to sample needles in the planted model by first sampling intervals, and then sampling a uniform needle in each interval. Fri, 13 Jan 2023 09:25:30 +0200https://eccc.weizmann.ac.il/report/2023/003TR23-002 | Diagonalization Games |
Noga Alon,
Olivier Bousquet,
Kasper Green Larsen,
Shay Moran,
Shlomo Moran
https://eccc.weizmann.ac.il/report/2023/002We study several variants of a combinatorial game which is based on Cantor's diagonal argument. The game is between two players called Kronecker and Cantor. The names of the players are motivated by the known fact that Leopold Kronecker did not appreciate Georg Cantor's arguments about the infinite, and even referred to him as a ``scientific charlatan''.
In the game Kronecker maintains a list of m binary vectors,
each of length n, and Cantor's goal is to produce a new binary vector which is different from each of Kronecker's vectors, or prove that no such vector exists. Cantor does not see Kronecker's vectors but he is allowed to ask queries of the form ``What is bit number j of vector number i? What is the minimal number of queries with which Cantor can achieve his goal? How much better can Cantor do if he is allowed to pick his queries \emph{adaptively}, based on Kronecker's previous replies?
The case when m=n is solved by diagonalization using n (non-adaptive) queries. We study this game more generally, and prove an optimal bound in the adaptive case and nearly tight upper and lower bounds in the non-adaptive case.
Sun, 08 Jan 2023 04:36:41 +0200https://eccc.weizmann.ac.il/report/2023/002TR23-001 | New Lower Bounds against Homogeneous Non-Commutative Circuits |
Prerona Chatterjee,
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2023/001We give several new lower bounds on size of homogeneous non-commutative circuits. We present an explicit homogeneous bivariate polynomial of degree $d$ which requires homogeneous non-commutative circuit of size $\Omega(d/\log d)$. For an $n$-variate polynomial with $n>1$, the result can be improved to $\Omega(nd)$, if $d\leq n$, or $\Omega(nd \frac{\log n}{\log d})$, if $d\geq n$.
Under the same assumptions, we also give a quadratic lower bound for the ordered version of the central symmetric polynomial. Thu, 05 Jan 2023 14:43:37 +0200https://eccc.weizmann.ac.il/report/2023/001TR22-186 | Power of Decision Trees with Monotone Queries |
Prashanth Amireddy,
Sai Jayasurya,
Jayalal Sarma
https://eccc.weizmann.ac.il/report/2022/186In this paper, we initiate study of the computational power of adaptive and non-adaptive monotone decision trees – decision trees where each query is a monotone function on the input bits. In the most general setting, the monotone decision tree height (or size) can be viewed as a measure of non-monotonicity of a given Boolean function. We also study the restriction of the model by restricting (in terms of circuit complexity) the monotone functions that can be queried at each node. This naturally leads to complexity classes of the form $DT(mon-\mathcal{C})$ for any circuit complexity class $\mathcal{C}$, where the height of the tree is $O(\log n)$, and the query functions can be computed by monotone circuits in the class $\mathcal{C}$. In the above context, we prove the following characterizations and bounds.
$\bullet$ For any Boolean function $f$, we show that the minimum monotone decision tree height can be exactly characterized (both in the adaptive and non-adaptive versions of the model) in terms of its alternation ($alt(f)$ is defined as the maximum number of times that the function value changes, in any chain in the Boolean lattice). We also characterize the non-adaptive decision tree height with a natural generalization of certification complexity of a function. Similarly, we determine the complexity of non-deterministic and randomized variants of monotone decision trees in terms of $alt(f)$.
$\bullet$ We show that $DT(mon-\mathcal{C}) = \mathcal{C}$ if $\mathcal{C}$ contains monotone circuits for the threshold functions. For $\mathcal{C} = AC_0$, we are able to show that any function in $AC_0$ can be computed by a sub-linear height monotone decision tree with queries having monotone $AC_0$ circuits.
$\bullet$ To understand the logarithmic height case in case of $AC_0$ i.e., $DT(mon-AC_0)$, we show that for any $f$ (on $n$ bits) in $DT(mon-AC_0)$, and for any positive constant $\epsilon \le 1$, there is an $AC_0$ circuit for $f$ with $O(n^\epsilon)$ negation gates.
En route our main proofs, we study the monotone variant of the decision list model, and prove corresponding characterizations in terms of $alt(f)$ and also derive as a consequence that $DT(mon-\mathcal{C}) = DL(mon-\mathcal{C})$ if $\mathcal{C}$ has appropriate closure properties (where $DL(mon-\mathcal{C})$ is defined similar to $DT(mon-\mathcal{C})$ but for decision lists).Sat, 31 Dec 2022 23:08:57 +0200https://eccc.weizmann.ac.il/report/2022/186TR22-185 | Randomized versus Deterministic Decision Tree Size |
Yogesh Dahiya,
Arkadev Chattopadhyay,
Nikhil Mande,
Jaikumar Radhakrishnan,
Swagato Sanyal
https://eccc.weizmann.ac.il/report/2022/185A classic result of Nisan [SICOMP '91] states that the deterministic decision tree depth complexity of every total Boolean function is at most the cube of its randomized decision tree depth complexity. The question whether randomness helps in significantly reducing the size of decision trees appears not to have been addressed. We show that the logarithm of the deterministic decision tree size complexity of every total Boolean function on $n$ input variables is at most the fourth power of the logarithm of its bounded-error randomized decision tree size complexity, ignoring a polylogarithmic factor in the input size. Our result has the following consequences:
1. The deterministic AND-OR query complexity of a total Boolean function is at most the fourth power of its randomize AND-OR query complexity, ignoring a $(\log n)^{O(1)}$ factor.
2. The deterministic AND (OR) query complexity of a total Boolean function is at most the cube of its randomized AND (OR) query complexity, ignoring a $(\log n)^{O(1)}$ factor. This answers a recent open question posed by Knop, Lovett, McGuire and Yuan [SIGACT News '21].
3. The notion of rank of a Boolean function was defined in a classic work of Ehrenfeucht and Haussler [Information and Computation'89] in the context of learning theory, and is characterized by the logarithm of decision tree size up to a logarithmic factor in the input size. Our results confirm a recent conjecture (ignoring a $(\log n)^{O(1)}$ factor) of Cornelissen, Mande and Patro [FSTTCS '22], that asserted the equivalence of randomized and deterministic analogs of rank, upto polynomial factors, for all total Boolean functions.
4. Combined with the above-mentioned work of Ehrenfeucht and Haussler, our result implies that the class of functions computable by randomized decision trees of polynomial size, is PAC-learnable in quasi-polynomial time.
To obtain our main result on decision tree size, we introduce the notion of block number of a Boolean function, which can be thought of as a counting analog of block sensitivity of a Boolean function that played a central role in Nisan's result mentioned above.
Thu, 29 Dec 2022 20:58:04 +0200https://eccc.weizmann.ac.il/report/2022/185TR22-184 | Testing in the bounded-degree graph model with degree bound two |
Oded Goldreich,
Laliv Tauber
https://eccc.weizmann.ac.il/report/2022/184Considering the bounded-degree graph model, we show that if the degree bound is two,
then every graph property can be tested within query complexity that only depends on the proximity parameter.
Specifically, the query complexity is ${\rm poly}(1/\epsilon)$, where $\epsilon$ denotes the proximity parameter.
The key observation is that a graph of maximum degree two consists of a collection of paths and cycles,
and that a collection of long paths and cycles is relatively close (in this model) to a single cycle. Wed, 28 Dec 2022 16:24:08 +0200https://eccc.weizmann.ac.il/report/2022/184TR22-183 | New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method |
Lijie Chen
https://eccc.weizmann.ac.il/report/2022/183In this paper, we obtain several new results on lower bounds and derandomization for ACC^0 circuits (constant-depth circuits consisting of AND/OR/MOD_m gates for a fixed constant m, a frontier class in circuit complexity):
1. We prove that any polynomial-time Merlin-Arthur proof system with an ACC^0 verifier (denoted by MA_{ACC^0}) can be simulated by a nondeterministic proof system with quasi-polynomial running time and polynomial proof length on infinitely many input lengths. This improves the previous simulation by [Chen, Lyu, and Williams, FOCS 2020], which requires both quasi-polynomial running time and proof length.
2. We show that MA_{ACC^0} cannot be computed by fixed-polynomial-size ACC^0 circuits, and our hard languages are hard on a sufficiently dense set of input lengths.
3. We show that NEXP (nondeterministic exponential-time) does not have ACC^0 circuits of sub-half-exponential size, improving the previous sub-third-exponential size lower bound for NEXP against ACC^0 by [Williams, J. ACM 2014].
Combining our first and second results gives a conceptually simpler and derandomization-centric proof of the recent breakthrough result NQP = \NTIME[2^{polylog(n)}] is not in ACC^0 by [Murray and Williams, SICOMP 2020]: Instead of going through an easy witness lemma as they did, we first prove an ACC^0 lower bound for a subclass of MA, and then derandomize that subclass into NQP, while retaining its hardness against ACC^0.
Moreover, since our derandomization of MA_{ACC^0} achieves a polynomial proof length, we indeed prove that nondeterministic quasi-polynomial-time with n^{omega(1)} nondeterminism bits (denoted as NTIMEGUESS[2^{polylog(n)},n^{omega(1)}]) has no poly(n)-size ACC^0 circuits, giving a new proof of a result by Vyas. Combining with a win-win argument based on randomized encodings from [Chen and Ren, STOC 2020], we also prove that NTIMEGUESS[2^{polylog(n)},n^{omega(1)}] cannot be (1/2+1/poly(n))-approximated by poly(n)-size ACC^0 circuits, improving the recent strongly average-case lower bounds for NQP against ACC^0 by [Chen and Ren, STOC 2020].
One interesting technical ingredient behind our second result is the construction of a PSPACE-complete language that is paddable, downward self-reducible, same-length checkable, and weakly error correctable. Moreover, all its reducibility properties have corresponding AC^0[2] non-adaptive oracle circuits. Our construction builds and improves upon similar constructions from [Trevisan and Vadhan, Complexity 2007] and [Chen, FOCS 2019], which all require at least TC^0 oracle circuits for implementing these properties.Mon, 19 Dec 2022 23:47:54 +0200https://eccc.weizmann.ac.il/report/2022/183