It is a long-standing open problem in algebraic complexity to prove lower bounds against multilinear algebraic branching programs (mlABPs), however the best lower bounds are still quadratic (Alon, Kumar and Volk (Combinatorica 2020)). At the same time, it remains a possibility that the "min-partition rank" method introduced by Raz (Theory Comput. 2006), which is used to prove all known multilinear lower bounds, can also be used to prove superpolynomial lower bounds on the size of mlABPs. In this paper, we analyze the potential of the min-partition rank method to prove lower bounds on the size of mlABPs, and show the following results: 1) We relate this method to a purely combinatorial question regarding the minimum size of set systems whose chains satisfy a discrepancy condition. In the case of set-multilinear ABPs, this combinatorial measure characterizes the best lower bound that can be achieved via the min-partition rank method. 2) We prove a non-trivial upper bound on the size of a set system satisfying this combinatorial property. Together with our construction of full-rank mlABPs from set systems, this recovers a superpolynomial separation between mlABPs and multilinear formulas (Dvir, Malod, Perifel and Yehudayoff (STOC 2012)) via a conceptually different proof. 3) The property we study extends combinatorial notions of "balancing sets" considered in previous works, for which near-tight bounds are known via intervals families. We show that any intervals set system is very far from satisfying our property. This showcases how our methods capture combinatorial structures that evade previous techniques, and also allows us to improve and generalize known lower bounds for sum of ordered set-multilinear ABPs (Chatterjee, Kush, Saraf, Shpilka (CCC 2024)). These results build a bridge between algebraic complexity theory and the behavior of random walks. Our upper bound uses the fact that, with noticeable probability, a random walk of length n on the integers returns to its starting point at least once every n/log n steps (Csáki, Erdős, and Révész (PTRF 1985)), while, for our lower bound, we prove that two independent random walks are "far" from each other in discrete Fréchet distance.

This work studies the expressivity of ReLU neural networks with a focus on their depth. A sequence of previous works showed that ⌈ log2(n+1) ⌉ hidden layers are sufficient to compute all continuous piecewise linear (CPWL) functions on ℝn. Hertrich, Basu, Di Summa, and Skutella (NeurIPS ’21 / SIDMA ’23) conjectured that this result is optimal in the sense that there are CPWL functions on ℝn, like the maximum function, that require this depth. We disprove the conjecture and show that ⌈log3(n−1)⌉+1 hidden layers are sufficient to compute all CPWL functions on ℝn.

We study the power of negation in the Boolean and algebraic settings and show the following results.

Learning theory has traditionally followed a model-centric approach, focusing on designing optimal algorithms for a fixed natural learning task (e.g., linear classification or regression). In this paper, we adopt a complementary data-centric perspective, whereby we fix a natural learning rule and focus on optimizing the training data. Specifically, we study the following question: given a learning rule $\mathcal{A}$ and a data selection budget $n$, how well can $\mathcal{A}$ perform when trained on at most $n$ data points selected from a population of $N$ points? We investigate when it is possible to select $n \ll N$ points and achieve performance comparable to training on the entire population. We address this question across a variety of empirical risk minimizers. Our results include optimal data-selection bounds for mean estimation, linear classification, and linear regression. Additionally, we establish two general results: a taxonomy of error rates in binary classification and in stochastic convex optimization. Finally, we propose several open questions and directions for future research.

This note proposes a set of open problems concerning data selection in regression tasks. The central question is: given a natural learning rule $\mathcal{A}$ and a selection budget $n$, how well can $\mathcal{A}$ perform when trained on $n$ examples selected from a larger dataset? We present concrete instances of this question in basic regression settings, including mean estimation and linear regression.

It is a well-known fact that the permanent polynomial is complete for the complexity class VNP, and it is largely suspected that the determinant does not share this property, despite its similar expression. We study the question of why the VNP-completeness proof of the permanent fails for the determinant. We isolate three fundamental properties that are sufficient to prove a polynomial sequence is VNP-hard, of which two are shared by both the permanent and the determinant. We proceed to show that the permanent satisfies the third property, which we refer to as the "cost of a boolean sum", while the determinant does not, showcasing the fundamental difference between the polynomial families. We further note that this differentiation also applies in the border complexity setting and that our results apply for counting complexity.

Stochastic convex optimization is one of the most well-studied models for learning in modern machine learning. Nevertheless, a central fundamental question in this setup remained unresolved: how many data points must be observed so that any empirical risk minimizer (ERM) shows good performance on the true population? This question was proposed by Feldman who proved that $\Omega(\frac{d}{\epsilon} + \frac{1}{\epsilon^2} )$ data points are necessary (where $d$ is the dimension and $\epsilon > 0$ the accuracy parameter). Proving an $\omega(\frac{d}{\epsilon} + \frac{1}{\epsilon^2})$ lower bound was left as an open problem. In this work we show that in fact $\tilde{O}(\frac{d}{\epsilon} + \frac{1}{\epsilon^2})$ data points are also sufficient. This settles the question and yields a new separation between ERMs and uniform convergence. This sample complexity holds for the classical setup of learning bounded convex Lipschitz functions over the Euclidean unit ball. We further generalize the result and show that a similar upper bound holds for all symmetric convex bodies. The general bound is composed of two terms: (i) a term of the form $\tilde{O}(\frac{d}{\epsilon})$ with an inverse-linear dependence on the accuracy parameter, and (ii) a term that depends on the statistical complexity of the class of linear functions (captured by the Rademacher complexity). The proof builds a mechanism for controlling the behavior of stochastic convex optimization problems.

