All reports by Author Shay Moran:

__
TR23-002
| 5th January 2023
__

Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran#### Diagonalization Games

Revisions: 2

__
TR22-035
| 7th March 2022
__

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

__
TR18-074
| 23rd April 2018
__

Daniel Kane, Shachar Lovett, Shay Moran#### Generalized comparison trees for point-location problems

__
TR17-177
| 16th November 2017
__

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

Revisions: 1

__
TR17-085
| 4th May 2017
__

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang#### Active classification with comparison queries

__
TR17-082
| 4th May 2017
__

Daniel Kane, Shachar Lovett, Shay Moran#### Near-optimal linear decision trees for k-SUM and related problems

__
TR15-189
| 25th November 2015
__

Shay Moran, Cyrus Rashtchian#### Shattered Sets and the Hilbert Function

Revisions: 2

__
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-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

__
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

Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran

We study several variants of a combinatorial game which is based on Cantor's diagonal argument. The game is between two players called Kronecker and Cantor. The names of the players are motivated by the known fact that Leopold Kronecker did not appreciate Georg Cantor's arguments about the infinite, and even ... 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 >>>

Daniel Kane, Shachar Lovett, Shay Moran

Let $H$ be an arbitrary family of hyper-planes in $d$-dimensions. We show that the point-location problem for $H$

can be solved by a linear decision tree that only uses a special type of queries called \emph{generalized comparison queries}. These queries correspond to hyperplanes that can be written as a linear ...
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 >>>

Daniel Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang

We study an extension of active learning in which the learning algorithm may ask the annotator to compare the distances of two examples from the boundary of their label-class. For example, in a recommendation system application (say for restaurants), the annotator may be asked whether she liked or disliked a ... more >>>

Daniel Kane, Shachar Lovett, Shay Moran

We construct near optimal linear decision trees for a variety of decision problems in combinatorics and discrete geometry.

For example, for any constant $k$, we construct linear decision trees that solve the $k$-SUM problem on $n$ elements using $O(n \log^2 n)$ linear queries.

Moreover, the queries we use are comparison ...
more >>>

Shay Moran, Cyrus Rashtchian

We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions. Our main complexity-theoretic result proves that most linear program feasibility problems cannot be computed by polynomial-sized constant-depth circuits. Moreover, our result ... 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 >>>

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

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