All reports by Author Noga Alon:

__
TR23-002
| 5th January 2023
__

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

Revisions: 2

__
TR16-086
| 29th May 2016
__

Noga Alon, Klim Efremenko, Benny Sudakov#### Testing Equality in Communication Graphs

Revisions: 1

__
TR15-054
| 7th April 2015
__

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein#### Welfare Maximization with Limited Interaction

__
TR15-014
| 18th January 2015
__

Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler#### Reliable Communication over Highly Connected Noisy Networks

__
TR14-135
| 23rd October 2014
__

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

Revisions: 2

__
TR12-169
| 22nd November 2012
__

Noga Alon, Santosh Vempala#### The Approximate Rank of a Matrix and its Algorithmic Applications

Revisions: 2

__
TR12-133
| 21st October 2012
__

Noga Alon, Gil Cohen#### On Rigid Matrices and Subspace Polynomials

Revisions: 1

__
TR11-067
| 25th April 2011
__

Noga Alon, Amir Shpilka, Chris Umans#### On Sunflowers and Matrix Multiplication

Comments: 1

__
TR11-049
| 9th April 2011
__

Noga Alon, Shachar Lovett#### Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions

__
TR09-012
| 4th February 2009
__

Noga Alon, Shai Gutner#### Balanced Hashing, Color Coding and Approximate Counting

__
TR08-066
| 16th July 2008
__

Noga Alon, Shai Gutner#### Kernels for the Dominating Set Problem on Graphs with an Excluded Minor

Revisions: 1

__
TR08-065
| 11th July 2008
__

Noga Alon, Rina Panigrahy, Sergey Yekhanin#### Deterministic Approximation Algorithms for the Nearest Codeword Problem

__
TR06-119
| 13th September 2006
__

Noga Alon, Oded Schwartz, Asaf Shapira#### An Elementary Construction of Constant-Degree Expanders

__
TR05-095
| 26th August 2005
__

Noga Alon, Ilan Newman, Alexander Shen, GĂˇbor Tardos, Nikolay Vereshchagin#### Partitioning multi-dimensional sets in a small number of ``uniform'' parts

__
TR05-085
| 5th August 2005
__

Asaf Shapira, Noga Alon#### Homomorphisms in Graph Property Testing - A Survey

__
TR02-048
| 31st July 2002
__

Noga Alon, Oded Goldreich, Yishay Mansour#### Almost $k$-wise independence versus $k$-wise independence

__
TR01-100
| 14th December 2001
__

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski#### Random Sampling and Approximation of MAX-CSP Problems

__
TR94-009
| 12th December 1994
__

Noga Alon, Raphael Yuster, Uri Zwick#### Color-coding

__
TR94-005
| 12th December 1994
__

Noga Alon, Alan Frieze, Dominic Welsh#### Polynomial time randomised approximation schemes for Tutte-Gr\"{o}thendieck invariants: the dense case

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

Noga Alon, Klim Efremenko, Benny Sudakov

Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose

that on each vertex of the graph there is a player having an $n$-bit

string. Each player is allowed to communicate with its neighbors according

to an agreed communication protocol, and the players must decide,

deterministically, if their inputs ...
more >>>

Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein

We continue the study of welfare maximization in unit-demand (matching) markets, in a distributed information model

where agent's valuations are unknown to the central planner, and therefore communication is required to determine an

