All reports by Author Amir Yehudayoff:

__
TR22-137
| 26th September 2022
__

Daniel Avraham , Amir Yehudayoff#### On blocky ranks of matrices

__
TR22-035
| 7th March 2022
__

Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff#### A Characterization of Multiclass Learnability

__
TR21-148
| 3rd November 2021
__

Benjamin Diamond, Amir Yehudayoff#### Explicit Exponential Lower Bounds for Exact Hyperplane Covers

Revisions: 1

__
TR21-102
| 13th July 2021
__

Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff#### Tight bounds on the Fourier growth of bounded functions on the hypercube

Revisions: 1

__
TR20-189
| 24th December 2020
__

Pavel Hrubes, Amir Yehudayoff#### Shadows of Newton polytopes

__
TR20-058
| 24th April 2020
__

Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff#### Interactive Proofs for Verifying Machine Learning

Revisions: 1

__
TR20-006
| 22nd January 2020
__

Anup Rao, Amir Yehudayoff#### The Communication Complexity of the Exact Gap-Hamming Problem

__
TR19-026
| 28th February 2019
__

Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff#### Lower Bounds on Balancing Sets and Depth-2 Threshold Circuits

Revisions: 1

__
TR18-194
| 15th November 2018
__

Amir Yehudayoff#### Anti-concentration in most directions

Revisions: 5

__
TR18-124
| 6th July 2018
__

Amir Yehudayoff#### Separating Monotone VP and VNP

__
TR18-031
| 15th February 2018
__

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff#### On the Communication Complexity of Key-Agreement Protocols

Revisions: 2

__
TR17-177
| 16th November 2017
__

Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff#### On Communication Complexity of Classification Problems

Revisions: 1

__
TR16-151
| 26th September 2016
__

Amir Yehudayoff#### Pointer chasing via triangular discrimination

__
TR15-164
| 13th October 2015
__

Pavel Hrubes, Amir Yehudayoff#### On isoperimetric profiles and computational complexity

__
TR15-040
| 24th March 2015
__

Shay Moran, Amir Yehudayoff#### Proper PAC learning is compressing

Revisions: 1

__
TR15-025
| 22nd February 2015
__

Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff#### Teaching and compressing for low VC-dimension

__
TR14-135
| 23rd October 2014
__

Noga Alon, Shay Moran, Amir Yehudayoff#### Sign rank, VC dimension and spectral gaps

Revisions: 2

__
TR14-101
| 8th August 2014
__

Balthazar Bauer, Shay Moran, Amir Yehudayoff#### Internal compression of protocols to entropy

Revisions: 1

__
TR14-060
| 21st April 2014
__

Anup Rao, Amir Yehudayoff#### Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness

Revisions: 1

__
TR14-046
| 8th April 2014
__

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff#### Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound

__
TR14-022
| 19th February 2014
__

Shay Moran, Makrand Sinha, Amir Yehudayoff#### Fooling Pairs in Randomized Communication Complexity

Revisions: 1

__
TR14-019
| 14th February 2014
__

Parikshit Gopalan, Amir Yehudayoff#### Inequalities and tail bounds for elementary symmetric polynomials

__
TR13-106
| 29th July 2013
__

Shay Moran, Amir Yehudayoff#### A note on average-case sorting

Revisions: 2

__
TR13-079
| 2nd June 2013
__

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff#### Direct Sum Fails for Zero Error Average Communication

__
TR13-035
| 6th March 2013
__

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff#### Direct product via round-preserving compression

Revisions: 1

__
TR12-143
| 5th November 2012
__

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff#### Direct Products in Communication Complexity

Revisions: 2

__
TR12-118
| 18th September 2012
__

Avi Wigderson, Amir Yehudayoff#### Population Recovery and Partial Identification

__
TR12-061
| 16th May 2012
__

Pavel Hrubes, Amir Yehudayoff#### Formulas are exponentially stronger than monotone circuits in non-commutative setting

__
TR11-160
| 1st December 2011
__

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff#### Restriction Access

__
TR11-134
| 9th October 2011
__

Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff#### Separating multilinear branching programs and formulas

__
TR10-149
| 22nd September 2010
__

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff#### Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes

Revisions: 1

__
TR10-040
| 10th March 2010
__

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff#### Relationless completeness and separations

__
TR10-035
| 7th March 2010
__

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff#### Pseudorandom Generators for Regular Branching Programs

__
TR10-021
| 21st February 2010
__

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff#### Non-commutative circuits and the sum-of-squares problem

__
TR09-070
| 1st September 2009
__

Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff#### Pseudorandomness for Width 2 Branching Programs

__
TR08-006
| 18th January 2008
__

