Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Noga Alon:

TR16-086 | 29th May 2016
Noga Alon, Klim Efremenko, Benny Sudakov

Testing Equality in Communication Graphs

Revisions: 1

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

TR15-054 | 7th April 2015
Noga Alon, Noam Nisan, Ran Raz, Omri Weinstein

Welfare Maximization with Limited Interaction

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

TR15-014 | 18th January 2015
Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, Bernhard Haeupler

Reliable Communication over Highly Connected Noisy Networks

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

TR14-135 | 23rd October 2014
Noga Alon, Shay Moran, Amir Yehudayoff

Sign rank, VC dimension and spectral gaps

Revisions: 2

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

TR12-169 | 22nd November 2012
Noga Alon, Santosh Vempala

The Approximate Rank of a Matrix and its Algorithmic Applications

Revisions: 2

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

TR12-133 | 21st October 2012
Noga Alon, Gil Cohen

On Rigid Matrices and Subspace Polynomials

Revisions: 1

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

TR11-067 | 25th April 2011
Noga Alon, Amir Shpilka, Chris Umans

On Sunflowers and Matrix Multiplication

Comments: 1

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

TR11-049 | 9th April 2011
Noga Alon, Shachar Lovett

Almost k-wise vs. k-wise independent permutations, and uniformity for general group actions

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

TR09-012 | 4th February 2009
Noga Alon, Shai Gutner

Balanced Hashing, Color Coding and Approximate Counting

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

TR08-066 | 16th July 2008
Noga Alon, Shai Gutner

Kernels for the Dominating Set Problem on Graphs with an Excluded Minor

Revisions: 1

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

TR08-065 | 11th July 2008
Noga Alon, Rina Panigrahy, Sergey Yekhanin

Deterministic Approximation Algorithms for the Nearest Codeword Problem

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

TR06-119 | 13th September 2006
Noga Alon, Oded Schwartz, Asaf Shapira

An Elementary Construction of Constant-Degree Expanders

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

... more >>>

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

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

TR05-085 | 5th August 2005
Asaf Shapira, Noga Alon

Homomorphisms in Graph Property Testing - A Survey

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

TR02-048 | 31st July 2002
Noga Alon, Oded Goldreich, Yishay Mansour

Almost $k$-wise independence versus $k$-wise independence

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

TR01-100 | 14th December 2001
Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski

Random Sampling and Approximation of MAX-CSP Problems

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

TR94-009 | 12th December 1994
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 >>>

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

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

ISSN 1433-8092 | Imprint