This work studies embedding of arbitrary VC classes in well-behaved VC classes, focusing particularly on extremal classes. Our main result expresses an impossibility: such embeddings necessarily require a significant increase in dimension. In particular, we prove that for every $d$ there is a class with VC dimension $d$ that cannot be embedded in any extremal class of VC dimension smaller than exponential in $d$. In addition to its independent interest, this result has an important implication in learning theory, as it reveals a fundamental limitation of one of the most extensively studied approaches to tackling the long-standing sample compression conjecture. Concretely, the approach proposed by Floyd and Warmuth entails embedding any given VC class into an extremal class of a comparable dimension, and then applying an optimal sample compression scheme for extremal classes. However, our results imply that this strategy would in some cases result in a sample compression scheme at least exponentially larger than what is predicted by the sample compression conjecture. The above implications follow from a general result we prove: any extremal class with VC dimension $d$ has dual VC dimension at most $2d+1$. This bound is exponentially smaller than the classical bound $2^{d+1}-1$ of Assouad, which applies to general concept classes (and is known to be unimprovable for some classes). We in fact prove a stronger result, establishing that $2d+1$ upper bounds the dual Radon number of extremal classes. This theorem represents an abstraction of the classical Radon theorem for convex sets, extending its applicability to a wider combinatorial framework, without relying on the specifics of Euclidean convexity. The proof utilizes the topological method and is primarily based on variants of the Topological Radon Theorem.

We provide a unified framework for characterizing pure and approximate differentially private (DP) learnability. The framework uses the language of graph theory: for a concept class $\mathcal{H}$, we define the contradiction graph $G$ of $\mathcal{H}$. Its vertices are realizable datasets and two datasets $S,S’$ are connected by an edge if they contradict each other (i.e., there is a point $x$ that is labeled differently in $S$ and $S’$). Our main finding is that the combinatorial structure of $G$ is deeply related to learning $\mathcal{H}$ under DP. Learning $\mathcal{H}$ under pure DP is captured by the fractional clique number of $G$. Learning $\mathcal{H}$ under approximate DP is captured by the clique number of $G$. Consequently, we identify graph-theoretic dimensions that characterize DP learnability: the \emph{clique dimension} and \emph{fractional clique dimension}. Along the way, we reveal properties of the contradiction graph which may be of independent interest. We also suggest several open questions and directions for future research.

We use and adapt the Borsuk-Ulam Theorem from topology to derive limitations on list-replicable and globally stable learning algorithms. We further demonstrate the applicability of our methods in combinatorics and topology. We show that, besides trivial cases, both list-replicable and globally stable learning are impossible in the agnostic PAC setting. This is in contrast with the realizable case where it is known that any class with a finite Littlestone dimension can be learned by such algorithms. In the realizable PAC setting, we sharpen previous impossibility results and broaden their scope. Specifically, we establish optimal bounds for list replicability and global stability numbers in finite classes. This provides an exponential improvement over previous works and implies an exponential separation from the Littlestone dimension. We further introduce lower bounds for weak learners, i.e., learners that are only marginally better than random guessing. Lower bounds from previous works apply only to stronger learners. To offer a broader and more comprehensive view of our topological approach, we prove a local variant of the Borsuk-Ulam theorem in topology and a result in combinatorics concerning Kneser colorings. In combinatorics, we prove that if c is a coloring of all non-empty subsets of [n] such that disjoint sets have different colors, then there is a chain of subsets that receives at least 1+ ⌊ n/2⌋ colors (this bound is sharp). In topology, we prove e.g. that for any open antipodal-free cover of the d-dimensional sphere, there is a point ‍x that belongs to at least t=⌈d+3/2⌉ sets.

Abstract A matrix is blocky if it is a "blowup" of a permutation matrix. The blocky rank of a matrix M is the minimum number of blocky matrices that linearly span M. Hambardzumyan, Hatami and Hatami defined blocky rank and showed that it is connected to communication complexity and operator theory. We describe additional connections to circuit complexity and combinatorics, and we prove upper and lower bounds on blocky rank in various contexts.

Replicability is essential in science as it allows us to validate and verify research findings. Impagliazzo, Lei, Pitassi and Sorrell ('22) recently initiated the study of replicability in machine learning. A learning algorithm is replicable if it typically produces the same output when applied on two i.i.d. inputs using the same internal randomness. We study a variant of replicability that does not involve fixing the randomness. An algorithm satisfies this form of replicability if it typically produces the same output when applied on two i.i.d. inputs (without fixing the internal randomness). This variant is called global stability and was introduced by Bun, Livni and Moran ('20) in the context of differential privacy. Impagliazzo et al. showed how to boost any replicable algorithm so that it produces the same output with probability arbitrarily close to 1. In contrast, we demonstrate that for numerous learning tasks, global stability can only be accomplished weakly, where the same output is produced only with probability bounded away from 1. To overcome this limitation, we introduce the concept of list replicability, which is equivalent to global stability. Moreover, we prove that list replicability can be boosted so that it is achieved with probability arbitrarily close to 1. We also describe basic relations between standard learningtheoretic complexity measures and list replicable numbers. Our results, in addition, imply that besides trivial cases, replicable algorithms (in the sense of Impagliazzo et al.) must be randomized. The proof of the impossibility result is based on a topological fixed-point theorem. For every algorithm, we are able to locate a "hard input distribution by applying the Poincaré-Miranda theorem in a related topological setting. The equivalence between global stability and list replicability is algorithmic.