Ran Raz, Amir Yehudayoff#### Lower Bounds and Separations for Constant Depth Multilinear Circuits

__
TR07-121
| 21st November 2007
__

Zeev Dvir, Amir Shpilka, Amir Yehudayoff#### Hardness-Randomness Tradeoffs for Bounded Depth Arithmetic Circuits

__
TR07-085
| 2nd September 2007
__

Ran Raz, Amir Yehudayoff#### Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors

__
TR06-060
| 4th May 2006
__

Ran Raz, Amir Shpilka, Amir Yehudayoff#### A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

Daniel Avraham , Amir Yehudayoff

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. ... more >>>

Nataly Brukhim, Daniel Carmon, Irit Dinur, Shay Moran, Amir Yehudayoff

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 ... more >>>

Benjamin Diamond, Amir Yehudayoff

We describe an explicit and simple subset of the discrete hypercube which cannot be exactly covered by fewer than exponentially many hyperplanes. The proof exploits a connection to communication complexity, and relies heavily on Razborov's lower bound for disjointness.

more >>>Siddharth Iyer, Anup Rao, Victor Reis, Thomas Rothvoss, Amir Yehudayoff

We give tight bounds on the degree $\ell$ homogenous parts $f_\ell$ of a bounded function $f$ on the cube. We show that if $f: \{\pm 1\}^n \rightarrow [-1,1]$ has degree $d$, then $\| f_\ell \|_\infty$ is bounded by $d^\ell/\ell!$, and $\| \hat{f}_\ell \|_1$ is bounded by $d^\ell e^{{\ell+1 \choose 2}} ... more >>>

Pavel Hrubes, Amir Yehudayoff

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.

Shafi Goldwasser, Guy Rothblum, Jonathan Shafer, Amir Yehudayoff

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 ... more >>>

Anup Rao, Amir Yehudayoff

We prove a sharp lower bound on the distributional communication complexity of the exact gap-hamming problem.

more >>>Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao, Amir Yehudayoff

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,\ldots,S_k \subset [n]$ is balancing if for every subset $X \subset \{1,2,\ldots,n\}$ of size $n/2$, there is an $i \in [k]$ so that $|S_i \cap X| = ... more >>>

Amir Yehudayoff

We prove anti-concentration for the inner product of two independent random vectors in the discrete cube. Our results imply Chakrabarti and Regev's lower bound on the randomized communication complexity of the gap-hamming problem. They are also meaningful in the context of randomness extraction. The proof provides a framework for establishing ... more >>>

Amir Yehudayoff

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.

Iftach Haitner, Noam Mazor, Rotem Oshman, Omer Reingold, Amir Yehudayoff

Key-agreement protocols whose security is proven in the random oracle model are an important alternative to the more common public-key based key-agreement protocols. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but they are limited in the number of ... more >>>

Daniel Kane, Roi Livni, Shay Moran, Amir Yehudayoff

This work introduces a model of distributed learning in the spirit of Yao's communication complexity model. We 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 ... more >>>

Amir Yehudayoff

We prove an essentially sharp $\tilde\Omega(n/k)$ lower bound on the $k$-round distributional complexity of the $k$-step pointer chasing problem under the uniform distribution, when Bob speaks first. This is an improvement over Nisan and Wigderson's $\tilde \Omega(n/k^2)$ lower bound. A key part of the proof is using triangular discrimination instead ... more >>>

Pavel Hrubes, Amir Yehudayoff

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, ... more >>>

Shay Moran, Amir Yehudayoff

We prove that proper PAC learnability implies compression. Namely, if a concept $C \subseteq \Sigma^X$ is properly PAC learnable with $d$ samples, then $C$ has a sample compression scheme of size $2^{O(d)}$.

In particular, every boolean concept class with constant VC dimension has a sample compression scheme of constant size. ...
more >>>

Shay Moran, Amir Shpilka, Avi Wigderson, Amir Yehudayoff

In this work we study the quantitative relation between VC-dimension and two other basic parameters related to learning and teaching. We present relatively efficient constructions of {\em sample compression schemes} and

for classes of low VC-dimension. Let $C$ be a finite boolean concept class of VC-dimension $d$. Set $k ...
more >>>

Noga Alon, Shay Moran, Amir Yehudayoff

We study the maximum possible sign rank of $N \times N$ sign matrices with a given VC dimension $d$. For $d=1$, this maximum is $3$. For $d=2$, this maximum is $\tilde{\Theta}(N^{1/2})$. Similar (slightly less accurate) statements hold for $d>2$ as well. We discuss the tightness of our methods, and describe ... more >>>

Balthazar Bauer, Shay Moran, Amir Yehudayoff