efficient allocation. Dobzinski, Nisan and Oren (STOC'14) showed that if the market size is $n$, ...
more >>>

Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

We consider the task of multiparty computation performed over networks in

the presence of random noise. Given an $n$-party protocol that takes $R$

rounds assuming noiseless communication, the goal is to find a coding

scheme that takes $R'$ rounds and computes the same function with high

probability even when the ...
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 >>>

Noga Alon, Santosh Vempala

We introduce and study the \epsilon-rank of a real matrix A, defi ned, for any \epsilon > 0 as the minimum rank over matrices that approximate every entry of A to within an additive \epsilon. This parameter is connected to other notions of approximate rank and is motivated by ... more >>>

Noga Alon, Gil Cohen

We introduce a class of polynomials, which we call \emph{subspace polynomials} and show that the problem of explicitly constructing a rigid matrix can be reduced to the problem of explicitly constructing a small hitting set for this class. We prove that small-bias sets are hitting sets for the class of ... more >>>

Noga Alon, Amir Shpilka, Chris Umans

We present several variants of the sunflower conjecture of Erd\H{o}s and Rado and discuss the relations among them.

We then show that two of these conjectures (if true) imply negative answers to questions of Coppersmith and Winograd and Cohn et al. regarding possible approaches for obtaining fast matrix multiplication algorithms. ... more >>>

Noga Alon, Shachar Lovett

A family of permutations in $S_n$ is $k$-wise independent if a uniform permutation chosen from the family maps any distinct $k$ elements to any distinct $k$ elements equally likely. Efficient constructions of $k$-wise independent permutations are known for $k=2$ and $k=3$, but are unknown for $k \ge 4$. In fact, ... more >>>

Noga Alon, Shai Gutner

Color Coding is an algorithmic technique for deciding efficiently

if a given input graph contains a path of a given length (or

another small subgraph of constant tree-width). Applications of the

method in computational biology motivate the study of similar

algorithms for counting the number of copies of a ...
more >>>

Noga Alon, Shai Gutner

The domination number of a graph $G=(V,E)$ is the minimum size of

a dominating set $U \subseteq V$, which satisfies that every

vertex in $V \setminus U$ is adjacent to at least one vertex in

$U$. The notion of a problem kernel refers to a polynomial time

algorithm that achieves ...
more >>>

Noga Alon, Rina Panigrahy, Sergey Yekhanin

The Nearest Codeword Problem (NCP) is a basic algorithmic question in the theory of error-correcting codes. Given a point v in an n-dimensional space over F_2 and a linear subspace L in F_2^n of dimension k NCP asks to find a point l in L that minimizes the (Hamming) distance ... more >>>

Noga Alon, Oded Schwartz, Asaf Shapira

We describe a short and easy to analyze construction of

constant-degree expanders. The construction relies on the

replacement-product, which we analyze using an elementary

combinatorial argument. The construction applies the replacement

product (only twice!) to turn the Cayley expanders of \cite{AR},

whose degree is polylog n, into constant degree

expanders.

Noga Alon, Ilan Newman, Alexander Shen, GĂˇbor Tardos, Nikolay Vereshchagin

Our main result implies the following easily formulated statement. The set of edges E of every finite bipartite graph can be split into poly(log |E|) subsets so the all the resulting bipartite graphcs are almost regular. The latter means that the ratio between the maximal and minimal non-zero degree of ... more >>>

Asaf Shapira, Noga Alon

Property-testers are fast randomized algorithms for distinguishing

between graphs (and other combinatorial structures) satisfying a

certain property, from those that are far from satisfying it. In

many cases one can design property-testers whose running time is in

fact {\em independent} of the size of the input. In this paper we

more >>>

Noga Alon, Oded Goldreich, Yishay Mansour

We say that a distribution over $\{0,1\}^n$

is almost $k$-wise independent

if its restriction to every $k$ coordinates results in a

distribution that is close to the uniform distribution.

A natural question regarding almost $k$-wise independent

distributions is how close they are to some $k$-wise

independent distribution. We show ...
more >>>

Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

We present a new efficient sampling method for approximating

r-dimensional Maximum Constraint Satisfaction Problems, MAX-rCSP, on

n variables up to an additive error \epsilon n^r.We prove a new

general paradigm in that it suffices, for a given set of constraints,

to pick a small uniformly random ...
more >>>

Noga Alon, Raphael Yuster, Uri Zwick

We describe a novel randomized method, the method of

{\em color-coding\/} for finding simple paths and cycles of a specified

length $k$, and other small subgraphs, within a given graph $G=(V,E)$.

The randomized algorithms obtained using this method can be

derandomized using families of {\em perfect hash functions\/}. ...
more >>>

Noga Alon, Alan Frieze, Dominic Welsh

The Tutte-Gr\"othendieck polynomial $T(G;x,y)$ of a graph $G$

encodes numerous interesting combinatorial quantities associated

with the graph. Its evaluation in various points in the $(x,y)$

plane give the number of spanning forests of the graph, the number

of its strongly connected orientations, the number of its proper

$k$-colorings, the (all ...
more >>>