A seminal result in learning theory characterizes the PAC learnability of binary classes through the Vapnik-Chervonenkis dimension. Extending this characterization to the general multiclass setting has been open since the pioneering works on multiclass PAC learning in the late 1980s. This work resolves this problem: we characterize multiclass PAC learnability through the DS dimension, a combinatorial dimension defined by Daniely and Shalev-Shwartz, (2014). The classical characterization of the binary case boils down to empirical risk minimization. In contrast, our characterization of the multiclass case involves a variety of algorithmic ideas; these include a natural setting we call list PAC learning. In the list learning setting, instead of predicting a single outcome for a given unseen input, the goal is to provide a short menu of predictions. Our second main result concerns the Natarajan dimension, which has been a central candidate for characterizing multiclass learnability. This dimension was introduced by Natarajan (1988) as a barrier for PAC learning. He furthered showed that it is the only barrier, provided that the number of labels is bounded. Whether the Natarajan dimension characterizes PAC learnability in general has been posed as an open question in several papers since. This work provides a negative answer: we construct a non-learnable class with Natarajan dimension 1. For the construction, we identify a fundamental connection between concept classes and topology (i.e., colorful simplicial complexes). We crucially rely on a deep and involved construction of hyperbolic pseudo-manifolds by Januszkiewicz and Światkowski. It is interesting that hyperbolicity is directly related to learning problems that are difficult to solve although no obvious barriers exist. This is another demonstration of the fruitful links machine learning has with different areas in mathematics.

We prove anticoncentration bounds for the inner product of two independent random vectors and use these bounds to prove lower bounds in communication complexity. We show that if $A,B$ are subsets of the cube $\{\pm 1\}^n$ with $|A| \cdot |B| \geq 2^{1.01 n}$, and $X \in A$ and $Y \in B$ are sampled independently and uniformly, then the inner product $\langle{X},{Y}\rangle$ takes on any fixed value with probability at most $O(1/\sqrt{n})$. In fact, we prove the following stronger “smoothness" statement: $ \max_{k } \big| \Pr[\langle{X},{Y}\rangle = k] - \Pr[\langle{X},{Y}\rangle = k+4]\big| \leq O(1/n).$ We use these results to prove that the exact gap-hamming problem requires linear communication, resolving an open problem in communication complexity. We also conclude anticoncentration for structured distributions with low entropy. If $x \in \mathbb{Z}^n$ has no zero coordinates, and $B \subseteq \{\pm 1\}^n$ corresponds to a subspace of $\mathbb{F}_2^n$ of dimension $0.51n$, then $\max_k \Pr[\langle{x},{Y}\rangle = k] \leq O(\sqrt{\ln (n)/n})$.

We define the shadow complexity of a polytope P as the maximum number of vertices in a linear projection of P to the plane. We describe connections to algebraic complexity and to parametrized optimization. We also provide several basic examples and constructions, and develop tools for bounding shadow complexity.

We consider the following question: using a source of labeled data and interaction with an untrusted prover, what is the complexity of verifying that a given hypothesis is "approximately correct"? We study interactive proof systems for PAC verification, where a verifier that interacts with a prover is required to accept good hypotheses, and reject bad hypotheses. Both the verifier and the prover are efficient and have access to labeled data samples from an unknown distribution. We are interested in cases where the verifier can use significantly less data than is required for (agnostic) PAC learning, or use a substantially cheaper data source (e.g., using only random samples for verification, even though learning requires membership queries). We believe that today, when data and data-driven algorithms are quickly gaining prominence, the question of verifying purported outcomes of data analyses is very well-motivated. We show three main results. First, we prove that for a specific hypothesis class, verification is significantly cheaper than learning in terms of sample complexity, even if the verifier engages with the prover only in a single-round (NP-like) protocol. Moreover, for this class we prove that single-round verification is also significantly cheaper than testing closeness to the class. Second, for the broad class of Fourier-sparse boolean functions, we show a multi-round (IP-like) verification protocol, where the prover uses membership queries, and the verifier is able to assess the result while only using random samples. Third, we show that verification is not always more efficient. Namely, we show a class of functions where verification requires as many samples as learning does, up to a logarithmic factor.

A fundamental result in statistical learning theory is the equivalence of PAC learnability of a class with the finiteness of its Vapnik-Chervonenkis dimension. However, this clean result applies only to binary classification problems. In search for a similar combinatorial characterization of learnability in a more general setting, we discovered a surprising independence of set theory for some basic general notion of learnability. Consider the following statistical estimation problem: given a family F of real valued random variables over some domain X and an i.i.d. sample drawn from an unknown distribution P over X, find f in F such that its expectation w.r.t. P is close to the supremum expectation over all members of F. This Expectation Maximization (EMX) problem captures many well studied learning problems. Surprisingly, we show that the EMX learnability of some simple classes depends on the cardinality of the continuum and is therefore independent of the set theory ZFC axioms. Our results imply that that there exist no "finitary" combinatorial parameter that characterizes EMX learnability in a way similar to the VC-dimension characterization of binary classification learnability.

