BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Amir Yehudayoff appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
We prove a vertex isoperimetric inequality for the $n$-dimensional Hamming ball $\mathcal{B}_n(R)$ of radius $R$. The isoperimetric inequality is sharp up to a constant factor for sets that are comparable to $\mathcal{B}_n(R)$ in size. A key step in the proof is a local expansion phenomenon in hypercubes.
We prove anti-concentration 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 anti-concentration for structured distributions with low entropy. If $x \in \mathcal{Z}^n$ has no zero coordinates, and $B \subseteq \{\pm 1\}^n$ corresponds to a subspace of $\mathcal{F}_2^n$ of dimension $0.51n$, then $\max_k \Pr[\langle x,Y \rangle = k] \leq O(\sqrt{\ln (n)/n})$.
The affine quermassintegrals associated to a convex body in $\mathbb{R}^n$ are affine-invariant analogues of the classical intrinsic volumes from the Brunn-Minkowski theory, and thus constitute a central pillar of affine convex geometry. They were introduced in the 1980's by E. Lutwak, who conjectured that among all convex bodies of a given volume, the $k$-th affine quermassintegral is minimized precisely on the family of ellipsoids. The known cases $k=1$ and $k=n-1$ correspond to the classical Blaschke-Santaló and Petty projection inequalities, respectively. In this work we confirm Lutwak's conjecture, including characterization of the equality cases, for all values of $k=1,\ldots,n-1$, in a single unified framework. In fact, it turns out that ellipsoids are the only local minimizers with respect to the Hausdorff topology. For the proof, we introduce a number of new ingredients, including a novel construction of the Projection Rolodex of a convex body. In particular, from this new view point, Petty's inequality is interpreted as an integrated form of a generalized Blaschke--Santaló inequality for a new family of polar bodies encoded by the Projection Rolodex. We extend these results to more general $L^p$-moment quermassintegrals, and interpret the case $p=0$ as a sharp averaged Loomis--Whitney isoperimetric inequality.
We prove that at least $Ω(n^{0.51})$ hyperplanes are needed to slice all edges of the $n$-dimensional hypercube. We provide a couple of applications: lower bounds on the computational complexity of parity, and a lower bound on the cover number of the hypercube by skew hyperplanes.
This paper studies the complexity of distributed construction of purely additive spanners in the CONGEST model. We describe algorithms for building such spanners in several cases. Because of the need to simultaneously make decisions at far apart locations, the algorithms use additional mechanisms compared to their sequential counterparts. We complement our algorithms with a lower bound on the number of rounds required for computing pairwise spanners. The standard reductions from set-disjointness and equality seem unsuitable for this task because no specific edge needs to be removed from the graph. Instead, to obtain our lower bound, we define a new communication complexity problem that reduces to computing a sparse spanner, and prove a lower bound on its communication complexity using information theory. This technique significantly extends the current toolbox used for obtaining lower bounds for the CONGEST model, and we believe it may find additional applications.
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. The central theme of this work is establishing equivalences between learnability and compressibility, and utilizing these equivalences in the study of statistical learning theory. We begin with the setting of multiclass categorization (zero/one loss). We prove that in this case learnability is equivalent to compression of logarithmic sample size, and that uniform convergence implies compression of constant size. We then consider Vapnik's general learning setting: we show that in order to extend the compressibility-learnability equivalence to this case, it is necessary to consider an approximate variant of compression. Finally, we provide some applications of the compressibility-learnability equivalences: (i) Agnostic-case learnability and realizable-case learnability are equivalent in multiclass categorization problems (in terms of sample complexity). (ii) This equivalence between agnostic-case learnability and realizable-case learnability does not hold for general learning problems: There exists a learning problem whose loss function takes just three values, under which agnostic-case and realizable-case learnability are not equivalent. (iii) Uniform convergence implies compression of constant size in multiclass categorization problems. Part of the argument includes an analysis of the uniform convergence rate in terms of the graph dimension, in which we improve upon previous bounds. (iv) A dichotomy for sample compression in multiclass categorization problems: If a non-trivial compression exists then a compression of logarithmic size exists. (v) A compactness theorem for multiclass categorization problems.
We study the theoretical capacity to statistically learn local landscape information by Evolution Strategies (ESs). Specifically, we investigate the covariance matrix when constructed by ESs operating with the selection operator alone. We model continuous generation of candidate solutions about quadratic basins of attraction, with deterministic selection of the decision vectors that minimize the objective function values. Our goal is to rigorously show that accumulation of winning individuals carries the potential to reveal valuable information about the search landscape, e.g., as already practically utilized by derandomized ES variants. We first show that the statistically-constructed covariance matrix over such winning decision vectors shares the same eigenvectors with the Hessian matrix about the optimum. We then provide an analytic approximation of this covariance matrix for a non-elitist multi-child $(1,λ)$-strategy, which holds for a large population size $λ$. Finally, we also numerically corroborate our results.
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. {The lower bounds improve over previous ones by Ben-David et al., and the upper bounds are novel.} 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. 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 $Δ\leq 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\subseteq\{\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.
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. Set $k = O(d 2^d \log \log |C|)$. We 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 $k$. This problem was studied by Kuhlmann (1999). Our construction implies that the recursive teaching (RT) dimension of $C$ is at most $k$ 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 Yehudayoff (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 further construct sample compression schemes of size $k$ for $C$, with additional information of $k \log(k)$ bits. Roughly speaking, given any list of $C$-labelled examples of arbitrary length, we can retain only $k$ labeled examples in a way that allows to recover the labels of all others examples in the list, using additional $k\log (k)$ information bits. This problem was first suggested by Littlestone and Warmuth (1986).
The aim of this text is to provide an elementary and self-contained exposition of Gromov's argument on topological overlap (the presentation is based on Gromov's work, as well as two follow-up papers of Matousek and Wagner, and of Dotterrer, Kaufman and Wagner). We also discuss a simple generalization in which the vertices are weighted according to some probability distribution. This allows to use von Neumann's minimax theorem to deduce a dual statement.
We study the extent of independence needed to approximate the product of bounded random variables in expectation, a natural question that has applications in pseudorandomness and min-wise independent hashing. For random variables whose absolute value is bounded by $1$, we give an error bound of the form $σ^{Ω(k)}$ where $k$ is the amount of independence and $σ^2$ is the total variance of the sum. Previously known bounds only applied in more restricted settings, and were quanitively weaker. We use this to give a simpler and more modular analysis of a construction of min-wise independent hash functions and pseudorandom generators for combinatorial rectangles due to Gopalan et al., which also slightly improves their seed-length. Our proof relies on a new analytic inequality for the elementary symmetric polynomials $S_k(x)$ for $x \in \mathbb{R}^n$ which we believe to be of independent interest. We show that if $|S_k(x)|,|S_{k+1}(x)|$ are small relative to $|S_{k-1}(x)|$ for some $k>0$ then $|S_\ell(x)|$ is also small for all $\ell > k$. From these, we derive tail bounds for the elementary symmetric polynomials when the inputs are only $k$-wise independent.
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 to recover the labels of all other examples in the list. They showed that compression implies PAC 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$. The proof uses an approximate minimax phenomenon for binary matrices of low VC dimension, which may be of interest in the context of game theory.
A grounded M-Lipschitz function on a rooted d-ary tree is an integer-valued map on the vertices that changes by at most along edges and attains the value zero on the leaves. We study the behavior of such functions, specifically, their typical value at the root v_0 of the tree. We prove that the probability that the value of a uniformly chosen random function at v_0 is more than M+t is doubly-exponentially small in t. We also show a similar bound for continuous (real-valued) grounded Lipschitz functions.
Lawler, Schramm and Werner showed that the scaling limit of the loop-erased random walk on $\mathbb{Z}^2$ is $\mathrm{SLE}_2$. We consider scaling limits of the loop-erasure of random walks on other planar graphs (graphs embedded into $\mathbb{C}$ so that edges do not cross one another). We show that if the scaling limit of the random walk is planar Brownian motion, then the scaling limit of its loop-erasure is $\mathrm{SLE}_2$. Our main contribution is showing that for such graphs, the discrete Poisson kernel can be approximated by the continuous one. One example is the infinite component of super-critical percolation on $\mathbb{Z}^2$. Berger and Biskup showed that the scaling limit of the random walk on this graph is planar Brownian motion. Our results imply that the scaling limit of the loop-erased random walk on the super-critical percolation cluster is $\mathrm{SLE}_2$.
Internal Diffusion Limited Aggregation (IDLA) is a model that describes the growth of a random aggregate of particles from the inside out. Shellef proved that IDLA processes on supercritical percolation clusters of integer-lattices fill Euclidean balls, with high probability. In this article, we complete the picture and prove a limit-shape theorem for IDLA on such percolation clusters, by providing the corresponding upper bound. The technique to prove upper bounds is new and robust: it only requires the existence of a "good" lower bound. Specifically, this way of proving upper bounds on IDLA clusters is more suitable for random environments than previous ways, since it does not harness harmonic measure estimates.
This work, following the outline set in [B2], presents an explicit construction of a family of monotone expanders. The family is essentially defined by the Mobius action of SL_2(R) on the real line. For the proof, we show a product-growth theorem for SL_2(R).
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 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: (1) Impossibility results for 2-query LCCs over the complex numbers: 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 the complex numbers. (2) Generalization of results in combinatorial geometry: We prove a quantitative analog of the Sylvester-Gallai theorem: Let $v_1,...,v_m$ be a set of points in $\C^d$ such that for every $i \in [m]$ there exists at least $δm$ values of $j \in [m]$ such that the line through $v_i,v_j$ contains a third point in the set. We show that the dimension of $\{v_1,...,v_m \}$ is at most $O(1/δ^2)$. Our results generalize to the high dimensional case (replacing lines with planes, etc.) and to the case where the points are colored (as in the Motzkin-Rabin Theorem).
A k-wise independent distribution on n bits is a joint distribution of the bits such that each k of them are independent. In this paper we consider k-wise independent distributions with identical marginals, each bit has probability p to be 1. We address the following question: how high can the probability that all the bits are 1 be, for such a distribution? For a wide range of the parameters n,k and p we find an explicit lower bound for this probability which matches an upper bound given by Benjamini et al., up to multiplicative factors of lower order. The question we investigate can be seen as a relaxation of a major open problem in error-correcting codes theory, namely, how large can a linear error correcting code with given parameters be? The question is a type of discrete moment problem, and our approach is based on showing that bounds obtained from the theory of the classical moment problem provide good approximations for it. The main tool we use is a bound controlling the change in the expectation of a polynomial after small perturbation of its zeros.
We study the entropy of the set traced by an $n$-step random walk on $\Z^d$. We show that for $d \geq 3$, the entropy is of order $n$. For $d = 2$, the entropy is of order $n/\log^2 n$. These values are essentially governed by the size of the boundary of the trace.