Hardness of edge-modification problems (2009)
For a graph property P consider the following computational problem. Given an input graph G, what is the minimum number of edge modifications (additions and/or deletions) that one has to apply to G...
The maximum edit distance from hereditary graph properties (2008)
For a graph property P, the edit distance of a graph G from P, denoted EP(G), is the minimum number of edge modifications (additions or deletions) one needs to apply to G in order to turn it into a...
Can a Graph Have Distinct Regular Partitions? ∗ (2008)
Noga Alon, Asaf Shapira, Uri Stav
The regularity lemma of Szemerédi gives a concise approximate description of a graph via a so called regular partition of its vertex set. In this paper we address the following problem: can a graph...
Can a Graph Have Distinct Regular Partitions? ∗ (2008)
Noga Alon, Asaf Shapira, Uri Stav
The regularity lemma of Szemerédi gives a concise approximate description of a graph via a so called regular-partition of its vertex set. In this paper we address the following problem: can a graph...
Broadcasting with side information (2008)
Alon, Noga, Hasidim, Avinatan, Lubetzky, Eyal, Stav, Uri, Weinstein, Amit
A sender holds a word x consisting of n blocks x_i, each of t bits, and wishes to broadcast a codeword to m receivers, R_1,...,R_m. Each receiver R_i is interested in one block, and has prior side...
Non-linear index coding outperforming the linear optimum (2008)
The following source coding problem was introduced by Birk and Kol: a sender holds a word $x\in\{0,1\}^n$, and wishes to broadcast a codeword to $n$ receivers, $R_1,...,R_n$. The receiver $R_i$ is...
Can a Graph Have Distinct Regular Partitions? ∗ (2008)
Noga Alon, Asaf Shapira, Uri Stav
The regularity lemma of Szemerédi gives a concise approximate description of a graph via a so called regular-partition of its vertex set. In this paper we address the following problem: can a graph...
Stability type results for hereditary properties (2007)
The classical Stability Theorem of Erdős and Simonovits can be stated as follows. For a monotone graph property P, let t ≥ 2 be such that t + 1 = min{χ(H) : H / ∈ P}. Then any edges from graph...
What is the furthest graph from a hereditary property? (2006)
For a graph property P, the edit distance of a graph G from P, denoted EP(G), is the minimum number of edge modifications (additions or deletions) one needs to apply to G in order to turn it into a...