How quickly can a given class of concepts be learned from examples? It is common to measure the performance of a supervised machine learning algorithm by plotting its “learning curve”, that is, the decay of the error rate as a function of the number of training examples. However, the classical theoretical framework for understanding learnability, the PAC model of Vapnik-Chervonenkis and Valiant, does not explain the behavior of learning curves: the distribution-free PAC model of learning can only bound the upper envelope of the learning curves over all possible data distributions. This does not match the practice of machine learning, where the data source is typically fixed in any given scenario, while the learner may choose the number of training examples on the basis of factors such as computational resources and desired accuracy.

We show that the Radon number characterizes the existence of weak nets in separable convexity spaces (an abstraction of the Euclidean notion of convexity). The construction of weak nets when the Radon number is finite is based on Helly’s property and on metric properties of VC classes. The lower bound on the size of weak nets when the Radon number is large relies on the chromatic number of the Kneser graph. As an application, we prove an amplification result for weak $$\epsilon $$ -nets.

How many bits of information are revealed by a learning algorithm for a concept class of VC-dimension $d$? Previous works have shown that even for $d=1$ the amount of information may be unbounded (tend to $\infty$ with the universe size). Can it be that all concepts in the class require leaking a large amount of information? We show that typically concepts do not require leakage. There exists a proper learning algorithm that reveals $O(d)$ bits of information for most concepts in the class. This result is a special case of a more general phenomenon we explore. If there is a low information learner when the algorithm \emph{knows} the underlying distribution on inputs, then there is a learner that reveals little information on an average concept \emph{without knowing} the distribution on inputs.

This work studies distributed learning in the spirit of Yao’s model of communication complexity: consider a two-party setting, where each of the players gets a list of labelled examples and they communicate in order to jointly perform some learning task. To naturally fit into the framework of learning theory, the players can send each other examples (as well as bits) where each example/bit costs one unit of communication. This enables a uniform treatment of infinite classes such as half-spaces in $\R^d$, which are ubiquitous in machine learning. We study several fundamental questions in this model. For example, we provide combinatorial characterizations of the classes that can be learned with efficient communication in the proper-case as well as in the improper-case. These findings imply unconditional separations in this context between various learning tasks, e.g. realizable versus agnostic learning, proper versus improper learning, etcetera. %They also imply lower bounds that match the performance %of algorithm from previous works. The derivation of these results hinges on a type of decision problems we term “{\it realizability problems}” where the goal is deciding whether a distributed input sample is consistent with an hypothesis from a pre-specified class. From a technical perspective, the protocols we devise (i.e. the upper bounds) are based on ideas from machine learning and the impossibility results (i.e. the lower bounds) are based on ideas from communication complexity.

There are various notions of balancing set families that appear in combinatorics and computer science. For example, a family of proper non-empty subsets S_1,...,S_k subset [n] is balancing if for every subset X subset {1,2,...,n} of size n/2, there is an i in [k] so that |S_i cap X| = |S_i|/2. We extend and simplify the framework developed by Hegedűs for proving lower bounds on the size of balancing set families. We prove that if n=2p for a prime p, then k >= p. For arbitrary values of n, we show that k >= n/2 - o(n). We then exploit the connection between balancing families and depth-2 threshold circuits. This connection helps resolve a question raised by Kulikov and Podolskii on the fan-in of depth-2 majority circuits computing the majority function on n bits. We show that any depth-2 threshold circuit that computes the majority on n bits has at least one gate with fan-in at least n/2 - o(n). We also prove a sharp lower bound on the fan-in of depth-2 threshold circuits computing a specific weighted threshold function.

The conflict-driven clause learning (CDCL) paradigm has revolutionized SAT solving over the last two decades. Extending this approach to pseudo-Boolean (PB) solvers doing 0-1 linear programming holds the promise of further exponential improvements in theory, but intriguingly such gains have not materialized in practice. Also intriguingly, most PB extensions of CDCL use not the division rule in cutting planes as defined in [Cook et al., '87] but instead the so-called saturation rule. To the best of our knowledge, there has been no study comparing the strengths of division and saturation in the context of conflict-driven PB learning, when all linear combinations of inequalities are required to cancel variables. We show that PB solvers with division instead of saturation can be exponentially stronger. In the other direction, we prove that simulating a single saturation step can require an exponential number of divisions. We also perform some experiments to see whether these phenomena can be observed in actual solvers. Our conclusion is that a careful combination of division and saturation seems to be crucial to harness more of the power of cutting planes.

Key-agreement protocols whose security is proven in the random oracle model are an important alternative to protocols based on public-key cryptography. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but the parties are limited in the number of queries they can make to the oracle. The random oracle serves as an abstraction for black-box access to a symmetric cryptographic primitive, such as a collision resistant hash. Unfortunately, as shown by Impagliazzo and Rudich [STOC '89] and Barak and Mahmoody [Crypto '09], such protocols can only guarantee limited secrecy: the key of any l-query protocol can be revealed by an O(l^2)-query adversary. This quadratic gap between the query complexity of the honest parties and the eavesdropper matches the gap obtained by the Merkle's Puzzles protocol of Merkle [CACM '78]. In this work we tackle a new aspect of key-agreement protocols in the random oracle model: their communication complexity. In Merkle's Puzzles, to obtain secrecy against an eavesdropper that makes roughly l^2 queries, the honest parties need to exchange Omega(l) bits. We show that for protocols with certain natural properties, ones that Merkle's Puzzle has, such high communication is unavoidable. Specifically, this is the case if the honest parties' queries are uniformly random, or alternatively if the protocol uses non-adaptive queries and has only two rounds. Our proof for the first setting uses a novel reduction from the set-disjointness problem in two-party communication complexity. For the second setting we prove the lower bound directly, using information-theoretic arguments. Understanding the communication complexity of protocols whose security is proven (in the random-oracle model) is an important question in the study of practical protocols. Our results and proof techniques are a first step in this direction.

