Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

The purpose of this article is to initiate a systematic study of dimensionfree relations between basic communication and query complexity measures and various matrix norms. In other words, our goal is to obtain inequalities that bound a parameter solely as a function of another parameter. This is in contrast to perhaps the more common framework in communication complexity where polylogarithmic dependencies on the number of input bits are tolerated. Dimensionfree bounds are also closely related to structural results, where one seeks to describe the structure of Boolean matrices and functions that have low complexity. We prove such theorems for several communication and query complexity measures as well as various matrix and operator norms. In several other cases we show that such bounds do not exist. We propose several conjectures, and establish that, in addition to applications in complexity theory, these problems are central to characterization of the idempotents of the algebra of Schur multipliers, and could lead to new extensions of Cohen’s celebrated idempotent theorem regarding the Fourier algebra.more » « less

An efficient implicit representation of an nvertex graph G in a family F of graphs assigns to each vertex of G a binary code of length O(log n) so that the adjacency between every pair of vertices can be determined only as a function of their codes. This function can depend on the family but not on the individual graph. Every family of graphs admitting such a representation contains at most 2^O(n log(n)) graphs on n vertices, and thus has at most factorial speed of growth. The Implicit Graph Conjecture states that, conversely, every hereditary graph family with at most factorial speed of growth admits an efficient implicit representation. We refute this conjecture by establishing the existence of hereditary graph families with factorial speed of growth that require codes of length n^Ω(1).more » « less

Etessami, Kousha ; Feige, Uriel ; Puppis, Gabriele (Ed.)In a recent article, Alon, Hanneke, Holzman, and Moran (FOCS '21) introduced a unifying framework to study the learnability of classes of partial concepts. One of the central questions studied in their work is whether the learnability of a partial concept class is always inherited from the learnability of some "extension" of it to a total concept class. They showed this is not the case for PAC learning but left the problem open for the stronger notion of online learnability. We resolve this problem by constructing a class of partial concepts that is online learnable, but no extension of it to a class of total concepts is online learnable (or even PAC learnable).more » « less

We present new constructions of pseudorandom generators (PRGs) for two of the most widely studied nonuniform circuit classes in complexity theory. Our main result is a construction of the first nontrivial PRG for linear threshold (LTF) circuits of arbitrary constant depth and superlinear size. This PRG fools circuits with depth d∈N and n1+δ wires, where δ=2−O(d) , using seed length O(n1−δ) and with error 2−nδ . 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 circuitanalysis 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 s1/3+o(1)⋅polylog(1/ϵ) for error ϵ . In particular, our PRG can fool formulas of subcubic size s=n3−Ω(1) with an exponentially small error ϵ=exp(−nΩ(1)) . This significantly improves the inversepolynomial error of the previous stateoftheart for such formulas by Impagliazzo, Meka, and Zuckerman (FOCS 2012, JACM 2019), and again tightly matches the best currentlyknown 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 nonnatural “hybrid computational model” that combines several computational models.more » « less

Saraf, Shubhangi (Ed.)There are only a few known general approaches for constructing explicit pseudorandom generators (PRGs). The "iterated restrictions" approach, pioneered by Ajtai and Wigderson [Ajtai and Wigderson, 1989], has provided PRGs with seed length polylog n or even Õ(log n) for several restricted models of computation. Can this approach ever achieve the optimal seed length of O(log n)? In this work, we answer this question in the affirmative. Using the iterated restrictions approach, we construct an explicit PRG for readonce depth2 AC⁰[⊕] formulas with seed length O(log n) + Õ(log(1/ε)). In particular, we achieve optimal seed length O(log n) with nearoptimal error ε = exp(Ω̃(log n)). Even for constant error, the best prior PRG for this model (which includes readonce CNFs and readonce 𝔽₂polynomials) has seed length Θ(log n ⋅ (log log n)²) [Chin Ho Lee, 2019]. A key step in the analysis of our PRG is a tail bound for subsetwise symmetric polynomials, a generalization of elementary symmetric polynomials. Like elementary symmetric polynomials, subsetwise symmetric polynomials provide a way to organize the expansion of ∏_{i=1}^m (1 + y_i). Elementary symmetric polynomials simply organize the terms by degree, i.e., they keep track of the number of variables participating in each monomial. Subsetwise symmetric polynomials keep track of more data: for a fixed partition of [m], they keep track of the number of variables from each subset participating in each monomial. Our tail bound extends prior work by Gopalan and Yehudayoff [Gopalan and Yehudayoff, 2014] on elementary symmetric polynomials.more » « less

Byrka, Jaroslaw ; Meka, Raghu (Ed.)In this work, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over F₂. We show the following results for multilinear forms and tensors. Correlation bounds. We show that a random dlinear form has exponentially low correlation with lowdegree polynomials. More precisely, for d = 2^{o(k)}, we show that a random dlinear form f(X₁,X₂, … , X_d) : (F₂^{k}) ^d → F₂ has correlation 2^{k(1o(1))} with any polynomial of degree at most d/2 with high probability. This result is proved by giving nearoptimal bounds on the bias of a random dlinear form, which is in turn proved by giving nearoptimal bounds on the probability that a sum of t random ddimensional rank1 tensors is identically zero. Tensor rank vs Bias. We show that if a 3dimensional tensor has small rank then its bias, when viewed as a 3linear form, is large. More precisely, given any 3dimensional tensor T: [k]³ → F₂ of rank at most t, the bias of the 3linear form f_T(X₁, X₂, X₃) : = ∑_{(i₁, i₂, i₃) ∈ [k]³} T(i₁, i₂, i₃)⋅ X_{1,i₁}⋅ X_{2,i₂}⋅ X_{3,i₃} is at least (3/4)^t. This bias vs tensorrank connection suggests a natural approach to proving nontrivial tensorrank lower bounds. In particular, we use this approach to give a new proof that the finite field multiplication tensor has tensor rank at least 3.52 k, which is the best known rank lower bound for any explicit tensor in three dimensions over F₂. Moreover, this relation between bias and tensor rank holds for ddimensional tensors for any fixed d.more » « less