We study internal compression of communication protocols

to their internal entropy, which is the entropy of the transcript from the players' perspective.

We first show that errorless compression to the internal entropy

(and hence to the internal information) is impossible.

We then provide two internal compression schemes with error.

One ...
more >>>

Anup Rao, Amir Yehudayoff

We show that the deterministic multiparty communication complexity of set disjointness for $k$ parties on a universe of size $n$ is $\Omega(n/4^k)$. We also simplify Sherstov's proof

showing an $\Omega(\sqrt{n}/(k2^k))$ lower bound for the randomized communication complexity of set disjointness.

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

We consider two known lower bounds on randomized communication complexity: The smooth rectangle bound and the logarithm of the approximate non-negative rank. Our main result is that they are the same up to a multiplicative constant and a small additive term.

The logarithm of the nonnegative rank is known to ...
more >>>

Shay Moran, Makrand Sinha, Amir Yehudayoff

Fooling pairs are one of the standard methods for proving lower bounds for deterministic two-player communication complexity. We study fooling pairs in the context of randomized communication complexity.

We show that every fooling pair induces far away distributions on transcripts of private-coin protocols. We then conclude that the private-coin randomized ...
more >>>

Parikshit Gopalan, Amir Yehudayoff

This paper studies the elementary symmetric polynomials $S_k(x)$ for $x \in \mathbb{R}^n$. We show that if $|S_k(x)|,|S_{k+1}(x)|$ are small for some $k>0$ then $|S_\ell(x)|$ is also small for all $\ell > k$. We use this to prove probability tail bounds for the symmetric polynomials when the inputs are only $t$-wise ... more >>>

Shay Moran, Amir Yehudayoff

This note studies the average-case comparison-complexity of sorting n elements when there is a known distribution on inputs and the goal is to minimize

the expected number of comparisons. We generalize Fredman's algorithm which

is a variant of insertion sort and provide a basically tight upper bound: If \mu is

more >>>

Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff

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 ... more >>>

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

We obtain a strong direct product theorem for two-party bounded round communication complexity.

Let suc_r(\mu,f,C) denote the maximum success probability of an r-round communication protocol that uses

at most C bits of communication in computing f(x,y) when (x,y)~\mu.

Jain et al. [JPY12] have recently showed that if

more >>>

Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff

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 f(x,y) with C bits of communication, when the inputs (x,y) are ... more >>>

Avi Wigderson, Amir Yehudayoff

We study several problems in which an {\em unknown} distribution over an {\em 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 \subseteq \{0,1\}^n$. A ... more >>>

Pavel Hrubes, Amir Yehudayoff

We give an example of a non-commutative monotone 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 ... more >>>

Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff

We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call \emph{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 ... more >>>

Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff

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 ... more >>>

Boaz Barak, Zeev Dvir, Avi Wigderson, Amir Yehudayoff

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 ... more >>>

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

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 ...
more >>>

Mark Braverman, Anup Rao, Ran Raz, Amir Yehudayoff

We give new pseudorandom generators for \emph{regular} read-once branching programs of small width.

A branching program is regular if the in-degree of every vertex in it is (0 or) $2$.

For every width $d$ and length $n$,

our pseudorandom generator uses a seed of length $O((\log d + \log\log n ...
more >>>

Pavel Hrubes, Avi Wigderson, Amir Yehudayoff

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 \emph{non-commutative} arithmetic circuits and a problem about \emph{commutative} degree four polynomials, the classical sum-of-squares problem: find the smallest $n$ such that ... more >>>

Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff

Bogdanov and Viola (FOCS 2007) constructed a pseudorandom

generator that fools degree $k$ polynomials over $\F_2$ for an arbitrary

constant $k$. We show that such generators can also be used to fool branching programs of width 2 and polynomial length that read $k$ bits of inputs at a

time. This ...
more >>>

Ran Raz, Amir Yehudayoff

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$ ... more >>>

Zeev Dvir, Amir Shpilka, Amir Yehudayoff

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(x_1,...,x_m) that cannot be computed by a depth d arithmetic circuit of small size then there exists ... more >>>

Ran Raz, Amir Yehudayoff

We study multilinear formulas, monotone arithmetic circuits, maximal-partition discrepancy, best-partition communication complexity and extractors constructions. We start by proving lower bounds for an explicit polynomial for the following three subclasses of syntactically multilinear arithmetic formulas over the field C and the set of variables {x1,...,xn}:

1. Noise-resistant. A syntactically multilinear ... more >>>

Ran Raz, Amir Shpilka, Amir Yehudayoff

We construct an explicit polynomial $f(x_1,...,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^2(n) )$. The lower bound holds over any field.