This work is about the monotone versions of the algebraic complexity classes VP and VNP. The main result is that monotone VNP is strictly stronger than monotone VP.

We study learning algorithms that are restricted to using a small amount of information from their input sample. We introduce a category of learning algorithms we term {\em $d$-bit information learners}, which are algorithms whose output conveys at most $d$ bits of information of their input. A central theme in this work is that such algorithms generalize. We focus on the learning capacity of these algorithms, and prove sample complexity bounds with tight dependencies on the confidence and error parameters. We also observe connections with well studied notions such as sample compression schemes, Occam’s razor, PAC-Bayes and differential privacy. We discuss an approach that allows us to prove upper bounds on the amount of information that algorithms reveal about their inputs, and also provide a lower bound by showing a simple concept class for which every (possibly randomized) empirical risk minimizer must reveal a lot of information. On the other hand, we show that in the distribution-dependent setting every VC class has empirical risk minimizers that do not reveal a lot of information.

How many bits of information are required to PAC learn a class of hypotheses of VC dimension $d$? The mathematical setting we follow is that of Bassily et al., where the value of interest is the mutual information $\mathrm{I}(S;A(S))$ between the input sample $S$ and the hypothesis outputted by the learning algorithm $A$. We introduce a class of functions of VC dimension $d$ over the domain $\mathcal{X}$ with information complexity at least $\Omega \left(d\log \log \frac{|\mathcal{X}|}{d}\right)$ bits for any consistent and proper algorithm (deterministic or random). Bassily et al. proved a similar (but quantitatively weaker) result for the case $d=1$. The above result is in fact a special case of a more general phenomenon we explore. We define the notion of {\em information complexity} of a given class of functions $\cH$. Intuitively, it is the minimum amount of information that an algorithm for $\mathcal{X}$ must retain about its input to ensure consistency and properness. We prove a direct sum result for information complexity in this context; roughly speaking, the information complexity sums when combining several classes.

We explore the ability of Evolution Strategies (ESs) to statistically learn the local landscape. Specifically, we consider ESs operating only with isotropic Gaussian mutations near the optimum and investigate the covariance matrix when constructed out of selected individuals by truncation. Unlike previous studies, we do not assume a Derandomization adaptation scheme, nor do we use Information Geometric Optimization in our proofs. We prove that the statistically constructed covariance matrix over such selected decision vectors has the same eigenvectors as the Hessian matrix. We further prove that when the population size is increased, the covariance becomes proportional to the inverse of the Hessian. We also devise and corroborate an analytic approximation of this covariance matrix. In the framework we consider, this confirms the classical hypothesis that learning the landscape is an inherent property of standard ESs, and that this capability stems only from the usage of isotropic Gaussian mutations and rank-based selection.

In this work we derive a variant of the classic Glivenko-Cantelli Theorem, which asserts uniform convergence of the empirical Cumulative Distribution Function (CDF) to the CDF of the underlying distribution. Our variant allows for tighter convergence bounds for extreme values of the CDF. We apply our bound in the context of revenue learning, which is a well-studied problem in economics and algorithmic game theory. We derive sample-complexity bounds on the uniform convergence rate of the empirical revenues to the true revenues, assuming a bound on the k'th moment of the valuations, for any (possibly fractional) k > 1. For uniform convergence in the limit, we give a complete characterization and a zero-one law: if the first moment of the valuations is finite, then uniform convergence almost surely occurs; conversely, if the first moment is infinite, then uniform convergence almost never occurs.

This work studies the maximum possible sign rank of N \times N sign matrices with a given VC dimension d. For d=1, this maximum is three. For d=2, this maximum is \tildeΘ(N^1/2). For d >2, similar but slightly less accurate statements hold. Our lower bounds improve over previous ones by Ben-David et al. and can be interpreted as exhibiting a weakness of kernel-based classifiers. Our upper bounds, on the other hand, can be interpreted as exhibiting the universality of kernel-based classifiers. The lower bounds are obtained by probabilistic constructions, using a theorem of Warren in real algebraic topology. The upper bounds are obtained using a result of Welzl about spanning trees with low stabbing number, and using the moment curve. The upper bound technique is also used to: (i) provide estimates on the number of classes of a given VC dimension, and the number of maximum classes of a given VC dimension – answering a question of Frankl from ’89, and (ii) design an efficient algorithm that provides an O(N/\log(N)) multiplicative approximation for the sign rank (computing the sign rank is equivalent to the existential theory of the reals). We also observe a general connection between sign rank and spectral gaps which is based on Forster’s argument. Consider the N \times N adjacency matrix of a ∆regular graph with a second eigenvalue of absolute value λand ∆≤N/2. We show that the sign rank of the signed version of this matrix is at least ∆/λ. We use this connection to prove the existence of a maximum class C⊆{\pm 1}^N with VC dimension 2 and sign rank \tildeΘ(N^1/2). This answers a question of Ben-David et al. regarding the sign rank of large VC classes. We also describe limitations of this approach, in the spirit of the Alon-Boppana theorem. We further describe connections to communication complexity, geometry, learning theory, and combinatorics.

The isoperimetric profile of a graph is a function that measures, for an integer k, the size of the smallest edge boundary over all sets of vertices of size k. We observe a connection between isoperimetric profiles and computational complexity. We illustrate this connection by an example from communication complexity, but our main result is in algebraic complexity. We prove a sharp super-polynomial separation between monotone arithmetic circuits and monotone arithmetic branching programs. This shows that the classical simulation of arithmetic circuits by arithmetic branching programs by Valiant, Skyum, Berkowitz, and Rackoff (1983) cannot be improved, as long as it preserves monotonicity. A key ingredient in the proof is an accurate analysis of the isoperimetric profile of finite full binary trees. We show that the isoperimetric profile of a full binary tree constantly fluctuates between one and almost the depth of the tree.

This work continues the study of the relationship between sample compression schemes and statistical learning, which has been mostly investigated within the framework of binary classification. We first extend the investigation to multiclass categorization: we prove that in this case learnability is equivalent to compression of logarithmic sample size and that the uniform convergence property implies compression of constant size. We use the compressibility-learnability equivalence to show that (i) for multiclass categorization, PAC and agnostic PAC learnability are equivalent, and (ii) to derive a compactness theorem for learnability. We then consider supervised learning under general loss functions: we show that in this case, in order to maintain the compressibility-learnability equivalence, it is necessary to consider an approximate variant of compression. We use it to show that PAC and agnostic PAC are not equivalent, even when the loss function has only three values.

Sample compression schemes were defined by Littlestone and Warmuth (1986) as an abstraction of the structure underlying many learning algorithms. Roughly speaking, a sample compression scheme of size k means that given an arbitrary list of labeled examples, one can retain only k of them in a way that allows us to recover the labels of all other examples in the list. They showed that compression implies probably approximately correct learnability for binary-labeled classes and asked whether the other direction holds. We answer their question and show that every concept class C with VC dimension d has a sample compression scheme of size exponential in d .

We study internal compression of communication protocols to their internal entropy, which is the entropy of the transcript from the players' perspective. We provide two internal compression schemes with error. One of a protocol of Feige et al. for finding the first difference between two strings. The second and main one is an internal compression with error epsilon > 0 of a protocol with internal entropy H^{int} and communication complexity C to a protocol with communication at most order (H^{int}/epsilon)^2 * log(log(C)). This immediately implies a similar compression to the internal information of public-coin protocols, which provides an exponential improvement over previously known public-coin compressions in the dependence on C. It further shows that in a recent protocol of Ganor, Kol and Raz, it is impossible to move the private randomness to be public without an exponential cost. To the best of our knowledge, No such example was previously known.

We show that the deterministic number-on-forehead communication complexity of set disjointness for k parties on a universe of size n is Omega(n/4^k). This gives the first lower bound that is linear in n, nearly matching Grolmusz's upper bound of O(log^2(n) + k^2n/2^k). We also simplify the proof of Sherstov's Omega(sqrt(n)/(k2^k)) lower bound for the randomized communication complexity of set disjointness.

In this work we study the quantitative relation between VC-dimension and two other basic parameters related to learning and teaching. Namely, the quality of sample compression schemes and of teaching sets for classes of low VC-dimension. Let C be a binary concept class of size m and VC-dimension d. Prior to this work, the best known upper bounds for both parameters were log(m), while the best lower bounds are linear in d. We present significantly better upper bounds on both as follows. We construct sample compression schemes of size exp(d) for C. This resolves a question of Littlest one and Warmuth (1986). Roughly speaking, we show that given an arbitrary set of labeled examples from an unknown concept in C, one can retain only a subset of exp(d) of them, in a way that allows to recover the labels of all other examples in the set, using additional exp(d) information bits. We further show that there always exists a concept c in C with a teaching set (i.e. A list of c-labeled examples uniquely identifying c in C) of size exp(d) log log(m). This problem was studied by Kuhlmann (1999). Our construction also implies that the recursive teaching (RT) dimension of C is at most exp(d) log log(m) as well. The RT-dimension was suggested by Zilles et al. And Doliwa et al. (2010). The same notion (under the name partial-ID width) was independently studied by Wigderson and Yehuday off (2013). An upper bound on this parameter that depends only on d is known just for the very simple case d=1, and is open even for d=2. We also make small progress towards this seemingly modest goal.

We show that in the model of zero error communication complexity, direct sum fails for average communication complexity as well as for external information cost. Our example also refutes a version of a conjecture by Braverman et al. that in the zero error case amortized communication complexity equals external information cost.

We give new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is either 0 or 2, except for the first layer. For every width $d$ and length $n$, our pseudorandom generator uses a seed of length $O((\log d + \log\log n + \log(1/\epsilon))\log n)$ to produce $n$ bits that cannot be distinguished from a uniformly random string by any regular width $d$ length $n$ read-once branching program, except with probability $\epsilon$. We also give a result for general read-once branching programs, in the case that there are no vertices that are reached with small probability. We show that if a (possibly nonregular) branching program of length $n$ and width $d$ has the property that every vertex in the program is traversed with probability at least $\gamma$ on a uniformly random input, then the error of the generator above is at most $2 \epsilon/\gamma^2$. Finally, we show that the set of all binary strings with less than $d$ nonzero entries forms a hitting set for regular width $d$ branching programs.

We give an example of a non-commutative mono-tone polynomial f which can be computed by a polynomial-size non-commutative formula, but every monotone non-commutative circuit computing f must have an exponential size. In the non-commutative setting this gives, a fortiori, an exponential separation between monotone and general formulas, monotone and general branching programs, and monotone and general circuits. This answers some questions raised by Nisan.

We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let suc(μ, f, C) denote the maximum success probability of a 2-party communication protocol for computing the boolean function f(x, y) with C bits of communication, when the inputs (x, y) are drawn from the distribution μ. Let μnbe the product distribution on n inputs and fndenote the function that computes n copies of f on these inputs. We prove that if T log3/2T ≪ (C - 1)√n and suc(μ, f, C)n, fn, T) ≤ exp(-Ω(n)). When μ is a product distribution, we prove a nearly optimal result: as long as T log2T ≪ Cn, we must have suc(μn, fn, T) ≤ exp(-Ω(n)).

We study several problems in which an unknown distribution over an unknown population of vectors needs to be recovered from partial or noisy samples, each of which nearly completely erases or obliterates the original vector. For example, consider a distribution p over a population V ⊆ {0, 1}n. A noisy sample v' is obtained by choosing v according to p and flipping each coordinate of v with probability say 0.49 independently. The problem is to recover V, p as efficiently as possible from noisy samples. Such problems naturally arise in a variety of contexts in learning, clustering, statistics, computational biology, data mining and database privacy, where loss and error may be introduced by nature, inaccurate measurements, or on purpose. We give fairly efficient algorithms to recover the data under fairly general assumptions. Underlying our algorithms is a new structure we call a partial identification (PID) graph for an arbitrary finite set of vectors over any alphabet. This graph captures the extent to which certain subsets of coordinates in each vector distinguish it from other vectors. PID graphs yield strategies for dimension reductions and re-assembly of statistical information. The quality of our algorithms (sequential and parallel runtime, as well as numerical stability) critically depends on three parameters of PID graphs: width, depth and cost. The combinatorial heart of this work is showing that every set of vectors posses a PID graph in which all three parameters are small (we prove some limitations on their trade-offs as well). We further give an efficient algorithm to find such near-optimal PID graphs for any set of vectors. Our efficient PID graphs imply general algorithms for these recovery problems, even when loss or noise are just below the information-theoretic limit! In the learning/clustering context this gives a new algorithm for learning mixtures of binomial distributions (with known marginals) whose running time depends only quasi-polynomially on the number of clusters. We discuss implications to privacy and coding as well.

We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call restriction access. Restrictions are partial assignments to input variables. Each restriction simplifies the device, and yields a new device for the restricted function on the unassigned variables. On one extreme, full restrictions (assigning all variables) correspond to evaluating the device on a complete input, yielding the result of the computation on that input, which is the same as standard black-box access. On the other extreme, empty restrictions (assigning no variables) yield a full description of the original device. We explore the grey-scale of possibilities in the middle.

This work presents an explicit construction of a family of monotone expanders, which are bi-partite expander graphs whose edge-set is defined by (partial) monotone functions. The family is essentially defined by the Mobius action of SL2(R), the group of 2 x 2 matrices with determinant one, on the interval [0,1]. No other proof-of-existence for monotone expanders is known, not even using the probabilistic method.

This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of multilinear ABPs to that of multilinear arithmetic formulas, and prove a tight super-polynomial separation between the two models. Specifically, we describe an explicit n-variate polynomial F that is computed by a linear-size multilinear ABP but every multilinear formula computing F must be of size nΩ(log n).

A (q,k,t)-design matrix is an m x n matrix whose pattern of zeros/non-zeros satisfies the following design-like condition: each row has at most q non-zeros, each column has at least k non-zeros and the supports of every two columns intersect in at most t rows. We prove that for m ≥ n, the rank of any (q,k,t)-design matrix over a field of characteristic zero (or sufficiently large finite characteristic) is at least n - (qtn/2k)2. Using this result we derive the following applications: Impossibility results for 2-query LCCs over large fields: A 2-query locally correctable code (LCC) is an error correcting code in which every codeword coordinate can be recovered, probabilistically, by reading at most two other code positions. Such codes have numerous applications and constructions (with exponential encoding length) are known over finite fields of small characteristic. We show that infinite families of such linear 2-query LCCs do not exist over fields of characteristic zero or large characteristic regardless of the encoding length. Generalization of known results in combinatorial geometry: We prove a quantitative analog of the Sylvester-Gallai theorem: Let v1,...,vm be a set of points in Cd such that for every i ∈ [m] there exists at least δ m values of j ∈ [m] such that the line through vi,vj contains a third point in the set. We show that the dimension of v1,...,vm is at most O(1/δ2). Our results generalize to the high-dimensional case (replaceing lines with planes, etc.) and to the case where the points are colored (as in the Motzkin-Rabin Theorem).

This paper extends Valiant's work on VP and VNP to the settings in which variables are not multiplicatively commutative and/or associative. Our main result is a theory of completeness for these algebraic worlds. We define analogs of Valiant's classes VP and VNP, as well as of the polynomials permanent and determinant, in these worlds. We then prove that even in a completely relationless world which assumes no commutativity nor associativity, permanent remains VNP-complete, and determinant can polynomially simulate any arithmetic formula, just as in the standard commutative, associative world of Valiant. In the absence of associativity, the completeness proof gives rise to the following combinatorial problem: what is the smallest binary tree which contains as minors all binary trees with n leaves. We give an explicit construction of such a universal tree of polynomial size, a result of possibly independent interest. Given that such non-trivial reductions are possible even without commutativity and associativity, we turn to lower bounds. In the non-associative, commutative world we prove exponential circuit lower bounds on explicit polynomials, separating the non-associative commutative analogs of VP and VNP. Obtaining such lower bounds and a separation in the complementary associative, non-commutative world has been open for about 30 years.

We give new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is either 0 or 2. For every width d and length n, our pseudorandom generator uses a seed of length O((log d + log log n + log(1/ϵ)) log n) to produce n bits that cannot be distinguished from a uniformly random string by any regular width d length n read-once branching program, except with probability ϵ. We also give a result for general read-once branching programs, in the case that there are no vertices that are reached with small probability. We show that if a (possibly non-regular) branching program of length n and width d has the property that every vertex in the program is traversed with probability at least γ on a uniformly random input, then the error of the generator above is at most 2ϵ/γ2.

We initiate a direction for proving lower bounds on the size of non-commutative arithmetic circuits. This direction is based on a connection between lower bounds on the size of non-commutative arithmetic circuits and a problem about commutative degree four polynomials, the classical sum-of-squares problem: find the smallest n such that there exists an identity (x12+x22+•• + xk2)• (y1^2+y22+•• + yk2)= f12+f22+ ... +fn2, where each fi = fi(X,Y) is bilinear in X={x1,... ,xk} and Y={y1,..., yk}. Over the complex numbers, we show that a sufficiently strong super-linear lower bound on n in, namely, n ≥ k1+ε with ε >0, implies an exponential lower bound on the size of arithmetic circuits computing the non-commutative permanent.

In this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. More formally, if there exists an explicit polynomial f that cannot be computed by a depth d arithmetic circuit of small size, then there exists an efficient deterministic black-box algorithm to test whether a given depth $d-5$ circuit that computes a polynomial of relatively small individual degrees is identically zero or not. In particular, if we are guaranteed that the tested circuit computes a multilinear polynomial, then we can perform the identity test efficiently. To the best of our knowledge this is the first hardness-randomness tradeoff for bounded depth arithmetic circuits. The above results are obtained using the arithmetic Nisan–Wigderson generator of Kabanets and Impagliazzo together with a new theorem on bounded depth circuits, which is the main technical contribution of our work. This theorem deals with polynomial equations of the form $P(x_1,\dots,x_n,y)\equiv0$ and shows that if P has a circuit of depth d and size s and if the polynomial $f(x_1,\dots,x_n)$ satisfies $P(x_1,\dots,x_n,f)\equiv0$, then f has a circuit of depth $d+3$ and size $\mathrm{poly}(s,m^r)$, where m is the total degree of f and r is the degree of y in P. This circuit for f can be found probabilistically in time $\mathrm{poly}(s,m^r)$. In the other direction we observe that the methods of Kabanets and Impagliazzo can be used to show that derandomizing identity testing for bounded depth circuits implies lower bounds for the same class of circuits. More formally, if we can derandomize polynomial identity testing for bounded depth circuits, then NEXP does not have bounded depth arithmetic circuits. That is, either $\mathrm{NEXP}\not\subseteq P/\mathrm{poly}$ or the Permanent is not computable by polynomial size bounded depth arithmetic circuits.

We prove an exponential lower bound for the size of constant depth multilinear arithmetic circuits computing either the determinant or the permanent (a circuit is called multilinear, if the polynomial computed by each of its gates is multilinear). We also prove a super-polynomial separation between the size of product-depth d and product-depth d+1 multilinear circuits (where d is constant). That is, there exists a polynomial f such that (1) There exists a multilinear circuit of product-depth d+1 and of polynomial size computing f and (2) Every multilinear circuit of product-depth d computing f has super-polynomial size.

We construct an explicit polynomial $f(x_1,\dots,x_n)$, with coefficients in $\{0,1\}$, such that the size of any syntactically multilinear arithmetic circuit computing f is at least $\Omega(n^{4/3}/\log^2n)$. The lower bound holds over any field.

We construct an explicit polynomial f(x1,..., xn), with coefficients in {0, 1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Omega{n4/3log2n} The lower bound holds over any field.