Testing Reed Muller Codes ∗ (2009)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector’s bits. We show that...
Noga Alon, Daniel Lokshtanov, Saket Saurabh
Abstract. We present a randomized subexponential time, polynomial space parameterized algorithm for the k-Weighted Feedback Arc Set in Tournaments (k-FAST) problem. We also show that our algorithm...
Abstract. In the Maximum Subset Matching problem, which generalizes the maximum matching problem, we are given a graph G = (V, E) and S ⊂ V. The goal is to determine the maximum number of vertices...
Typical Peak Sidelobe Level of Binary Sequences (2009)
Noga Alon, Simon Litsyn, Er Shpunt
Abstract. For a binary sequence Sn = {si: i = 1, 2,..., n} ∈ {±1} n, n> 1, the peak sidelobe level (PSL) is defined as M(Sn) = max k=1,2,...,n−1 | n−k ∑ sisi+k|. i=1 It is shown that the...
Noga Alon, Haim Kaplan, Gabriel Nivasch, Shakhar Smorodinsky
Abstract. We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1-nets of size O(rα(r)), where...
STABLE KNESER HYPERGRAPHS AND IDEALS IN N WITH THE NIKOD ´YM PROPERTY (2009)
Noga Alon, Lech Drewnowski, Tomasz ̷luczak
Abstract. We use stable Kneser hypergraphs to construct ideals in N which are not nonatomic yet have the Nikod´ym property. 1.
Biomolecular Network Motif Counting and Discovery by Color Coding (2009)
Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, S. Cenk Sahinalp
Protein protein interaction (PPI) networks of many organisms share global topological features such as degree distribution, k − hop reachability, betweenness and closeness. Yet some of these...
The Complexity of the Outer Face in Arrangements of Random Segments ∗ (2009)
Noga Alon, Dan Halperin, Oren Nechushtan, Micha Sharir
We investigate the complexity of the outer face in arrangements of line segments of a fixed length ℓ in the plane, drawn uniformly at random within a square. We derive upper bounds on the expected...
Noga Alon, Ido Ben-eliezer, Michael Krivelevich
sample spaces cannot fool low degree polynomials
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...
Balanced Hashing, Color Coding and Approximate Counting (Extended Abstract) (2009)
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...
The inverse Banzhaf problem (2009)
Let F be a family of subsets of the ground set [n] = {1, 2,..., n}. For each i ∈ [n] we let p(F, i) be the number of pairs of subsets that differ in the element i and exactly one of them is in F....
Many Random Walks Are Faster Than One (2009)
Noga Alon, Chen Avin, Gady Kozma, Zvi Lotker, Mark R. Tuttle
We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex,...
Sum of Us: Strategyproof Selection from the Selectors (2009)
Alon, Noga, Fischer, Felix, Procaccia, Ariel D., Tennenholtz, Moshe
We consider directed graphs over a set of n agents, where an edge (i,j) is taken to mean that agent i supports or trusts agent j. Given such a graph and an integer k\leq n, we wish to select a subset...
Spanning directed trees with many leaves (2009)
Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh
Abstract. The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we...
The structure of almost all graphs in a hereditary property (2009)
Alon, Noga, Balogh, Jozsef, Bollobas, Bela, Morris, Robert
A hereditary property of graphs is a collection of graphs which is closed under taking induced subgraphs. The speed of \P is the function n \mapsto |\P_n|, where \P_n denotes the graphs of order n in...
Sums and products along sparse graphs (2009)
Alon, Noga, Angel, Omer, Benjamini, Itai, Lubetzky, Eyal
In their seminal paper from 1983, Erd\H{o}s and Szemer\'edi showed that any $n$ distinct integers induce either $n^{1+\epsilon}$ distinct sums of pairs or that many distinct products, and conjectured...
Embedding nearly-spanning bounded degree trees (2009)
Noga Alon, Michael Krivelevich, Benny Sudakov
We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of atreeT of maximum degree at most d on (1 − ɛ)n vertices, in terms of the expansion properties of G. As a...
Discrete Kakeya-type problems and small bases (2009)
Noga Alon, Boris Bukh, Benny Sudakov
A subset U of a group G is called k-universal if U contains a translate of every k-element subset of G. We give several nearly optimal constructions of small k-universal sets, and use them to resolve...
Computing Sciences Universiteit Utrecht (2009)
Noga Alon, Maike Buchin, Bettina Speckmann, Tu Eindhoven, Robert Berke, Péter Csorba, ...
We show that the vertices of any plane graph in which every face is of size at least g can be colored by ⌊(3g − 5)/4⌋ colors so that every color appears in every face. This is nearly tight, as...
LARGE NEARLY REGULAR INDUCED SUBGRAPHS ∗ (2009)
Noga Alon, Michael Krivelevich, Benny Sudakov
Abstract. For a real c ≥ 1 and an integer n, let f(n, c) denote the maximum integer f such that every graph on n vertices contains an induced subgraph on at least f vertices in which the maximum...
Spanning directed trees with many leaves (2009)
Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh
The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we obtain two...
Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions ⋆ (2009)
Noga Alon, Amin Coja-oghlan, Hiê. P Hàn, Mihyun Kang, Vojtěch Rödl, Mathias Schacht
Abstract. We deal with two intimately related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to measure how much a given graph “resembles ” a...
For a graph G whose number of edges is divisible by k, let R(G, Zk) denote the minimum integer r such that for every function f: E(Kr) ↦ → Zk there is a copy G ′ of G in Kr so that e∈E(G ′...
Problems and results in extremal combinatorics, part i (2009)
Extremal Combinatorics is an area in Discrete Mathematics that has developed spectacularly during the last decades. This paper contains a collection of problems and results in the area, including...
H-free graphs of large minimum degree (2009)
We prove the following extension of an old result of Andrásfai, Erdős and Sós. For every fixed graph H with chromatic number r + 1 ≥ 3, and for every fixed ɛ> 0, there are n0 = n0(H, ɛ) and...
MaxCut in H-free graphs (2009)
Noga Alon, Michael Krivelevich, Benny Sudakov
For a graph G, let f(G) denote the maximum number of edges in a cut of G. For an integer m and for a fixed graph H, let f(m, H) denote the minimum possible cardinality of f(G), as G ranges over all...
Choice-memory tradeoff in allocations (2009)
Alon, Noga, Gurel-Gurevich, Ori, Lubetzky, Eyal
In the classical balls-and-bins paradigm, where n balls are placed independently and uniformly in n bins, typically the number of bins with at least two balls in them has order n and the maximum...
On the power of two, three, and four probes (2009)
An adaptive (n, m, s, t)-scheme is a deterministic scheme for encoding a vector X of m bits with at most n ones by a vector Y of s bits, so that any bit of X can be determined by t adaptive probes to...
A note on regular Ramsey graphs (2009)
Noga Alon, Sonny Ben-shimon, Michael Krivelevich
We prove that there is an absolute constant C> 0 so that for every natural n there exists a trianglefree regular graph with no independent set of size at least C √ n log n. 1
Optimal Monotone Encodings (2008)
Moran, Naor and Segev have asked what is the minimal r = r(n, k) for which there exists an (n, k)-monotone encoding of length r, i.e., a monotone injective function from subsets of size up to k of...
SIAM Journal on Computing, 2(1):1-6, March 1973. (2008)
Dimitris Achlioptas, Sheldon B. Akers, Noga Alon
[3] E. A. Akkoyunlu. The enumeration of maximal cliques of large graphs.
Abstract On the Complexity of Radio Communication (Extended Abstract) (2008)
Noga Alon, Amotz Bar-noy, Nathan Linial, David Peleg
A radio network is a synchronous network of processors that communicate by transmitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then...
: www.idealibrary.com on The Space Complexity of Approximating the Frequency Moments* (2008)
Noga Alon, Yossi Matias, Mario Szegedy
The frequency moments of a sequence containing mi elements of type i, 1 i n, are the numbers Fk = n i=1 m k i. We consider the space complexity of randomized algorithms that approximate the numbers...
Codes and Xor graph products (2008)
What is the maximum possible number, f3(n), of vectors of length n over {0, 1, 2} such that the Hamming distance between every two is even? What is the maximum possible number, g3(n), of vectors in...
Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs (2008)
Abstract. There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a k O(dk) n time algorithm for...
Typechecking XML Views of Relational Databases ∗ Abstract (2008)
Noga Alon, Tova Milo, Dan Suciu
Motivated by the need to export relational databases as XML data in the context of the Web, we investigate the typechecking problem for transformations of relational data into tree data (XML). The...
Noga Alon, Béla Bollobás, Jeong Han, Kim Van, H. Vu
covers with geometric applications
Noga Alon, Melvyn B. Nathanson, Imre Z. Ruzsa
polynomial method and restricted sums of congruence classes ∗
A note on regular Ramsey graphs (2008)
Alon, Noga, Ben-Shimon, Sonny, Krivelevich, Michael
We prove that there is an absolute constant $C>0$ so that for every natural $n$ there exists a triangle-free \emph{regular} graph with no independent set of size at least $C\sqrt{n\log n}$.
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...
Economical coverings of sets of lattice points (2008)
Let t(n, d) be the minimum number t such that there are t of the n d lattice points {(x1,..., xd) : 1 ≤ xi ≤ n} so that the � � t d 2 lines that they determine cover all the above n lattice...
Testing low-degree polynomials over GF(2) (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
Abstract. We describe an efficient randomized algorithm to test if a given binary function � � ����� � � ���� � is a low-degree polynomial (that is, a sum of low-degree...
Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions ⋆ (2008)
Noga Alon, Amin Coja-oghlan, Hiê. P Hàn, Mihyun Kang, Vojtěch Rödl, Mathias Schacht
Abstract. We deal with two intimately related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to measure how much a given graph “resembles ” a...
Constructive Lower Bounds for off-diagonal Ramsey Numbers (2008)
We describe an explicit construction which, for some fixed absolute positive constant ε, produces, for every integer s> 1 and all sufficiently large m, a graph on at least m ε √ log s / log...
Discrete Kakeya-type problems and small bases (2008)
Noga Alon, Boris Bukh, Benny Sudakov
A subset U of a group G is called k-universal if U contains a translate of every k-element subset of G. We give several nearly optimal constructions of small k-universal sets, and use them to resolve...
Spanning directed trees with many leaves ⋆ (2008)
Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh
Abstract. The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we...
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...
Equilateral sets in l n p (2008)
We show that for every odd integer p ≥ 1 there is an absolute positive constant cp, so that the maximum cardinality of a set of vectors in R n such that the lp distance between any pair is...
Balanced Families of Perfect Hash Functions and Their Applications (2008)
Abstract. The construction of perfect hash functions is a well-studied topic. In this paper, this concept is generalized with the following definition. We say that a family of functions from [n]...
Noga Alon, Nicolò Cesa-bianchi, Shai Ben-david, David Haussler
Learnability in Valiant’s PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property of...
Noga Alon, Itai Benjamini, Alan Stacey
on finite graphs and isoperimetric inequalities
A Ramsey-type result for the hypercube (2008)
Noga Alon, Benny Sudakov, Jan Vondrák
We prove that for every fixed k and ℓ ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Qn with k colors contains a monochromatic cycle of length 2ℓ. This answers an open...
High degree graphs contain large-star factors (2008)
We show that any finite simple graph with minimum degree $d$ contains a spanning star forest in which every connected component is of size at least $\Omega((d/\log d)^{1/3})$. This settles a problem...
Economical toric spines via Cheeger's Inequality (2008)
Let $G_{\infty}=(C_m^d)_{\infty}$ denote the graph whose set of vertices is $\{1,..., m\}^d$, where two distinct vertices are adjacent iff they are either equal or adjacent in $C_m$ in each...
How to color shift hypergraphs (2008)
Noga Alon, Igor Kriz, Jaroslav Neˇsetˇril
Let g(k) denote the minimum integer m so that for every set S of m integers there is a k-coloring of the set of all integers so that every translate of S meets every color class. It is a well known...
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...
A separation theorem in property testing (2008)
Consider the following seemingly rhetorical question: Is it crucial for a property-tester to know the error parameter ɛ in advance? Previous papers dealing with various testing problems, suggest...
The edge-integrity of a graph G is I ′ (G): = min{|S | + m(G − S) : S ⊂ E}, where m(H) denotes the maximum order of a component of H. A graph G is called honest if its edge-integrity is the...
Noga Alon, Béla Bollobás, Jeong Han, Kim Van, H. Vu
covers with geometric applications
A Ramsey-type result for the hypercube (2008)
Noga Alon, Benny Sudakov, Jan Vondrák
We prove that for every fixed k and ℓ ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Qn with k colors contains a monochromatic cycle of length 2ℓ. This answers an open...
The Grothendieck constant of random and pseudo-random graphs. Discrete Optimization (2008)
The Grothendieck constant of a graph G = (V, E) is the least constant K such that for every matrix A: V × V → R:
Progressions in Sequences of Nearly Consecutive Integers (2008)
For k> 2 and r ≥ 2, let G(k, r) denote the smallest positive integer g such that every increasing sequence of g integers {a1, a2,..., ag} with gaps aj+1 − aj ∈ {1,..., r}, 1 ≤ j ≤ g −...
1 Introduction Poker, Chance and Skill (2008)
The question if poker is a game of skill or a game of chance received a considerable amount of attention mainly because of its potential legal implications. See, for example, [3] and
PROBLEM SECTION Splitting digraphs (2008)
There are several known results asserting that undirected graphs can be partitioned in a way that satisfies various imposed constrains on the degrees. The corresponding results for directed graphs,...
Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions (2008)
Noga Alon, Amin Coja-oghlan, Hiê. P Hàn, Mihyun Kang, Vojtěch Rödl, Mathias Schacht
Abstract. We deal with two very related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to measure how much a given graph “resembles ” a...
Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs (2008)
There is substantial literature dealing with fixed parameter algorithms for the dominating set problem on various families of graphs. In this paper, we give a $k^{O(dk)} n$ time algorithm for finding...
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...
Balanced Families of Perfect Hash Functions and Their Applications (2008)
The construction of perfect hash functions is a well-studied topic. In this paper, this concept is generalized with the following definition. We say that a family of functions from $[n]$ to $[k]$ is...
k-Wise Independent Random Graphs (2008)
We study the k-wise independent relaxation of the usual model G(N,p) of random graphs where, as in this model, N labeled vertices are fixed and each edge is drawn with probability p, however, it is...
On (ε, k)-min-wise independent permutations (2008)
Noga Alon, Toshiya Itoh, Tatsuya Nagatani
A family of permutations F of [n] = {1, 2,..., n} is (ε, k)-min-wise independent if for every nonempty subset X of at most k elements of [n], and for any x ∈ X, the probability that in a random...
Partitioning multi-dimensional sets in a small number of “uniform ” parts (2008)
Noga Alon, Ilan Newman Alex, Er Shen, Gábor Tardos, Nikolai 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 that all the resulting bipartite...
Noga Alon, Michael Krivelevich, Joel Spencer, Tibor Szabó
We investigate a game played on a hypergraph H = (V,E) bytwoplayers, Balancer and Unbalancer. They select one element of the vertex set V alternately until all vertices are selected. Balancer wins if...
Abstract Matching nuts and bolts (Extended Abstract) (2008)
Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky
We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of bolts and nuts and wants to find the corresponding pairs of bolts and nuts. The procedure uses our...
Abstract Tell Me Who I Am: An Interactive Recommendation System Extended Abstract (2008)
Noga Alon, Baruch Awerbuch, Johns Hopkins U
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
It is shown that the minimum possible number of edges in an n- superconcentrator of depth 3 is Θ(n log log n), whereas the minimum possible number of edges in an n-superconcentrator of depth 2 is...
Edge Coloring with Delays (2008)
Consider the following communication problem, that leads to a new notion of edge coloring. The communication network is represented by a bipartite multigraph, where the nodes on one side are the...
Quasi-Randomness and Algorithmic Regularity for Graphs with General Degree Distributions (2008)
Noga Alon, Amin Coja-oghlan, Hiê. P Hàn, Mihyun Kang, Vojtěch Rödl, Mathias Schacht
Abstract. We deal with two intimately related subjects: quasi-randomness and regular partitions. The purpose of the concept of quasi-randomness is to measure how much a given graph “resembles ” a...
Noga Alon, Michael Krivelevich, Benny Sudakov
coloring of random and pseudo-random graphs
Turán’s theorem in the hypercube (2008)
Noga Alon, Anja Krech, Tibor Szabó
We are motivated by the analogue of Turán’s theorem in the hypercube Qn: how many edges can a Qd-free subgraph of Qn have? We study this question through its Ramsey-type variant and obtain...
A family of sets has the (p, q) property if among any p members of the family some q have a nonempty intersection. It is shown that for every p ≥ q ≥ d + 1 there is a c = c(p, q, d) < ∞ such...
1 Sparse Universal Graphs for General Max-degree 3 Graphs (2008)
Ofer Arieli, Arnon Avron, Noga Alon, Vera Asodi
In this paper we develop frameworks for logical systems which are able to reflect not only nonmonotonic patterns of reasoning, but also paraconsistent reasoning. For this we consider a sequence of...
Independent sets in tensor graph powers (2008)
The tensor product of two graphs, G and H, has a vertex set V (G) × V (H) and an edge between (u, v) and (u ′ , v ′ ) iff both uu ′ ∈ E(G) and vv ′ ∈ E(H). Let A(G) denote the limit of...
Noga Alon, Sloan Foundation, Raphy Yuster, Uri Zwick
We describe a novel randomized method, the method of 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...
Admission control to minimize rejections and online set cover with repetitions (2008)
We study the admission control problem in general networks. Communication requests arrive over time, and the online algorithm accepts or rejects each request while maintaining the capacity...
Derandomization via small sample spaces (2008)
Many randomized algorithms run successfully even when the random choices they utilize are not fully independent. For the analysis some limited amount of independence, like k-wise independence for...
Abstract A parallel algorithmic version of the Local Lemma (2008)
The Lovász Local Lemma is a tool that enables one to show that certain events hold with positive, though very small probability. It often yields existence proofs of results without supplying any...
Tel Aviv ∗ Abstract W. Fernandez de la Vega (2008)
Noga Alon, Marek Karpinski, Ravi Kannan
We present a new efficient sampling method for approximating
Edge Coloring with Delays ∗ (2008)
Consider the following communication problem, that leads to a new notion of edge coloring. The communication network is represented by a bipartite multigraph, where the nodes on one side are the...
Maximum directed cuts in acyclic digraphs (2008)
Noga Alon, Béla Bollobás, András Gyárfás, Jenő Lehel, Alex Scott
It is easily shown that every digraph with m edges has a directed cut of size at least m/4, and that 1/4 cannot be replaced by any larger constant. We investigate the size of a largest directed cut...
NON-REPETITIVE COLORINGS OF GRAPHS (2008)
Abstract. A sequence a = a1a2...an is said to be non-repetitive if no two adjacent blocks of a are exactly the same. For instance the sequence 1232321 contains a repetition 2323, while 123132123213...
Given a set of nonnegative integers T, and a function S which assigns a set of integers S(v) to each vertex v of a graph G, an S-list T-coloring c of G is a vertexcoloring (with positive integers) of...
Additive Latin transversals (2008)
We prove that for every odd prime p, every k ≤ p and every two subsets A = {a1,..., ak} and B = {b1,..., bk} of cardinality k each of Zp, there is a permutation π ∈ Sk such that the sums ai + b...
ABSTRACT Every Monotone Graph Property is Testable (2008)
A graph property is called monotone if it is closed under taking (not necessarily induced) subgraphs (or, equivalently, if it is closed under removal of edges and vertices). Many monotone graph...
Testing low-degree polynomials over GF(2), booktitle (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
We describe an efficient randomized algorithm to test if a given binary function f: {0, 1} n → {0, 1} is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k ≥...
Noga Alon, Michael Krivelevich, Benny Sudakov
a large hidden clique in a random graph ∗
Amit Agarwal, Noga Alon, Moses Charikar
We present improved approximation algorithms for directed multicut and directed sparsest cut. The current best known approximation ratio for these problems is O(n 1/2). We obtain an...
All Boolean variables here range over the two element set {−1, 1}. Given n Boolean variables x1,..., xn, a non-monotone MAJORITY gate (in the variables xi) is a Boolean function whose value is the...
Algebraic and probabilistic methods in discrete mathematics (2008)
Combinatorics is an essential component of many mathematical areas, and its study has ex-prienced an impressive growth in recent years. This survey contains a discussion of two of the main general...
Edge-disjoint cycles in regular directed graphs (2008)
Noga Alon, Colin Mcdiarmid, Michael Molloy
We prove that any k-regular directed graph with no parallel edges contains a collection of at least Ω(k 2) edge-disjoint cycles, conjecture that in fact any such graph contains a collection of at...
Running head: Partitioning sets (2008)
Noga Alon, Ilan Newman Alex, Nikolai Vereshchagin
2 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 that all the resulting bipartite...
Codes and Xor graph products (2008)
What is the maximum possible number, f3(n), of vectors of length n over {0, 1, 2} such that the Hamming distance between every two is even? What is the maximum possible number, g3(n), of vectors in...
Probabilistic Proofs of Existence of Rare Events (2008)
In a typical probabilistic proof of a combinatorial result, one usually has to show that the probability of a certain event is positive. However, many of these proofs actually give more and show that...
Approximating the maximum clique minor and some (2008)
Noga Alon, Andrzej Lingas, Martin Wahlen
subgraph homeomorphism problems
Universality and tolerance (extended abstract (2008)
Noga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński, Endre Szemerédi
For any positive integers r and n, let H(r, n) denote the family of graphs on n vertices with maximum degree r, and let H(r, n, n) denote the family of bipartite graphs H on 2n vertices with n...
Fast algorithms for Maximum Subset Matching and All-Pairs Shortest Paths (2008)
in graphs with a (not so) small vertex cover
Noga Alon, Beverley Sackler, Charles J. Colbourn, Martin Tompa
U.S.A. In the manufacture of oligo arrays for DNA hybridization experiments, manufacturing defects must be detected and their position determined. The design of manufacturing protocols for such oligo...
Noga Alon, Nick Duffield, Carsten Lund, Mikkel Thorup
Suppose we have a large table T of items i, each with a weight wi, e.g., people and their salary. In a general preprocessing step for estimating arbitrary subset sums, we assign each item a random...
Nonrepetitive colorings of graphs (2008)
A vertex coloring of a graph G is k-nonrepetitive if one cannot find a periodic sequence with k blocks on any simple path of G. The minimum number of colors needed for such coloring is denoted by...
time has two-prover interactive protocols. Computational Complexity, 1:3–40, 1991. (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron Testing, László Babai, ...
[4] Sanjeev Arora, László Babai, Jacques Stern, and Z Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of
The Online Set Cover Problem (Extended Abstract) (2008)
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (seffi Naor
Let X = {1, 2,..., n} be a ground set of n elements, and let S be a family of subsets of X, |S | = m, with a positive cost cS associated with each S ∈ S. Consider the following online version of...
A Wiley-Interscience Publication (2008)
Noga Alon, Joel H. Spencer, John Wiley, To Nurit, Mary Ann
The Probabilistic Method has recently been developed intensively and became one of the most powerful and widely used tools applied in Combinatorics. One of the major reasons for this rapid...
Abstract Guessing Secrets Efficiently via List Decoding (Extended Abstract) (2008)
Noga Alon, Venkatesan Guruswami, Tali Kaufman, Madhu Sudan
We consider the guessing secrets problem defined by
Turán’s theorem in the hypercube (2008)
We are motivated by the analogue of Turán’s theorem in the hypercube Qn: how many edges can a Qd-free subgraph of Qn have. We study this question through its Ramsey-type variant and obtain...
Turán’s theorem in the hypercube (2008)
Noga Alon, Anja Krech, Tibor Szabó
We are motivated by the analogue of Turán’s theorem in the hypercube Qn: how many edges can a Qd-free subgraph of Qn have. We study this question through its Ramsey-type variant and obtain...
Abstract Testing Triangle-Freeness in General Graphs (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron
In this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are...
Noga Alon, Zvi Galil, Oded Margalit
The upper bound on the exponent, ω, of matrix multiplication over a ring that was three in 1968 has decreased several times and since 1986 it has been 2.376. On the other hand, the exponent of the...
Algorithmic aspects of acyclic edge colorings (2008)
A proper coloring of the edges of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a ′ (G), is the least number of colors in an...
Noga Alon, Bojan Mohar, Daniel P. S
⋆ This author’s research was supported in part by a United States Israeli BSF grant. ∗ This author’s research was supported by the Ministry of Research and Tech-
Sparse universal graphs for bounded-degree graphs (2008)
Let H be a family of graphs. A graph T is H-universal if it contains a copy of each H ∈ H as a subgraph. Let H(k, n) denote the family of graphs on n vertices with maximum degree at most k. 2 2 −...
Edge-disjoint cycles in regular directed graphs (2008)
Noga Alon, Colin Mcdiarmid, Michael Molloy
We prove that any k-regular directed graph with no parallel edges contains a collection of at least Ω(k 2) edge-disjoint cycles, conjecture that in fact any such graph contains a collection of at...
Extended Abstract Summary of results (2008)
Noga Alon, Zvi Galil, Oded Margalit, Moni Naor
The subcubic (O(n ω) for ω < 3) algorithms to multiply Boolean matrices do not provide the witnesses; namely, they compute C = AB but if Cij = 1 they do not find an index k (a witness) such that...
Universality and tolerance (extended abstract (2008)
Noga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński, Endre Szemerédi
For any positive ¦ integers § and, ¨� © ¦ � §� � let denote the family of graphs § on vertices with maximum degree, and let ¨� © ¦ � §� � §� � denote the family of...
Covering a hypergraph of subgraphs (2008)
Let G be a tree and let H be a collection of subgraphs of G, each having at most d connected components. Let ν(H) denote the maximum number of members of H no two of which share a common vertex, and...
A family of sets has the (p, q) property if among any p members of the family some q have a nonempty intersection. It is shown that for every p ≥ q ≥ d + 1 there is a c = c(p, q, d) < ∞ such...
Noga Alon, Michael Krivelevich, Joel Spencer, Tibor Szabó
We investigate a game played on a hypergraph H = (V, E) by two players, Balancer and Unbalancer. They select one element of the vertex set V alternately until all vertices are selected. Balancer wins...
Randomness and Pseudo-Randomness in Discrete Mathematics (2008)
Szele and others, that deterministic statements can be proved by probabilistic reasoning, led already in the first half of the century to several striking results in Analysis, Number Theory,...
Let H be a graph on h vertices, and let G be a graph on n vertices. An H-factor of G is a spanning subgraph of G consisting of n/h vertex disjoint copies of H. The fractional arboricity of H is a(H)...
Noga Alon, Jeong-han Kim, Joel Spencer
perfect matchings in regular simple hypergraphs
Abstract Tell Me Who I Am: An Interactive Recommendation System Extended Abstract (2008)
Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-shamir, Neumann Fund
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
A Ramsey-type result for the hypercube (2008)
Noga Alon, Benny Sudakov, Jan Vondrák
We prove that for every fixed k and ℓ ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Qn with k colors contains a monochromatic cycle of length 2ℓ. This answers an open...
Abstract Tracking Join and Self-Join Sizes in Limited Storage (2008)
Query optimizers rely on fast, high-quality estimates of result sizes in order to select between various join plans. Selfjoin sizes of relations provide bounds on the join size of any pairs of such...
Abstract Tracking Join and Self-Join Sizes in Limited Storage (2008)
Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy
gibbonsOresearch.bell-labs.com Query optimizers rely on fast, high-quality estimates of re-sult sizes in order to select between various join plans. Self-join sizes of relations provide bounds on the...
Noga Alon, Yossi Matias, Mario Szegedy
space complexity of approximating the frequency moments
Admission Control to Minimize Rejections and Online Set Cover with Repetitions (2008)
Alon, Noga, Azar, Yossi, Gutner, Shai
We study the admission control problem in general networks. Communication requests arrive over time, and the online algorithm accepts or rejects each request while maintaining the capacity...
The maximum number of perfect matchings in graphs with a given degree sequence (2008)
We show that the number of perfect matching in a simple graph $G$ with an even number of vertices and degree sequence $d_1,d_2, ..., d_n$ is at most $\prod_{i=1}^n (d_i !)^{\frac{1}{2d_i}}$. This...
Abstract Matching nuts and bolts (Extended Abstract) (2008)
Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan
We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of bolts and nuts and wants to nd the corresponding pairs of bolts and nuts. The procedure uses our...
Discrete Kakeya-type problems and small bases (2008)
Noga Alon, Boris Bukh, Benny Sudakov
A subset U of a group G is called k-universal if U contains a translate of every k-element subset of G. We give several nearly optimal constructions of small k-universal sets, and use them to resolve...
Categories and Subject Dcscriptors: G.l.O [Numerical Analysis]: General-parallel algontlznts: (2008)
Abstract. For any futed dimension d, the linear programming problem with IZ inequality con-straints can be solved on a probabilistic CRCW PRAM with O(n) processors almost surely in constant time. The...
A separation theorem in property testing (2008)
Consider the following seemingly rhetorical question: Is it crucial for a property-tester to know the error parameter ɛ in advance? Previous papers dealing with various testing problems, suggest...
Testing low-degree polynomials over (2008)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn
Abstract. We describe an efficient randomized algorithm to test if a given binary function is a low-degree polynomial (that is, a sum of low-degree monomials). For a ���� � given integer...
Noga Alon, Michael Krivelevich, Joel Spencer, Tibor Szabó
We investigate a game played on a hypergraph H = (V,E) by two players, Balancer and Unbalancer. They select one element of the vertex set V alternately until all vertices are selected. Balancer wins...
H-free graphs of large minimum degree (2008)
We prove the following extension of an old result of Andrásfai, Erdős and Sós. For every fixed graph H with chromatic number r +1 ≥ 3, and for every fixed ɛ>0, there are n0 = n0(H, ɛ) andρ...
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...
Admission control to minimize rejections and online set cover with repetitions (2008)
Noga Alon, Yossi Azar, Shai Gutner
Abstract We study the admission control problem in general networks. Communication requests arrive overtime, and the online algorithm accepts or rejects each request while maintaining the capacity...
A Ramsey-type result for the hypercube (2008)
Noga Alon, Benny Sudakov, Jan Vondrák
Abstract: We prove that for every fixed k and ℓ ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Qn with k colors contains a monochromatic cycle of length 2ℓ. This answers...
Spanning directed trees with many leaves (2008)
Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh
Abstract. The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we...
Noga Alon, Venkatesan Guruswami, Tali Kaufman
Madhu Sudan x Abstract We consider the guessing secrets problem defined by Chung, Graham, and Leighton [CGL01]. This is a variant of the standard 20 questions game where the player has a set of k? 1...
Approximate maximum parsimony and ancestral maximum likelihood (2008)
Noga Alon, Benny Chor, Fabio Pardi, Anat Rapoport
Abstract — We explore the maximum parsimony (MP) and ancestral maximum likelihood (AML) criteria in phylogenetic tree reconstruction. Both problems are NP hard, so we seek approximate solutions. We...
Noga Alon, Baruch Awerbuch, Johns Hopkins U, Yossi Azar, Boaz Patt-shamir
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
On the power of two, three and four probes (2008)
An adaptive (n, m, s, t)-scheme is a deterministic scheme for encoding a vector X of m bits with at most n ones by a vector Y of s bits, so that any bit of X can be determined by t adaptive probes to...
Biomolecular network motif counting and discovery by color coding (2008)
Alon, Noga, Dao, Phuong, Hajirasouliha, Iman, Hormozdiari, Fereydoun, Sahinalp, S. Cenk
Protein–protein interaction (PPI) networks of many organisms share global topological features such as degree distribution, k-hop reachability, betweenness and closeness. Yet, some of these...
Economical toric spines via cheeger’s inequality (2008)
Let G ∞ = (C d m) ∞ denote the graph whose set of vertices is {1,..., m} d, where two distinct vertices are adjacent iff they are either equal or adjacent in Cm in each coordinate. Let G1 = (C d...
Uniformly cross intersecting families (2008)
Let A and B denote two families of subsets of an n-element set. The pair (A, B) is said to be ℓ-cross-intersecting iff |A∩B | = ℓ for all A ∈ A and B ∈ B. Denote by Pℓ(n) the maximum...
Graphs with Integral Spectrum (2008)
Omran Ahmadi, Noga Alon, Ian F. Blake, Igor E. Shparlinski
It is shown that only a fraction of 2 −Ω(n) of the graphs on n vertices have an integral spectrum. Although there are several explicit constructions of such graphs, no upper bound for their...
Induced subgraphs with distinct sizes (2008)
We show that for every 0 < ɛ < 1/2, there is an n0 = n0(ɛ) such that if n> n0 then every n-vertex graph G of size at least ɛ ( ) () n n
The maximum number of perfect matchings in graphs with a given degree sequence (2008)
We show that the number of perfect matching in a simple graph G with an even number of vertices and degree sequence d1, d2,..., dn is at most ∏ 1 n i=1
Sizes of induced subgraphs of Ramsey graphs (2008)
Noga Alon, József Balogh, R Kostochka, Wojciech Samotij
An n-vertex graph G is c-Ramsey if it contains neither a complete nor an empty induced subgraph of size greater than c log n. Erdős, Faudree and Sós conjectured that every c-Ramsey graph with n...
A note on regular Ramsey graphs (2008)
Noga Alon, Sonny Ben-shimon, Michael Krivelevich
We prove that there is an absolute constant C> 0 so that for every natural n there exists a trianglefree regular graph with no independent set of size at least C √ n log n. 1
and Tel Aviv University (2007)
Noga Alon, Raphael Yuster, Uri Zwick
We describe a novel randomized method, the method of 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...
The following asymptotic result is proved. For every ffl? 0, and for every positive integer h, there exists an n 0 = n 0 (ffl; h) such that for every graph H with h vertices and for every n? n 0, any...
Let H be a graph on h vertices, and let G be a graph on n vertices. An H-factor of G is a spanning subgraph of G consisting of n=h vertex disjoint copies of H. The fractional arboricity of H is a(H)...
Noga Alon, Yair Caro, Raphael Yuster
Covering the edges of a graph by a prescribed tree with minimum overlap
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank
Consider the set H of all linear (or ane) transformations between two vector spaces over a nite eld F. We study how good H is as a class of hash functions, namely we consider hashing a set S of size...
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An ffl-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent...
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi
Abstract. In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage...
H-Factors in Dense Graphs (2007)
The following asymptotic result is proved. For every ffl ? 0, and for every positive integer h, there exists an n 0 = n 0 (ffl; h) such that for every graph H with h vertices and for every n ? n 0 ,...
Short Certificates for Tournaments (2007)
An isomorphism certificate of a labeled tournament T is a labeled subdigraph of T which together with an unlabeled copy of T allows the errorless reconstruction of T . It is shown that any tournament...
Regular Honest Graphs, Isoperimetric Numbers, and Bisection of Weighted Graphs (2007)
The edge-integrity of a graph G is I 0 (G) := minfjSj + m(G ; S) : S ae Eg# where m(H) denotes the maximum order of a component of H: A graph G is called honest if its edge-integrity is the maximum...
Acyclic Edge Colorings of Graphs (2007)
Noga Alon, Benny Sudakov, Ayal Zaks
A proper coloring of the edges of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a 0 (G), is the least number of colors in an...
Simple Constructions of Almost (2007)
Wise Independent Random, Noga Alon, Oded Goldreich, Johan Hastad
We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is...
Bipartite subgraphs (Final Version; to appear in Combinatorica) (2007)
It is shown that there exists a positive c so that for any large integer m, any graph with 2m 2 edges contains a bipartite subgraph with at least m 2 + m=2 + c p m edges. This is tight up to the...
Simple Constructions of Almost (2007)
Wise Independent, Noga Alon, Oded Goldreich, Johan Hastad
We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is...
Small sample spaces with almost independent random variables are applied to design efficient sequential deterministic algorithms for two problems. The first algorithm, motivated by the attempt to...
Equilateral sets in l n p (2007)
We show that for every odd integer p 1 there is an absolute positive constant c p, so that the maximum cardinality of a set of vectors in R n such that the l p distance between any pair is precisely...
Let Φ be a set of general boolean functions on n variables, such that each function depends on exactly k variables, and each variable can take a value from [1, d]. We say that Φ is ɛ-far from...
240 JOURNAL OF GRAPH THEORY (2007)
Noga Alon, Michael Krivelevich, Benny Sudakov
Abstract: A subgraph of a graph G is called trivial if it is either a clique or an independent set. Let qðGÞ denote the maximum number of vertices in a trivial subgraph of G. Motivated by an open...
Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov
We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an...
Noga Alon, Michael Krivelevich
A graph G is called k-saturated, where k 3 is an integer, if G is K k
graphs without short cycles (2007)
Noga Alon, Béla Bolloba S, Michael Krivelevich, Benny Sudakov E
Maximum cuts and judicious partitions in
Noga Alon, Michael Krivelevich, Benny Sudakov
It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d
Let be a set of general boolean functions on n variables, such that each function depends on exactly k variables, and each variable can take a value from [1; d]. We say that is -far from satisable,...
Noga Alon, Oded Goldreich, Rehovot Israel, Yishay Mansour
We say that a distribution over f0; 1g 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...
Transversal numbers for hypergraphs arising in geometry (2007)
Noga Alon, Gil Kalai, Roy Meshulam
Ji r ' i Matou sek y
Noga Alon, Venkatesan Guruswami, Tali Kaufman
We consider the guessing secrets problem dened by Chung, Graham, and Leighton [CGL01]. This is a variant of the standard 20 questions game where the player has a set of k> 1 secrets from a...
Noga Alon, Shai Ben-david, David Haussler
Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property...
Noga Alon, Michael Krivelevich, Benny Sudakov
We consider the following probabilistic model of a graph on n labeled vertices. First choose a random graph G(n; 1=2) and then choose randomly a subset Q of vertices of size k and force it to be a...
Voting paradoxes and digraphs realizations (2007)
A family of permutations F forms a realization of a directed graph T = (V; E) if for every directed edge uv of T, u precedes v in more than half of the permutations. The quality q(F; T) of the...
Noga Alon, Michael Krivelevich, Paul Seymour
It is shown that any k-critical graph with n vertices contains a cycle of length at least 2
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi
Abstract. In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage...
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F. We study how good H is as a class of hash functions, namely we consider hashing a set S...
Noga Alon, Colin Mcdiarmid, Michael Molloy
We prove that any k-regular directed graph with no parallel edges contains a collection of at least
Noga Alon, Tom Bohman, Daniel J. Kleitman
We prove that any partition of an n-dimensional discrete box into nontrivial sub-boxes must consist of at least 2 n sub-boxes, and consider some extensions of this theorem. 1 The theorem A set of the...
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An -test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or...
Noga Alon, Michael Krivelevich, Benny Sudakov
We consider the following probabilistic model of a graph on n labeled vertices. First choose a random graph G(n; 1=2) and then choose randomly a subset Q of vertices of size k and force it to be a...
Noga Alon, Michael Krivelevich, Simon Litsyn
hashing and applications to digital ngerprinting
Richard Beigel, Noga Alon, Mehmet Serkan Apaydn, Lance Fortnow, Simon Kasif
Tettelin et. al. proposed a new method for closing the gaps in whole genome shotgun sequencing projects. The method uses a multiplex PCR strategy in order to minimize the time and eort required to...
Learning a Hidden Matching (2007)
Combinatorial Identification Of, Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov
We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices induces an...
Turán numbers of bipartite graphs and related Ramsey-type questions (2007)
Noga Alon, Michael Krivelevich, Benny Sudakov
For a graph H and an integer n, the Turan number ex(n; H) is the maximum possible number of edges in a simple graph on n vertices that contains no copy of H . H is r-degenerate if every subgraph of...
The Number of Edge Colorings With No Monochromatic Cliques (2007)
Noga Alon Ozsef, Noga Alon, Peter Keevash, Benny Sudakov
Let F (n; r; k) denote the maximum possible number of distinct edge-colorings of a simple graph on n vertices with r colors, which contain no monochromatic copy of K k . It is shown that for every...
A General Approach to Online Network Optimization Problems (2007)
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (Seffi) Naor
We study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. In a general online network design problem,...
Finding and counting given length cycles (Extended Abstract) (2007)
Noga Alon, Raphael Yuster, Uri Zwick
Abstract. We present an assortment of methods for nding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of...
Almost K-Wise Independence Versus K-Wise Independence (2007)
Noga Alon Sackler, Noga Alon, Oded Goldreich, Rehovot Israel, Yishay Mansour
We say that a distribution over f0; 1g 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...
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Gábor Tardos
The research of P. Bro Miltersen was supported by the ESPRIT Long Term Research Programme of
Discrete Kakeya-type problems and small bases (2007)
Alon, Noga, Bukh, Boris, Sudakov, Benny
A subset U of a group G is called k-universal if U contains a translate of every k-element subset of G. We give several nearly optimal constructions of small k-universal sets, and use them to resolve...
Large nearly regular induced subgraphs (2007)
Alon, Noga, Krivelevich, Michael, Sudakov, Benny
For a real c \geq 1 and an integer n, let f(n,c) denote the maximum integer f so that every graph on n vertices contains an induced subgraph on at least f vertices in which the maximum degree is at...
Better Algorithms and Bounds for Directed Maximum Leaf Problems (2007)
Alon, Noga, Fomin, Fedor V., Gutin, Gregory, Krivelevich, Michael, Saurabh, Saket
The {\sc Directed Maximum Leaf Out-Branching} problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we...
Additive approximation for edge-deletion problems (2007)
Alon, Noga, Shapira, Asaf, Sudakov, Benny
A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following edge-deletion problem; given a monotone property P and a graph G, compute the...
On graphs with subgraphs of large independence numbers (2007)
Let G be a graph on n vertices in which every induced subgraph on s=\log^3 n vertices has an independent set of size at least t=\log n. What is the largest q=q(n) so that every such G must contain an...
Embedding nearly-spanning bounded degree trees (2007)
Alon, Noga, Krivelevich, Michael, Sudakov, Benny
We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1-\epsilon)n vertices, in terms of the expansion properties of G. As...
Poisson approximation for non-backtracking random walks (2007)
Random walks on expander graphs were thoroughly studied, with the important motivation that, under some natural conditions, these walks mix quickly and provide an efficient method of sampling the...
Many Random Walks Are Faster Than One (2007)
Alon, Noga, Avin, Chen, Koucky, Michal, Kozma, Gady, Lotker, Zvi, Tuttle, Mark R.
We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex,...
Parameterized Algorithms for Directed Maximum Leaf Problems (2007)
Alon, Noga, Fomin, Fedor, Gutin, Gregory, Krivelevich, Michael, Saurabh, Saket
We prove that finding a rooted subtree with at least $k$ leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in...
Tracing Many Users With Almost No Rate Penalty (2007)
For integers $n, r geq 2$ and $1 leq k leq r$, a family ${cal F}$ of subsets of $[n] = {1,ldots,n}$ is called $k$ -out-of-$r$ multiple-user tracing if, given the union of any $ell leq r$ sets from...
Tracing many users with almost no rate penalty (2007)
For integers n, r ≥ 2 and 1 ≤ k ≤ r, a family F of subsets of [n] = {1,..., n} is called k-outof-r multiple user tracing if, given the union of any ℓ ≤ r sets from the family, one can...
Finding disjoint paths in expanders deterministically and online (2007)
We describe a deterministic, polynomial time algorithm for finding edge-disjoint paths connecting given pairs of vertices in an expander. Specifically, the input of the algorithm is a sufficiently...
Optimal Universal Graphs with Deterministic Embedding (2007)
Let H be a finite family of graphs. A graph G is H-universal if it contains a copy of each H ∈ H as a subgraph. Let H(k, n) denote the family of graphs on n vertices with maximum degree at most 2 2...
Efficient testing of bipartite graphs for forbidden induced subgraphs ∗ (2007)
Noga Alon, Eldar Fischer, Ilan Newman
Alon et. al. [3], showed that every property that is characterized by a finite collection of forbidden induced subgraphs is ɛ-testable. However, the complexity of the test is double-tower with...
Better Algorithms and Bounds for Directed Maximum Leaf Problems (2007)
Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh
Abstract. The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we...
An elementary construction of constant-degree expanders (2007)
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, applied by [14] to give an iterative construction of...
Induced subgraphs with distinct size or order (2007)
We show that for every 0 < ɛ < 1/2, there is an n0 = n0(ɛ) such that if n> n0 then every n-vertex graph G of size at least ɛ � � � � n n 2 and at most (1 − ɛ) 2 contains...
Polychromatic Colorings of Plane Graphs (2007)
Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, Péter Csorba, Saswata Shannigrahi, ...
We show that the vertices of any plane graph in which every face is of length at least g can be colored by ⌊(3g − 5)/4 ⌋ colors so that every color appears in every face. This is nearly tight,...
Parameterized Algorithms for Directed Maximum Leaf Problems (2007)
Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh
Abstract. We prove that finding a rooted subtree with at least k leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves...
Weak ɛ-nets and interval chains (2007)
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1 r-nets of size O(rα(r)), where α(r)...
Parameterized Algorithms for Directed Maximum Leaf Problems (2007)
Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh
We prove that finding a rooted subtree with at least k leaves in a directed graph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in...
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...
Privileged users in zero-error transmission over a noisy channel (2007)
The k-th power of a graph G is the graph whose vertex set is V (G) k, where two distinct ktuples are adjacent iff they are equal or adjacent in G in each coordinate. The Shannon capacity of G, c(G),...
Parameterized Algorithms for Directed Maximum Leaf Problems (2007)
Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh, Royal Holloway
D is an out-tree if T is an oriented tree with only one vertex s of in-degree zero (called the root). The vertices of
Parameterized Algorithms for Directed Maximum Leaf Problems (2007)
Noga Alon, Noga Alon, Fedor V. Fomin, Fedor V. Fomin, Gregory Gutin, Gregory Gutin, ...
We prove that finding a rooted subtree with at least k leaves in a digraph is a fixed parameter tractable problem. A similar result holds for finding rooted spanning trees with many leaves in...
Small sample spaces cannot fool low degree polynomials Extended Abstract (2007)
Noga Alon, Ido Ben-eliezer, Michael Krivelevich
A distribution D on a set S ⊂ {0, 1} N ɛ-fools polynomials of degree at most d in N variables over Z2 if for any such polynomial P, the probability that P (x) vanishes when x is chosen according...
Better Algorithms and Bounds for Directed Maximum Leaf Problems (2007)
Noga Alon, Fedor V. Fomin, Gregory Gutin, Michael Krivelevich, Saket Saurabh, Royal Holloway
Abstract. The Directed Maximum Leaf Out-Branching problem is to find an out-branching (i.e. a rooted oriented spanning tree) in a given digraph with the maximum number of leaves. In this paper, we...
An elementary construction of constant-degree expanders (2007)
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, applied by [14] to give an iterative construction of...
Testing k-wise and almost k-wise independence (2007)
In this work, we consider the problems of testing whether a distribution over {0, 1} n is k-wise (resp. (ɛ, k)-wise) independent using samples drawn from that distribution. For the problem of...
Maximum directed cuts in acyclic digraphs (2007)
Noga Alon, Béla Bollobás, András Gyárfás, Jenő Lehel, Alex Scott
It is easily shown that every digraph with m edges has a directed cut of size at least m/4, and that 1/4 cannot be replaced by any larger constant. We investigate the size of a largest directed cut...
Weak ɛ-nets and interval chains (2007)
Noga Alon, Haim Kaplan, Gabriel Nivasch, Micha Sharir, Shakhar Smorodinsky
We construct weak ɛ-nets of almost linear size for certain types of point sets. Specifically, for planar point sets in convex position we construct weak 1 r-nets of size O(rα(r)), where α(r)...
Non-backtracking random walks mix faster (2006)
Alon, Noga, Benjamini, Itai, Lubetzky, Eyal, Sodin, Sasha
We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as...
Uniformly cross intersecting families (2006)
Let $\mathcal{A}$ and $\matchcal{B}$ denote two families of subsets of an $n$-element set. The pair $(\mathcal{A},\mathcal{B})$ is said to be $\ell$-cross-intersecting iff $|A\cap B| = \ell$ for all...
The Shannon capacity of a graph and the independence numbers of its powers (2006)
The independence numbers of powers of graphs have been long studied, under several definitions of graph products, and in particular, under the strong graph product. We show that the series of...
Privileged users in zero-error transmission over a noisy channel (2006)
The $k$-th power of a graph $G$ is the graph whose vertex set is $V(G)^k$, where two distinct $k$-tuples are adjacent iff they are equal or adjacent in $G$ in each coordinate. The Shannon capacity of...
Independent sets in tensor graph powers (2006)
The tensor product of two graphs, $G$ and $H$, has a vertex set $V(G)\times V(H)$ and an edge between $(u,v)$ and $(u',v')$ iff both $u u' \in E(G)$ and $v v' \in E(H)$. Let $A(G)$ denote the limit...
Graph powers, Delsarte, Hoffman, Ramsey and Shannon (2006)
The $k$-th $p$-power of a graph $G$ is the graph on the vertex set $V(G)^k$, where two $k$-tuples are adjacent iff the number of their coordinates which are adjacent in $G$ is not congruent to 0...
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A common thread in all the recent results concerning testing dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first...
Conflict-free colorings of shallow discs (2006)
Noga Alon, Shakhar Smorodinsky
We prove that any collection of n discs in which each one intersects at most k others, can be colored with at most O(log 3 k) colors so that for each point p in the union of all discs there is at...
Tell me who I am: An interactive recommendation system (2006)
Noga Alon, Baruch Awerbuch, Yossi Azar, Boaz Patt-shamir
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
Uniformly cross intersecting families (2006)
Let A and B denote two families of subsets of an n-element set. The pair (A, B) is said to be ℓ-cross-intersecting iff |A∩B | = ℓ for all A ∈ A and B ∈ B. Denote by Pℓ(n) the maximum...
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A common thread in all the recent results concerning the testing of dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our...
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...
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
A common thread in recent results concerning the testing of dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our first...
Uniformly cross intersecting families (2006)
Let A and B denote two families of subsets of an n-element set. The pair (A, B) is said to be ℓ-cross-intersecting iff |A∩B | = ℓ for all A ∈ A and B ∈ B. Denote by Pℓ(n) the maximum...
Non-backtracking random walks mix faster (2006)
Noga Alon, Itai Benjamini, Eyal Lubetzky, Sasha Sodin
We compute the mixing rate of a non-backtracking random walk on a regular expander. Using some properties of Chebyshev polynomials of the second kind, we show that this rate may be up to twice as...
Algorithmic construction of sets for k-restrictions (2006)
Noga Alon, Dana Moshkovitz, Shmuel Safra
This work addresses k-restriction problems, which unify combinatorial problems of the following type: The goal is to construct a short list of strings in Σ m that satisfies a given set of k-wise...
150 JOURNAL OF GRAPH THEORY (2006)
Abstract: Let G be a graph on n vertices in which every induced subgraph on s = log 3 n vertices has an independent set of size at least t = log n. What is the largest q = q(n) so that every such G...
Testing triangle-freeness in general graphs (2006)
Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron
In this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are...
Testing triangle-freeness in general graphs (2006)
Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron
In this paper we consider the problem of testing whether a graph is triangle-free, and more generally, whether it is H-free, for a fixed subgraph H. The algorithm should accept graphs that are...
A combinatorial characterization of the testable graph properties: it’s all about regularity (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A common thread in all the recent results concerning the testing of dense graphs is the use of Szemerédi’s regularity lemma. In this paper we show that in some sense this is not a coincidence. Our...
Noga Alon, Baruch Awerbuch, Johns Hopkins U, Yossi Azar, Boaz Patt-shamir
We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes...
Noga Alon, Ronitt Rubinfeld, Alexandr Andoni, Tali Kaufman, Ning Xie, Kevin Matulef
In this work, we consider the problems of testing whether a distribution over{0, 1} n is k-wise or (ǫ, k)-wise independent using samples drawn from that distribution. To distinguish k-wise...
Crossing patterns of semi-algebraic sets. (2005)
Alon, Noga, Pach, János, Pinchasi, Rom, Radoicic, Rados, Sharir, Micha
SHAPIRA: On an extremal hypergraph problem of Brown, Erdős and Sós (2005)
Let fr(n, v, e) denote the maximum number of edges in an r-uniform hypergraph on n vertices, which does not contain e edges spanned by v vertices. Extending previous results of Ruzsa and Szemerédi...
Every monotone graph property is testable (2005)
A graph property is called monotone if it is closed under removal of edges and vertices. Many monotone graph properties are some of the most well-studied properties in graph theory, and the abstract...
Testing of bipartite graph properties ∗ (2005)
Noga Alon, Eldar Fischer, Ilan Newman
Alon et. al. [3], showed that every property that is characterized by a finite collection of forbidden induced subgraphs is ɛ-testable. However, the complexity of the test is double-tower with...
Homomorphisms in graph property testing - A survey (2005)
on the occasion of his 60 th birthday
Linear equation, arithmetic progressions and hypergraph property testing (2005)
For a fixed k-uniform hypergraph D (k-graph for short, k ≥ 3), we say that a k-graph H) if it contains no copy (resp. induced copy) of D. Our goal in satisfies property PD (resp. P ∗ D this paper...
Linear equation, arithmetic progressions and hypergraph property testing (2005)
Abstract: For a fixed k-uniform hypergraph D (k-graph for short, k ≥ 3), we say that a k-graph H satisfies property PD (or property P ∗ D) if it contains no copy (or no induced copy) of D. Our...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimumrelaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimumrelaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Generalization error bounds for collaborative prediction with low-rank matrices (2005)
Nathan Srebro, Noga Alon, Tommi S. Jaakkola
We prove generalization error bounds for predicting entries in a partially observed matrix by fitting the observed entries with a low-rank matrix. In justifying the analysis approach we take to...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Erik D. Demaine, Martin Farach-colton, Anastasios Sidiropoulos
Abstract. We introduce a new notion of embedding, called minimum-relaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is...
Additive approximation for edge-deletion problems (2005)
Noga Alon, Asaf Shapira, Benny Sudakov
A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following algorithmic problem, called the edge-deletion problem; given a monotone...
Tight bounds for shared memory systems accessed by Byzantine processes (2005)
Noga Alon, Michael Merritt, Omer Reingold, Gadi Taubenfeld, Rebecca N. Wright
Summary. We provide efficient constructions and tight bounds for shared memory systems accessed by n processes, up to t of which may exhibit Byzantine failures, in a model previously explored by...
Quadratic forms on graphs (2005)
Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
We introduce a new graph parameter, called the Grothendieck constant of a graph G = (V, E), which is defined as the least constant K such that for every A: E → R,
Hardness of Fully Dense Problems (2005)
In the past decade, there has been a stream of work in designing approximation schemes for dense instances of NP-Hard problems. These include the work of Arora, Karger and Karpinski from 1995 and...
Estimating arbitrary subset sums with few probes (2005)
Noga Alon, Nick Duffield, Carsten Lund, Mikkel Thorup
Suppose we have a large table T of items i, each with a weight wi, e.g., people and their salary. In a general preprocessing step for estimating arbitrary subset sums, we assign each item a random...
Quadratic forms on graphs (2005)
Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
We introduce a new graph parameter, called the Grothendieck constant of a graph G = (V, E), which is defined as the least constant K such that for every A: E → R,
SHAPIRA: On an extremal hypergraph problem of Brown, Erdős and Sós (2005)
Let fr(n, v, e) denote the maximum number of edges in an r-uniform hypergraph on n vertices, which does not contain e edges spanned by v vertices. Extending previous results of Ruzsa and Szemerédi...
A characterization of the (natural) graph properties testable with one-sided error (2005)
The problem of characterizing all the testable graph properties is considered by many to be the most important open problem in the area of property-testing. Our main result in this paper is a...
Ordinal embeddings of minimum relaxation: General properties, trees and ultrametrics (2005)
Noga Alon, Mihai Bădoiu, Erik D. Demaine, Martin Farach-colton, Mohammadtaghi Hajiaghayi, Anastasios Sidiropoulos
We introduce a new notion of embedding, called minimumrelaxation ordinal embedding, parallel to the standard notion of minimum-distortion (metric) embedding. In an ordinal embedding, it is the...
Additive approximation for edge-deletion problems (2005)
Noga Alon, Asaf Shapira, Benny Sudakov
A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following algorithmic problem, called the edge-deletion problem; given a monotone...
Every monotone graph property is testable (2005)
A graph property is called monotone if it is closed under removal of edges and vertices. Many monotone graph properties are some of the most well-studied properties in graph theory, and the abstract...
Crossing patterns of semi-algebraic sets (2005)
Noga Alon, János Pach, Rom Pinchasi, Micha Sharir
We prove that, for every family F of n semi-algebraic sets in R d of constant description complexity, there exist a positive constant ε that depends on the maximum complexity of the elements of F,...
Homomorphisms in graph property testing - A survey (2005)
on the occasion of his 60 th birthday
Additive approximation for edge-deletion problems (2005)
Noga Alon, Asaf Shapira, Benny Sudakov
A graph property is monotone if it is closed under removal of vertices and edges. In this paper we consider the following algorithmic problem, called the edge-deletion problem; given a monotone...
Linear equation, arithmetic progressions and hypergraph property testing (2005)
For a fixed k-uniform hypergraph D (k-graph for short, k ≥ 3), we say that a k-graph H) if it contains no copy (resp. induced copy) of D. Our goal in satisfies property PD (resp. P ∗ D this paper...
A characterization of the (natural) graph properties testable with one-sided error (2005)
The problem of characterizing all the testable graph properties is considered by many to be the most important open problem in the area of property-testing. Our main result in this paper is a...
Generalization error bounds for collaborative prediction with low-rank matrices (2005)
Nathan Srebro, Noga Alon, Tommi S. Jaakkola
We prove generalization error bounds for predicting entries in a partially observed matrix by fitting the observed entries with a low-rank matrix. In justifying the analysis approach we take to...
Quadratic forms on graphs (2005)
Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor
We introduce a new graph parameter, called the Grothendieck constant of a graph G = (V, E), which is defined as the least constant K such that for every A: E → R,
The Shannon capacity of a graph and the independence numbers of its powers (2005)
The independence numbers of powers of graphs have been long studied, under several definitions of graph products, and in particular, under the strong graph product. We show that the series of...
The Raymond, Beverly Sackler, Faculty Exact Sciences, Tali Kaufman, Under Professors, Noga Alon, ...
Property Testing is nowadays one of the central fields in Theoretical Computer Science. This concept played a major role in the proof of the celebrated PCP theorem. A typical task in Property Testing...
Tight bounds for shared memory systems accessed by Byzantine processes (2005)
Noga Alon, Michael Merritt, Omer Reingold, Gadi Taubenfeld, Rebecca N. Wright
We provide efficient constructions and tight bounds for shared memory systems accessed by n processes, up to t of which may exhibit Byzantine failures, in a model previously explored by Malkhi et al....
Percolation on finite graphs and isoperimetric inequalities (2004)
Alon, Noga, Benjamini, Itai, Stacey, Alan
Consider a uniform expanders family Gn with a uniform bound on the degrees. It is shown that for any p and c>0, a random subgraph of Gn obtained by retaining each edge, randomly and independently,...
Dominating sets in k-majority tournaments (2004)
Alon, Noga, Brightwell, Graham, Kierstead, H. A., Kostochka, A. V., Winkler, Peter
A k-majority tournament T on a finite vertex set V is defined by a set of 2k − 1 linear orderings of V , with u ! v if and only if u lies above v in at least k of the orders. Motivated in part by...
A characterization of easily testable induced subgraphs (2004)
Let H be a fixed graph on h vertices. We say that a graph G is induced H-free if it does not contain any induced copy of H. Let G be a graph on n vertices and suppose that at least ɛn 2 edges have...
Learning a hidden subgraph (2004)
We consider the problem of learning a labeled graph from a given family of graphs on n vertices in a model where the only allowed operation is to query whether a set of vertices induces an edge....
The number of edge colorings with no monochromatic cliques (2004)
Noga Alon, József Balogh, Peter Keevash, Benny Sudakov
Let F (n, r, k) denote the maximum possible number of distinct edge-colorings of a simple graph on n vertices with r colors which contain no monochromatic copy of Kk. Itisshownthatfor every fixed k...
Graph products, fourier analysis and spectral techniques (2004)
Noga Alon, Irit Dinur, Ehud Friedgut, Benny Sudakov
We consider powers of regular graphs defined by the weak graph product and give a characterization of maximum-size independent sets for a wide family of base graphs which includes, among others,...
A characterization of easily testable induced subgraphs (2004)
Let H be a fixed graph on h vertices. We say that a graph G is induced H-free if it does not contain any induced copy of H. Let G be a graph on n vertices and suppose that at least ɛn 2 edges have...
Testing Reed Muller Codes \Lambda (2004)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
Abstract A code is locally testable if there is a way to indicate with high probability that a vector is far enough from any codeword by accessing only a very small number of the vector's bits....
Dominating Sets in k-Majority Tournaments (2004)
Noga Alon, Graham Brightwell, H. A. Kierstead, A. V. Kostochka, Peter Winkler
A k-majority tournament T on a finite vertex set V is defined by a set of 2k − 1 linear orderings of V, with u → v if and only if u lies above v in at least k of the orders. Motivated in part by...
A general approach to online network optimization problems (2004)
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (seffi Naor
Abstract We study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. In a general online network design...
A characterization of easily testable induced subgraphs (2004)
Let H be a fixed graph on h vertices. We say that a graph G is induced H-free if it does not contain any induced copy of H. Let G be a graph on n vertices and suppose that at least ɛn 2 edges have...
Learning a hidden subgraph (2004)
We consider the problem of learning a labeled graph from a given family of graphs on n vertices in a model where the only allowed operation is to query whether a set of vertices induces an edge....
Approximating the cut-norm via Grothendieck’s inequality (2004)
The cut-norm ||A||C of a real matrix A = (aij)i∈R,j∈S is the maximum, over all I ⊂ R, J ⊂ S of the quantity | � i∈I,j∈J aij|. This concept plays a major role in the design of efficient...
A characterization of easily testable induced subgraphs (2004)
Let H be a fixed graph on h vertices. We say that a graph G is induced H-free if it does not contain any induced copy of H. Let G be a graph on n vertices and suppose that at least ɛn 2 edges have...
XML with data values: typechecking revisited (2003)
We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had...
Typechecking XML views of relational databases (2003)
Alon, Noga, Milo, Tova, Suciu, Dan, Vianu, Victor
Motivated by the need to export relational databases as XML data in the context of the Web, we investigate the typechecking problem for transformations of relational data into tree data (XML). The...
XML with data values: typechecking revisited (2003)
We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had...
Typechecking XML views of relational databases (2003)
Alon, Noga, Milo, Tova, Suciu, Dan, Vianu, Victor
Motivated by the need to export relational databases as XML data in the context of the Web, we investigate the typechecking problem for transformations of relational data into tree data (XML). The...
XML with data values: typechecking revisited (2003)
Alon, Noga, Milo, Tova, NEVEN, Frank
We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had...
Typechecking XML views of relational databases (2003)
Alon, Noga, Milo, Tova, NEVEN, Frank, Suciu, Dan, Vianu, Victor
Motivated by the need to export relational databases as XML data in the context of the Web, we investigate the typechecking problem for transformations of relational data into tree data (XML). The...
Discrete Mathematics: Methods and Challenges (2003)
Combinatorics is a fundamental mathematical discipline as well as an essential component of many mathematical areas, and its study has experienced an impressive growth in recent years. One of the...
Partitioning into graphs with only small components (2003)
Noga Alon, Guoli Ding, Bogdan Oporowski, Dirk Vertigan
Abstract. The paper presents several results on edge partitions and vertex partitions of graphs into graphs with bounded size components. We show that every graph of bounded tree-width and bounded...
Testing subgraphs in directed graphs (2003)
Let H be a fixed directed graph on h vertices, let G be a directed graph on n vertices and suppose that at least ɛn2 edges have to be deleted from it to make it H-free. We show that in this case G...
Problems and results in extremal combinatorics–I (2003)
Extremal Combinatorics is one of the central areas in Discrete Mathematics. It deals with problems that are often motivated by questions arising in other areas, including Theoretical Computer...
Testing subgraphs in directed graphs (2003)
Let H be a fixed directed graph on h vertices, let G be a directed graph on n vertices and suppose that at least ɛn 2 edges have to be deleted from it to make it H-free. We show that in this case G...
Testing subgraphs in directed graphs (2003)
Let H be a fixed directed graph on h vertices, let G be a directed graph on n vertices and suppose that at least ɛn2 edges have to be deleted from it to make it H-free. We show that in this case G...
Addendum to "Scalable Secure Storage when Half the System is (2003)
Faulty Noga Alon, Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
Introduction. We consider the following problem. A file of size s bits is to be stored on n disks. Our failure model assumes that a potentially malicious adversary may choose after the file is stored...
The Online Set Cover Problem (2003)
Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph (Seffi) Naor
Let X = f1; 2; : : : ; ng be a ground set of n elements, and let S be a family of subsets of X , jSj = m, with a positive cost c S associated with each S 2 S.
Partitioning into graphs with only small components (2003)
Noga Alon, Guoli Ding, Bogdan Oporowski, Dirk Vertigan
Abstract. The paper presents several results on edge partitions and vertex partitions of graphs into graphs with bounded size components. We show that every graph of bounded tree-width and bounded...
doi:10.1017/S0963548305007017 Printed in the United Kingdom MaxCut in H-Free Graphs (2003)
Noga Alon, Michael Krivelevich, Benny Sudakov
For a graph G, letf(G) denote the maximum number of edges in a cut of G. For an integer m and for a fixed graph H, letf(m, H) denote the minimum possible cardinality of f(G), as G ranges over all...
Graph Products, Fourier Analysis and Spectral Techniques (2003)
Noga Alon, Irit Dinur, Ehud Friedgut, Benny Sudakov
We consider powers of regular graphs defined by the weak graph product and give a characterization of maximum-size independent sets for a wide family of base graphs which includes, among others,...
Generalized Hashing and Parent-Identifying Codes (2003)
Noga Alon, Gerard Cohen, Michael Krivelevich, Simon Litsyn
Let C be a code of length n over an alphabet of q letters. For a pair of integers 2 t < u, C is (t; u)-hashing if for any two subsets T ; U C, satisfying T U , jT j = t, jU j = u, there is a...
Testing Low-Degree Polynomials over GF(2) (2003)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
We describe an efficient randomized algorithm to test if a given binary function f : f0; 1g ! f0; 1g is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k 1 and a...
Testing Low-Degree Polynomials over GF(2) (2003)
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
We describe an efficient randomized algorithm to test if a given binary function f : f0; 1g ! f0; 1g is a low-degree polynomial (that is, a sum of low-degree monomials). For a given integer k 1 and a...
Problems and results in extremal combinatorics–I (2003)
Extremal Combinatorics is one of the central areas in Discrete Mathematics. It deals with problems that are often motivated by questions arising in other areas, including Theoretical Computer...
Noga Alon, Tao Jiang, Zevi Miller, Dan Pritikin
ABSTRACT: We consider a canonical Ramsey type problem. An edge-coloring of a graph is called m-good if each color appears at most m times at each vertex. Fixing a graph G and a positive integer m,...
Noga Alon, Ramat-aviv Israel, Yishay Mansour, Oded Goldreich
We say that a distribution over {0, 1} n is (ɛ, k)-wise independent if its restriction to every k coordinates results in a distribution that is ɛ-close to the uniform distribution. A natural...
Discrete mathematics: methods and challenges (2002)
Combinatorics is a fundamental mathematical discipline as well as an essential component of many mathematical areas, and its study has experienced an impressive growth in recent years. One of the...
Percolation on finite graphs and isoperimetric inequalities (2002)
Alon, Noga, Benjamini, Itai, Stacey, Alan
Consider a uniform expanders family G_n with a uniform bound on the degrees. It is shown that for any p and c>0, a random subgraph of G_n obtained by retaining each edge, randomly and independently,...
Noga Alon, Nathan Linial, Amotz Bar-noy, David Peleg
A radio network is a synchronous network of processors that communicate by trans-mitting messages to their neighbors. A processor receives a message in a given step if and only if it is silent then...
A Lower Bound on the Expected Length of 1-1 Codes Abstract (2002)
We show that the minimum expected length of a 1-1 encoding of a discrete random variable X is at least 1 H(X)−log(H(X)+1)−log e and that this bound is asymptotically achievable. 1
The Moore bound for irregular graphs (2002)
Noga Alon, Shlomo Hoory, Nathan Linial
What is the largest number of edges in a graph of order n and girth g? For dregular graphs, essentially the best known answer is provided by the Moore bound. This result is extended here to cover...
STRING QUARTETS IN BINARY (2002)
Noga Alon, János Körner, Angelo Monti
Let M(n, A) denote the maximum possible cardinality of a family of binary strings of length n, such that for every four distinct members of the family there is a coordinate in which exactly two of...
Short certificates for tournaments (2002)
An isomorphism certificate of a labeled tournament T is a labeled subdigraph of T which to-gether with an unlabeled copy of T allows the errorless reconstruction of T. It is shown that any tournament...
The investigation of the asymptotic behaviour of various parameters of powers of a fixed graph leads to many fascinating problems, some of which are motivated by questions in information theory,...
Constructing worst case instances for semidefinite programming based approximation algorithms (2002)
Noga Alon, Benny Sudakov, Uri Zwick
Semide nite programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees...
The Moore bound for irregular graphs (2002)
Noga Alon, Shlomo Hoory, Nathan Linial
What is the largest number of edges in a graph of order n and girth g? For d-regular graphs, essentially the best known answer is provided by the Moore bound. This result is extended here to cover...
The Moore bound for irregular graphs (2002)
Noga Alon, Shlomo Hoory, Nathan Linial
What is the largest number of edges in a graph of order n and girth g? For d-regular graphs, essentially the best known answer is provided by the Moore bound. This result is extended here to cover...
Constructing worst case instances for semidefinite programming based approximation algorithms (2002)
Noga Alon, Benny Sudakov, Uri Zwick
Semide nite programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees...
Tracking Join and Self-Join Sizes in Limited Storage (2002)
Noga Alon, Phillip B. Gibbons, Yossi Matias, Mario Szegedy
This paper presents algorithms for tracking (approximate) join and self-join sizes in limited storage, in the presence of insertions and deletions to the data set(s). Such algorithms detect changes...
Noga Alon, Michael Krivelevich, Benny Sudakov
For a graph H and an integer n, theTurán number ex(n, H) isthemaximum possible number of edges in a simple graph on n vertices that contains no copy of H. H is rdegenerate if every one of its...
Learning a hidden matching (2002)
Noga Alon, Richard Beigel, Simon Kasif, Steven Rudich, Benny Sudakov
Abstract. We consider the problem of learning a matching (i.e., a graph in which all vertices have degree 0 or 1) in a model where the only allowed operation is to query whether a set of vertices...
Noga Alon, Tao Jiang, Zevi Miller, Dan Pritikin
colored subgraphs and rainbow subgraphs in edge-colorings
Noga Alon, Miklós Bóna, Joel Spencer
Answering a question of Wilf, we show that if n is sufficiently large, then one cannot cover an n × p(n) rectangle using each of the p(n) distinct Ferrers shapes of size n exactly once. Moreover,...
Noga Alon, Tom Bohman, Ron Holzman, Daniel J. Kleitman, A An
We prove that any partition of an n-dimensional discrete box into nontrivial sub-boxes must consist of at least 2 n sub-boxes, and consider some extensions of this theorem.
XML with Data Values: Typechecking Revisited (2001)
Alon, Noga, Milo, Tova, Suciu, Dan, Vianu, Victor
We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had...
XML with Data Values: Typechecking Revisited (2001)
Alon, Noga, Milo, Tova, Suciu, Dan, Vianu, Victor
We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had...
XML with Data Values: Typechecking Revisited (2001)
Alon, Noga, Milo, Tova, NEVEN, Frank, Suciu, Dan, Vianu, Victor
We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had...
XML with data values: typechecking revisited (2001)
Noga Alon, Tova Milo, Dan Suciu
We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had...
Equireplicate balanced binary codes for oligo arrays (2001)
Noga Alon, Charles J. Colbourn, Martin Tompa
Abstract. In the manufacture of oligo arrays for DNA hybridization experiments, manufacturing defects must be detected and their position determined. The design of manufacturing protocols for such...
Near-optimal universal graphs for graphs with bounded degrees (2001)
Noga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński, Endre Szemerédi
Abstract. Let H be a family of graphs. We say that G is H-universal if, for each H ∈ H, the graph G contains a subgraph isomorphic to H. Let H(k, n) denote the family of graphs on n vertices with...
Near-optimal universal graphs for graphs with bounded degrees (2001)
Noga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński, Endre Szemerédi
Abstract. Let H be a family of graphs. We say that G is H-universal if, for each H ∈H,the graph G contains a subgraph isomorphic to H. Let H(k, n) denote the family of graphs on n vertices with...
Acyclic edge colorings of graphs (2001)
Noga Alon, Benny Sudakov, Ayal Zaks
A proper coloring of the edges of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a ′ (G), is the least number of colors in an...
Parent-identifying codes (2001)
Noga Alon, Eldar Fischer, Mario Szegedy
For a set C of words of length 4 over an alphabet of size n, and for a, b ∈ C, let D(a, b) be the set of all descendants of a and b, that is, all words x of length 4 where xi ∈ {ai, bi} for all 1...
Near-optimal universal graphs for graphs with bounded degrees (2001)
Noga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojtěch Rödl, Andrzej Ruciński, Endre Szemerédi
Abstract. Let H be a family of graphs. We say that G is H-universal if, for each H ∈H, the graph G contains a subgraph isomorphic to H. Let H(k, n) denote the family of graphs on n vertices with...
Lower bounds for approximations by low degree polynomials over Zm (2001)
Noga Alon, Tel Aviv, Richard Beigel
Abstract We use a Ramsey-theoretic argument to obtain the firstlower bounds for approximations over Zm by nonlinearpolynomials: ffl A degree-2 polynomial over Zm (m odd) mustdiffer from the parity...
Large induced forests in sparse graphs (2001)
Noga Alon, Dhruv Mubayi, Robin Thomas
For a graph G, leta(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree ∆. Our results include: (a) if...
Large induced forests in sparse graphs (2001)
Noga Alon, Dhruv Mubayi, Robin Thomas
For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree ∆. Our results include: (a)...
Lower bounds for approximations by low degree polynomials over Zm (2001)
We use a Ramsey-theoretic argument to obtain the first lower bounds for approximations over Zm by nonlinear polynomials: A degree-2 polynomial over Zm (m odd) must differ from the parity function on...
XML with data values: typechecking revisited (2001)
Noga Alon, Tova Milo, Dan Suciu, Frank Neven, Victor Vianu
We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had...
Typechecking XML Views of Relational Databases (2001)
Noga Alon, Tova Milo, Frank Neven, Dan Suciu, Victor Vianu
Motivated by the need to export relational databases as XML data in the context of the Web, we investigate the typechecking problem for transformations of relational data into tree data (XML). The...
Equireplicate balanced binary codes for oligo arrays (2001)
Noga Alon, Beverley Sackler, Charles J. Colbourn, Martin Tompa
U.S.A. In the manufacture of oligo arrays for DNA hybridization experiments, manufacturing defects must be detected and their position determined. The design of manufacturing protocols for such oligo...
Typechecking XML Views of Relational Databases (2001)
Noga Alon, Tova Milo, Frank Neven, Dan Suciu, Victor Vianu
Motivated by the need to export relational databases as XML data in the context of the Web, we investigate the typechecking problem for transformations of relational data into tree data (XML). The...
XML with data values: typechecking revisited (2001)
Noga Alon, Tova Milo, Frank Neven, Dan Suciu, Victor Vianu
We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had...
Parent-identifying codes (2001)
Noga Alon, Eldar Fischer, Mario Szegedy
For a set C of words of length 4 over an alphabet of size n, and for a; b 2 C, let D(a; b) be the set of all descendants of a and b, that is, all words x of length 4 where x i 2 fa i; b i g for all 1...
Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms (2001)
Noga Alon, Benny Sudakov, Uri Zwick
Semide nite programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees...
Random Sampling and Approximation of MAX-CSP Problems (2001)
Noga Alon, 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 . We prove a new general paradigm...
Random Sampling and Approximation of MAX-CSP Problems (2001)
Noga Alon, 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 . We prove a new general paradigm...
Constructing Worst Case Instances for Semidefinite Programming Based Approximation Algorithms (2001)
Noga Alon, Benny Sudakov, Uri Zwick
SL,BAEb#[1 programming based approximation algorithms, such as the Goemans and Williamson approximation algorithm for the MAX CUT problem, are usually shown to have certain performance guarantees...
Partitioning into Graphs with Only Small Components (2001)
Noga Alon, Guoli Ding, Bogdan Oporowski, Dirk Vertigan
The paper presents several results on edge partitions and vertex partitions of graphs into graphs with bounded size components.
Acyclic edge colorings of graphs (2001)
Noga Alon, Benny Sudakov, Ayal Zaks
Abstract: A proper coloring of the edges of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic edge chromatic number of G, denoted by a 0 (G), is the least number of colors...
XML with Data Values: Typechecking Revisited (2001)
Noga Alon, Tova Milo, Frank Neven, Dan Suciu, Victor Vianu
Weinvestigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had...
Typechecking XML Views of Relational Databases (2001)
Noga Alon, Tova Milo, Frank Neven, Dan Suciu, Victor Vianu
Motivated by the need to export relational databases as XML data in the context of the Web, we investigate the typechecking problem for transformations of relational data into tree data (XML). The...
Transversal Numbers for Hypergraphs Arising in Geometry (2001)
Noga Alon, Gil Kalai, Roy Meshulam
Introduction Helly's theorem asserts that if F is a nite family of convex sets in R in which every d + 1 or fewer sets have a point in common then F 6= ;. Our starting point, the (p; q) theorem,...
Near-optimum Universal Graphs for Graphs with Bounded Degrees (Extended Abstract) (2001)
Noga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojtech Rodl, Andrzej Rucinski, Endre Szemeredi
Noga Alon ,Mi Capalbo Yoshi2z3 Kohayakawa 3,### , Vojtech Rodl , AndrzejRuci nski , and Endre Szemeredi 1 Department of Mathematics, Raymond and Beverly Sackler Faculty of Exact Sciences, Aviv...
XML with Data Values: Typechecking Revisited (2001)
Noga Alon Tel, Noga Alon, Tova Milo, Frank Neven, Dan Suciu, ...
We investigate the typechecking problem for XML queries: statically verifying that every answer to a query conforms to a given output DTD, for inputs satisfying a given input DTD. This problem had...
Typechecking XML Views of Relational Databases (2001)
Noga Alon, Tova Milo, Frank Neven, Dan Suciu, Victor Vianu
Motivated by the need to export relational databases as XML data in the context of the Web, we investigate the typechecking problem for transformations of relational data into tree data (XML). The...
On the complexity of arrangements of circles in the plane (2001)
Noga Alon, Hagit Last, Rom Pinchasi, Micha Sharir
Continuing and extending the analysis in a previous paper [9], we establish several combinatorial results on the complexity of arrangements of circles in the plane. The main results are a collection...
Scalable Secure Storage when Half the System Is Faulty (2000)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...
Bipartite subgraphs and the smallest eigenvalue (2000)
Two results dealing with the relation between the smallest eigenvalue of a graph and its bipartite subgraphs are obtained. The first result is that the smallest eigenvalue µ of any non-bipartite...
Scalable Secure Storage when Half the System Is Faulty (2000)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...
On the concentration of eigenvalues of random symmetric matrices (2000)
Noga Alon, Michael Krivelevich, Van H. Vu
It is shown that for every 1 ≤ s ≤ n, the probability that the s-th largest eigenvalue of a random symmetric n-by-n matrix with independent random entries of absolute value at most 1 deviates...
On the concentration of eigenvalues of random symmetric matrices (2000)
Noga Alon, Michael Krivelevich, Van H. Vu
It is shown that for every 1 ≤ s ≤ n, the probability that the s-th largest eigenvalue of a random symmetric n-by-n matrix with independent random entries of absolute value at most 1 deviates...
Scalable Secure Storage when Half the System Is Faulty (2000)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...
Scalable Secure Storage when Half the System Is Faulty (2000)
Noga Alon, Haim Kaplan, Michael Krivelevich, Dahlia Malkhi, Julien Stern
In this paper, we provide a method to safely store a document in perhaps the most challenging settings, a highly decentralized replicated storage system where up to half of the storage servers may...
On the concentration of eigenvalues of random symmetric matrices (2000)
Noga Alon, Michael Krivelevich, Van H. Vu
It is shown that for every 1 s n, the probability that the s-th largest eigenvalue of a random symmetric n-by-n matrix with independent random entries of absolute value at most 1 deviates from its...
Noga Alon, Seannie Dar, Michal Parnas, Dana Ron
A set X of points in ! d is (k; b)-clusterable if X can be partitioned into k subsets (clusters) so that the diameter (alternatively, the radius) of each cluster is at most b. We present algorithms...
Large Induced Forests in Sparse Graphs (2000)
Noga Alon, Dhruv Mubayi, Robin Thomas
For a graph G, let a(G) denote the maximum size of a subset of vertices that induces a forest. Suppose that G is connected with n vertices, e edges, and maximum degree \Delta. Our results include:...
On The Complexity of Arrangements of (2000)
Circles In The, Noga Alon, Rom Pinchasi, Micha Sharir
Continuing and extending the analysis in a previous paper [11], we establish several combinatorial results on the complexity of arrangements of circles in the plane. The main results are a collection...
Locally thin set families (2000)
Noga Alon, Emanuela Fachini, János Körner
A family of subsets of an n–set is k–locally thin if for every k of its member sets the ground set has at least one element contained in exactly 1 of them. We derive new asymptotic upper bounds...
On the number of permutations avoiding a given pattern (1999)
Let σ ∈ Sk and τ ∈ Sn be permutations. We say τ contains σ if there exist 1 ≤ x1 < x2 <... < xk ≤ n such that τ(xi) < τ(xj) if and only if σ(i) < σ(j). If τ does not...
Combinatorial nullstellensatz (1999)
We present a general algebraic technique and discuss some of its numerous applications in Combinatorial Number Theory, in Graph Theory and in Combinatorics. These applications in-clude results in...
Decreasing the diameter of bounded degree graphs (1999)
Noga Alon, András Gyárfás, Miklós Ruszinkó
To the memory of Paul Erdős Let fd(G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with...
Alon and Yuster [4] have proven that if a fixed graph K on g vertices is (h + 1)-colorable, then any graph G with n vertices and minimum degree at least h n h+1n contains at least (1 − ɛ) g vertex...
Perfect matchings in ɛ-regular graphs (1999)
Noga Alon, Vojtech Rödl, Andrzej Ruciński
A super (d, ɛ)-regular graph on 2n vertices is a bipartite graph on the classes of vertices V1 and V2, where |V1 | = |V2 | = n, in which the minimum degree and the maximum degree are between...
Noga Alon, Martin Dietzfelbinger, Peter Bro, Miltersen Erez Petrank, Gábor Tardos
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F. We study how good H is as a class of hash functions, namely we consider hashing a set S...
Noga Alon, Michael Krivelevich
Let G be a graph on n vertices and suppose that at least n 2 edges have to be deleted from it to make it k-colorable. It is shown that in this case most induced subgraphs of G on ck ln k= 2 vertices...
Martin Dietzfelbinger, Peter Bro Miltersen, G Abor Tardos, Noga Alon, Noga Alon, Erez Petrank, ...
et al.:
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
Efficient testing of large graphs (1999)
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An -test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent or...
Noga Alon, Michael Krivelevich
Let G be a graph on n vertices and suppose that at least n 2 edges have to be deleted from it to make it k-colorable. It is shown that in this case most induced subgraphs of G on ck ln k= 2 vertices...
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
On the number of permutations avoiding a given pattern (1999)
Let oe 2 S k and 2 S n be permutations. We say contains oe if there exist
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
Independent Sets in Hypergraphs with Applications to Routing Via Fixed Paths (1999)
Noga Alon, Uri Arad, Yossi Azar
The problem of finding a large independent set in a hypergraph by an online algorithm is considered. We provide bounds for the best possible performance ratio of deterministic vs. randomized and...
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
An ordered partition of a set of n points in the d dimensional Euclidean space is called a separable partition if the convex hulls of the parts are pairwise disjoint. For each fixed p and d we...
On Two Segmentation Problems (1999)
this paper is organized as follows. In Section 2 we consider the hypercube segmentation problem, describe our randomized approximation algorithm, and present is derandomization. In Section 3 we...
Coloring Graphs with Sparse Neighborhoods (1999)
Noga Alon, Michael Krivelevich, Benny Sudakov
INTRODUCTION The chromatic number /(G) of a graph G is the minimum number of colors required to color all its vertices so that adjacent vertices get distinct colors. It is easy and well known that if...
Constructive lower bounds for off-diagonal Ramsey numbers (1999)
We describe an explicit construction which, for some fixed absolute positive constant ", produces, for every integer s ? 1 and all sufficiently large m, a graph on at least m " p log s= log...
Economical Covers With Geometric Applications (1999)
Noga Alon, Bela Bollobas, Jeong Han Kim, Kim Van, Van Ha Vu
A cover of a hypergraph is a collection of edges whose union contains all vertices. Let H = (V, E) be a k-uniform, D-regular hypergraph on n vertices, in which no two vertices are contained in more...
On Two Segmentation Problems (1999)
The hypercube segmentation problem is the following: Given a set S of m vertices of the discrete d-dimensional cube {0, 1}^d, find k vertices P 1 , ..., P k , P i in {0, 1}^d and a partitions of S...
On two segmentation problems (1999)
The hypercube segmentation problem is the following: Given a set S of m 4d vertices of the discrete d-dimensional cube 0, 1, find k vertices P 1,...,P k, 4d Pi � 0, 1 and a partitions of S into k...
Efficient testing of large graphs (1999)
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An ɛ-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent...
Noga Alon, Michael Krivelevich
Let G be a graph on n vertices and suppose that at least ɛn 2 edges have to be deleted from it to make it k-colorable. It is shown that in this case most induced subgraphs of G on ck ln k/ɛ 2...
An ordered partition of a set of n points in the d dimensional Euclidean space is called a separable partition if the convex hulls of the parts are pairwise disjoint. For each fixed p and d we...
Regular Languages are Testable with a Constant Number of Queries (1999)
Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy
We continue the study of combinatorial property testing, initiated by Goldreich, Goldwasser and Ron in [7]. The subject of this paper is testing regular languages. Our main result is as follows. For...
Norm-graphs: variations and applications (1999)
Noga Alon, Lajos Rónyai, Tibor Szabó
We describe several variants of the norm-graphs introduced by Kollár, Rónyai, and Szabó and study some of their extremal properties. Using these variants we construct, for infinitely many values...
Alon, Noga, Bóna, Miklós, Spencer, Joel
Answering a question of Wilf, we show that if $n$ is sufficiently large, then one cannot cover an $n \times p(n)$ rectangle using each of the $p(n)$ distinct Ferrers shapes of size $n$ exactly once....
On the Capacity of Digraphs (1998)
For a digraph G = (V, E) let w(G n) denote the maximum possible cardinality of a subset S of V n in which for every ordered pair (u1, u2,..., un) and (v1, v2,..., vn) of members of S there is some 1...
Bipartite subgraphs of integer weighted graphs (1998)
For every integer p> 0 let f(p) be the minimum possible value of the maximum weight of a cut in an integer weighted graph with total weight p. It is shown that for every large n and every m <...
On-line and off-line approximation algorithms for vector covering problems. Algorithmica (1998)
Noga Alon, Yossi Azar, János Csirik, Leah Epstein, Gerhard J. Woeginger
This paper deals with vector covering problems in d-dimensional space. The input to a vector covering problem consists of a set X of d-dimensional vectors in [0, 1] d. The goal is to partition X into...
Approximation schemes for scheduling on parallel machines (1998)
Noga Alon, Yossi Azar, Gerhard J. Woeginger, Tal Yadid
We discuss scheduling problems with m identical machines and n jobs where each job has to be assigned to some machine. The goal is to optimize objective functions that solely depend on the machine...
An asymptotic isoperimetric inequality (1998)
For a finite metric space V with a metric ρ, let V n be the metric space in which the distance between (a1,..., an) and (b1,..., bn) is the sum � n i=1 ρ(ai, bi). We obtain an asymptotic formula...
Packing and covering of dense graphs (1998)
Noga Alon, Yair Caro, Raphael Yuster
Let d be a positive integer. A graph G is called d-divisible if d divides the degree of each vertex of G. G is called nowhere d-divisible if no degree of a vertex of G is divisible by d. For a graph...
The choice number of random bipartite graphs, lecture at (1998)
Noga Alon, Michael Krivelevich
Abstract. A random bipartite graph G � n � n � p � is obtained by taking two disjoint subsets of vertices A and B of cardinality n each, and by connecting each pair of vertices a � A and b...
Approximation schemes for scheduling on parallel machines (1998)
Noga Alon, Yossi Azar, Gerhard J. Woeginger, Tal Yadid
We discuss scheduling problems with m identical machines and n jobs where each job has to be assigned to some machine. The goal is to optimize objective functions that solely depend on the machine...
On-line and off-line approximation algorithms for vector covering problems. Algorithmica (1998)
Noga Alon, Yossi Azar, J Anos Csirik, Leah Epstein, Sergey V. Sevastianov, ...
This paper deals with vector covering problems in d-dimensional space. The input to a vector covering problem consists of a set X of d-dimensional vectors in [0; 1] d. The goal is to partition X into...
The choice number of random bipartite graphs, lecture at (1998)
Noga Alon, Michael Krivelevich
A random bipartite graph G(n; n; p) is obtained by taking two disjoint subsets of vertices A and B of cardinality n each, and by connecting each pair of vertices a 2 A and b 2 B by an edge randomly...
Packing and covering of dense graphs (1998)
Noga Alon, Yair Caro, Raphael Yuster
Let d be a positive integer. A graph G is called d-divisible if d divides the degree of each vertex of G. G is called nowhere d-divisible if no degree of a vertex of G is divisible by d. For a graph...
Perfect Matchings in ε-Regular Graphs (1998)
Noga Alon, Vojtech Rödl, Andrzej Rucinski
Asuper(d, #)-regular graph on 2n vertices is a bipartite graph on the classes of vertices V 1 and V 2 , where |V 1 | = |V 2 | = n, in which the minimum degree and the maximum degree are between (d -...
A super (d; ffl)-regular graph on 2n vertices is a bipartite graph on the classes of vertices V 1 and V 2 , where jV 1 j = jV 2 j = n, in which the minimum degree and the maximum degree are between...
The Shannon Capacity of a union (1998)
For an undirected graph G = (V; E), let G n denote the graph whose vertex set is V n in which two distinct vertices (u 1 ; u 2 ; : : : ; un ) and (v 1 ; v 2 ; : : : ; v n ) are adjacent iff for all i...
On-line and Off-line Approximation Algorithms for Vector Covering Problems (1998)
Noga Alon, Janos Csirik, Sergey V. Sevastianov, Gerhard J. Woeginger
This paper deals with vector covering problems in d-dimensional space. The input to a vector covering problem consists of a set X of d-dimensional vectors in [0; 1] d . The goal is to partition X...
Bipartite Subgraphs and the Smallest Eigenvalue (1998)
Two results dealing with the relation between the smallest eigenvalue of a graph and its bipartite subgraphs are obtained. The first result is that the smallest eigenvalue of any nonbipartite graph...
Finding a Large Hidden Clique in a Random Graph (1998)
Noga Alon, Michael Krivelevich, Benny Sudakov
: We consider the following probabilistic model of a graph on n labeled vertices. Z. First choose a random graph Gn,1#2 , and then choose randomly a subset Q of vertices of size k and force it to be...
Coloring Graphs With Sparse Neighborhoods (1998)
By Noga Alon, Noga Alon, Michael Krivelevich, Benny Sudakov
It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d 2 =f is at...
Perfect Matchings in ε-Regular Graphs (1998)
Noga Alon, Vojtech Rödl, Andrzej Rucinski
A super (d; ffl)-regular graph on 2n vertices is a bipartite graph on the classes of vertices V 1 and V 2 , where jV 1 j = jV 2 j = n, in which the minimum degree and the maximum degree are between...
Noga Alon, Michael Krivelevich, Benny Sudakov
It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d 2 f is at...
The Shannon capacity of a union (1998)
For an undirected graph G = (V, E), let G n denote the graph whose vertex set is V n in which two distinct vertices (u1, u2,..., un) and (v1, v2,..., vn) are adjacent iff for all i between 1 and n...
A (homogeneous) d-interval is a union of d closed intervals in the line. Using topological methods, Tardos and Kaiser proved that for any finite collection of d-intervals that contains no k + 1...
Spectral Techniques in Graph Algorithms (1998)
The existence of efficient algorithms to compute the eigenvectors and eigenvalues of graphs supplies a useful tool for the design of various graph algorithms. In this survey we describe several...
Finding a large hidden clique in a random graph (1998)
Noga Alon, Michael Krivelevich, Benny Sudakov
ABSTRACT: We consider the following probabilistic model of a graph on n labeled vertices. First choose a random graph Gn,1�2 Ž., and then choose randomly a subset Q of vertices of size k and force...
Finding and counting given length cycles (1997)
Noga Alon, Raphael Yuster, Uri Zwick
We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the...
Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs (1997)
Let χ1(n) denote the maximum possible absolute value of an entry of the inverse of 1 ( an n by n invertible matrix with 0, 1 entries. It is proved that χ1(n) = n 2 +o(1))n. This solves a problem of...
Neighborly families of boxes and bipartite coverings, in: The Mathematics of Paul Erdős (1997)
Dedicated to Professor Paul Erdős on the occasion of his 80 th birthday A bipartite covering of order k of the complete graph Kn on n vertices is a collection of complete bipartite graphs so that...
Voigt: Choosability and fractional chromatic numbers (1997)
A graph G is (a, b)-choosable if for any assignment of a list of a colors to each of its vertices there is a subset of b colors of each list so that subsets corresponding to adjacent vertices are...
Anti-Hadamard matrices, coin weighing, threshold gates, and indecomposable hypergraphs (1997)
Let χ1(n) denote the maximum possible absolute value of an entry of the inverse of 1 ( an n by n invertible matrix with 0, 1 entries. It is proved that χ1(n) = n 2 +o(1))n. This solves a problem of...
Subgraphs with a large cochromatic number (1997)
Noga Alon, Michael Krivelevich, Benny Sudakov
The cochromatic number of a graph G = (V, E) is the smallest number of parts in a partition of V in which each part is either an independent set or induces a complete subgraph. We show that if the...
The concentration of the chromatic number of random graphs, Combinatorica 17 (1997)
Noga Alon, Michael Krivelevich
We prove that for every constant> 0 the chromatic number of the random graph G(n; p) with p = n
Subgraphs with a large cochromatic number (1997)
Noga Alon, Michael Krivelevich, Benny Sudakov
The cochromatic number of a graph G = (V; E) is the smallest number of parts in a partition of V in which each part is either an independent set or induces a complete subgraph. We show that if the...
Constructive bounds for a Ramsey-type problem (1997)
Noga Alon, Michael Krivelevich
For every xed integers r; s satisfying 2 r there exists some = (r; s)> 0 for which we construct explicitly an innite family of graphs H r;s;n, where H r;s;n has n vertices, contains no clique on s...
Finding and counting given length cycles (1997)
Noga Alon, Raphael Yuster, Uri Zwick
We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the...
Subgraphs with a Large Cochromatic Number (1997)
Noga Alon, Michael Krivelevich, Benny Sudakov
: The cochromatic number of a graph G =(V,E) is the smallest number of parts in a partition of V in which each part is either an independent set or induces a complete subgraph. We show that if the...
Approximation Schemes for Scheduling (1997)
Noga Alon, Yossi Azar, Gerhard J. Woeginger, Tal Yadid
We consider the classic scheduling/load balancing problems where there are m identical machines and n jobs, and each job should be assigned to some machine. Traditionally, the assignment of jobs to...
A Purely Combinatorial Proof of the Hadwiger Debrunner (p, q) Conjecture (1997)
Noga Alon, N. Alon, Daniel J. Kleitman
A family of sets has the (p; q) property if among any p members of the family some q have a nonempty intersection. The authors have proved that for every p q d + 1 there is a c = c(p; q; d) ! 1 such...
Scale-sensitive Dimensions, Uniform Convergence, and Learnability (1997)
Noga Alon, Shai Ben-david, David Haussler
Learnability in Valiant's PAC learning model has been shown to be strongly related to the existence of uniform laws of large numbers. These laws define a distribution-free convergence property...
Short Certificates for Tournaments (1997)
An isomorphism certificate of a labeled tournament T is a labeled subdigraph of T which together with an unlabeled copy of T allows the errorless reconstruction of T . It is shown that any tournament...
Constructive bounds for a Ramsey-type problem (1997)
Noga Alon, Michael Krivelevich
For every fixed integers r; s satisfying 2 r ! s there exists some ffl = ffl(r; s) ? 0 for which we construct explicitly an infinite family of graphs H r;s;n , where H r;s;n has n vertices, contains...
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos
Consider the set H of all linear (or affine) transformations between two vector spaces over a finite field F . We study how good H is as a class of hash functions, namely we consider hashing a set S...
Noga Alon, Michael Krivelevich, Benny Sudakov
The choice number of a graph G is the minimum integer k such that for every assignment of asetS(v) ofkcolors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a...
Subgraphs with a large cochromatic number (1997)
Noga Alon, Michael Krivelevich, Benny Sudakov
Abstract: The cochromatic number of a graph G =(V,E) is the smallest number of parts in a partition of V in which each part is either an independent set or induces a complete subgraph. We show that...
Small sample spaces with almost independent random variables are applied to design efficient sequential deterministic algorithms for two problems. The first algorithm, motivated by the attempt to...
The space complexity of approximating the frequency moments (1996)
Noga Alon, Yossi Matias, Mario Szegedy
The frequency moments of a sequence containing mi elements of type i, for 1 ≤ i ≤ n, are the numbers Fk = �n i=1 mki. We consider the space complexity of randomized algorithms that approximate...
Approximate hypergraph coloring, in (1996)
Noga Alon, Pierre Kelsen, Sanjeev Mahajan, Hariharan Ramesh
A coloring of a hypergraph is a mapping of vertices to colors such that no hyperedge is monochromatic. We are interested in the problem of coloring 2-colorable hypergraphs. For the special case of...
The geometry of coin-weighing problems, extended abstract for FOCS conference (1996)
Noga Alon, Dmitry N. Kozlov, Van H. Vu
Given a set of m coins out of a collection of coins of k unknown distinct weights, we wish to decide if all the m given coins have the same weight or not using the minimum possible number of...
2-factors in dense graphs (1996)
A conjecture of Sauer and Spencer states that any graph G on n vertices with minimum degree at least 2 3n contains any graph H on n vertices with maximum degree 2 or less. This conjecture is proven...
H-factors in dense graphs (1996)
The following asymptotic result is proved. For every fixed graph H with h vertices, any graph G with n vertices and with minimum degree d ≥ χ(H)−1 χ(H) n contains (1 − o(1))n/h vertex...
A linear time erasure-resilient code with nearly optimal recovery (1996)
We develop an efficient scheme that produces an encoding of a given message such that the message can be decoded from any portion of the encoding that is approximately equal to the length of the...
On k-saturated graphs with restrictions on the degrees (1996)
Noga Alon, Paul Erdős, Ron Holzman, Michael Krivelevich
A graph G is called k-saturated, where k ≥ 3 is an integer, if G is K k-free but the addition of any edge produces a K k (we denote by K k a complete graph on k vertices). We investigate...
H-factors in dense graphs (1996)
The following asymptotic result is proved. For every ɛ> 0, and for every positive integer h, there exists an n0 = n0(ɛ, h) such that for every graph H with h vertices and for every n> n0, any...
Noga Alon, C. Kenneth Fan, Daniel Kleitman, Jozsef Losonczy, Noga Alon, C. Kenneth Fan, ...
Abstract. The purpose of this note is to give a constuctive proof of a conjecture in [1] concerning the existence of acyclic matchings. 1. Main result Let B, D ⊂ Z n. Assume that |B | = |D | and 0...
Coins with arbitrary weights (1996)
Given a set of m coins out of a collection of coins of k unknown distinct weights, we wish to decide if all the m given coins have the same weight or not using the minimum possible number of...
The geometry of coin-weighing problems, extended abstract for FOCS conference (1996)
Noga Alon, Dmitry N. Kozlov, Van H. Vu
Given a set of m coins out of a collection of coins of k unknown distinct weights, we wish to decide if all the m given coins have the same weight or not using the minimum possible number of...
A linear time erasure-resilient code with nearly optimal recovery (1996)
We develop an efficient scheme that produces an encoding of a given message such that the message can be decoded from any portion of the encoding that is approximately equal to the length of the...
H-factors in dense graphs (1996)
The following asymptotic result is proved. For every fixed graph H with h vertices, any graph G with n vertices and with minimum degree d (H)\Gamma1
2-factors in Dense Graphs (1996)
A conjecture of Sauer and Spencer states that any graph G on n vertices with minimum degree at least 2 3 n contains any graph H on n vertices with maximum degree 2 or less. This conjecture is proven...
It is shown that there exists a positive c so that for any large integer m, any graph with 2m 2 edges contains a bipartite subgraph with at least m 2 + m=2 + c p m edges. This is tight up to the...
Noga Alon, C. Kenneth Fan, Daniel Kleitman, Jozsef Losonczy, Let B
: The purpose of this note is to give a constructive proof of a conjecture in Fan and Losonczy (1996) concerning the existence of acyclic matchings. The rst and third authors were supported in part...
Derandomized Graph Products (1996)
Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman
Berman and Schnitger [10] gave a randomized reduction from approximating MAXSNP problems [24] within constant factors arbitrarily close to 1 to approximating clique within a factor of n^ε...
The Space Complexity of Approximating the Frequency Moments (1996)
Noga Alon, Yossi Matias, Mario Szegedy
The frequency moments of a sequence containing m i elements of type i, for 1 i n, are the numbers Fk = P n i=1 m k i . We consider the space complexity of randomized algorithms that approximate the...
Short certificates for tournaments (1996)
An isomorphism certificate of a labeled tournament T is a labeled subdigraph of T which together with an unlabeled copy of T allows the errorless reconstruction of T. It is shown that any tournament...
It is shown that there exists a positive c so that for any large integer m, any graph with 2m 2 edges contains a bipartite subgraph with at least m 2 + m/2 + c √ m edges. This is tight up to the...
Improved parallel approximation of a class of integer programming problems (1995)
We present a method to derandomize RNC algorithms, converting them to NC algorithms. Using it, we show how to approximate a class of NP-hard integer programming problems in NC, to within factors...
Dynamic-Resharing Verifiable Secret Sharing against Mobile Adversary (1995)
Noga Alon, Zvi Galil, Moti Yung
We present a novel efficient variant of Verifiable Secret Sharing (VSS) where the dealing of shares is dynamically refreshed (without changing or corrupting the secret) against the threat of the...
The 123 Theorem and its extensions (1995)
It is shown that for every b> a> 0 and for every two independent identically distributed real random variables X and Y P rob[|X − Y | ≤ b] < (2⌈b/a ⌉ − 1)P rob[|X − Y | ≤ a]....
Tough Ramsey graphs without short cycles (1995)
A graph G is t-tough if any induced subgraph of it with x> 1 connected components is obtained from G by deleting at least tx vertices. It is shown that for every t and g there are t-tough graphs...
A note on network reliability (1995)
Let G = (V, E) be a loopless undirected multigraph, with a probability pe, 0 ≤ pe ≤ 1 assigned to every edge e ∈ E. Let Gp be the random subgraph of G obtained by deleting each edge e of G,...
Linear Time Erasure Codes With Nearly Optimal Recovery (1995)
Noga Alon, Jeff Edmonds, Michael Luby
An (n, c, ℓ, r)-erasure code consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm produces a set of ℓ-bit packets of total length cn...
On a problem of Erdős and Turán and some related results (1995)
Noga Alon, Mihail N. Kolountzakis
We employ the probabilistic method to prove a stronger version of a result of Helm, related to a conjecture of Erdős and Turán about additive bases of the positive integers. We show that for a...
Repeated communication and Ramsey graphs (1995)
e study the savings afforded by repeated use in two zero-error communication problems. e show that for some random sources, communicating one instance requires arbitrarily-many bits, but...
Polynomial time randomised approximation schemes for the Tutte polynomial of dense graphs (1995)
Noga Alon, Alan Frieze, Dominic Welsh
The Tutte-Grothendieck 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...
Repeated Communication and Ramsey Graphs (1995)
We study the savings afforded by repeated use in two zero-error communication problems. We show that for some random sources, communicating one instance requires arbitrarily-many bits, but...
A Graph-Theoretic Game and its Application to the k-Server Problem (1995)
Noga Alon, Richard M. Karp, David Peleg, Douglas West
This paper investigates a zero-sum game played on a weighted connected graph G between two players, the tree player and the edge player. At each play, the tree player chooses a spanning tree T and...
Noga Alon, Raphy Yuster, Uri Zwick
We describe a novel randomized method, the method of 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...
Proof Of The Alternating Sign Matrix Conjecture (1995)
Doron Zeilberger, Gert Almkvist, Noga Alon, George Andrews, Dror Bar-natan, Francois Bergeron, ...
: The number of n n matrices whose entries are either -1, 0, or 1, whose row- and column- sums are all 1, and such that in every row and every column the non-zero entries alternate in sign, is proved...
Linear Time Erasure Codes with Nearly Optimal Recovery (1995)
Noga Alon, Jeff Edmonds, Michael Luby
) Noga Alon Jeff Edmonds y Michael Luby z Abstract An (n; c; `; r)-erasure code consists of an encoding algorithm and a decoding algorithm with the following properties. The encoding algorithm...
Epsilon-Discrepancy Sets And Their Applications For Interpolation Of Sparse Polynomials (1995)
We present a simple explicit construction of a probability distribution supported on (p \Gamma 1) 2 vectors in Z n p , where p n=" is a prime, for which the absolute value of each nontrivial...
On a problem of Erdös and Turán and some related results (1995)
Noga Alon, Mihail N. Kolountzakis
We employ the probabilistic method to prove a stronger version of a result of Helm, related to a conjecture of Erdos and Tur'an about additive bases of the positive integers. We show that for a...
Repeated Communication and Ramsey Graphs (1995)
We study the savings afforded by repeated use in two zero-error communication problems. We show that for some random sources, communicating one instance requires arbitrarily-many bits, but...
Noga Alon, Alan Frieze, Dominic Welsh
The Tutte-Grothendieck 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...
Source Coding and Graph Entropies (1995)
A sender wants to accurately convey information to a receiver who has some, possibly related, data. We study the expected number of bits the sender must transmit for one and for multiple instances in...
Derandomized Graph Products (1995)
Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman
. Berman and Schnitger gave a randomized reduction from approximating MAX-SNP problems within constant factors arbitrarily close to 1 to approximating clique within a factor of n ffl (for some ffl)....
Approximating the Independence Number Via the Theta-Function (1995)
We describe an approximation algorithm for the independence number of a graph. If a graph on n vertices has an independence number n=k + m for some fixed integer k 3 and some m ? 0, the algorithm...
Finding and Counting Given Length Cycles (1995)
Noga Alon, Raphael Yuster, Uri Zwick
We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the...
The 123 Theorem and its extensions (1995)
Noga Alon And, Noga Alon, Raphael Yuster
It is shown that for every b ? a ? 0 and for every two independent identically distributed real random variables X and Y P rob[jX \Gamma Y j b] ! (2db=ae \Gamma 1)P rob[jX \Gamma Y j a]: This is...
On the discrepancy of combinatorial rectangles (1995)
Abstract. Let B d n denote the family which consists of all subsets S1 × · · · × Sd, where Si ⊆ [n], and Si � = ∅, for i = 1,..., d. We compute the L2–discrepancy of B d n and give...
Repeated communication and Ramsey graphs (1995)
We study the savings afforded by repeated use in two zero-error communication problems. We show that for some random sources, communicating one instance requires arbitrarily-many bits, but...
A lattice point problem and additive number theory (1995)
For every dimension d ≥ 1 there exists a constant c = c(d) such that for all n ≥ 1, every set of at least cn lattice points in the d-dimensional Euclidean space contains a subset of car-dinality...
Derandomized Graph Products (1995)
Noga Alon, Uriel Feige, Avi Wigderson, David Zuckerman
Berman and Schnitger [10] gave a randomized reduction from approximating MAX-SNP problems [24] within constant factors arbitrarily close to 1 to approximating clique within a factor of n ɛ (for some...
On the discrepancy of combinatorial rectangles (1995)
Abstract. Let B d n denote the family which consists of all subsets S1 × · · · × Sd, where Si ⊆ [n], and Si � = ∅, for i = 1,..., d. We compute the L2–discrepancy of B d n and give...
Packing of partial designs (1994)
We say that two hypergraphs H1 and H2 with v vertices each can be packed if there are edge disjoint hypergraphs H ′ 1 and H ′ 2 on the same set V of v vertices, where H ′ i is isomorphic to Hi....
Noga Alon, Raphael Yuster, Uri Zwick
We describe a novel randomized method, the method of 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...
Subdivided graphs have linear Ramsey numbers (1994)
It is shown that the Ramsey number of any graph with n vertices in which no two vertices of degree at least 3 are adjacent is at most 12n. In particular, the above estimate holds for the Ramsey...
Probabilistic methods in coloring and decomposition problems (1994)
Numerous problems in Graph Theory and Combinatorics can be formulated in terms of the existence of certain colorings of graphs or hypergraphs. Many of these problems can be solved or partially solved...
Routing Permutations on Graphs via Matchings (1994)
We consider a class of routing problems on connected graphs G. Initially, each vertex v of G is occupied by a “pebble ” which has a unique destination π(v) in G (so that π is a permutation of...
A spectral technique for coloring random 3-colorable graphs (1994)
Abstract. Let G3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of...
Random cayley graphs and expanders (1994)
For every 1> δ> 0 there exists a c = c(δ)> 0 such that for every group G of order n, and for a set S of c(δ) log n random elements in the group, the expected value of the second largest...
Random cayley graphs and expanders (1994)
For every 1? ffi? 0 there exists a c = c(ffi) ? 0 such that for every group G of order n, and for a set S of c(ffi) log n random elements in the group, the expected value of the second largest...
A spectral technique for coloring random 3-colorable graphs (1994)
Abstract. Let G 3n,p,3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes, and then choose every pair of...
Approximating the Independence Number Via the Theta-Function (1994)
Abstract We study the relationship between the independence number of a graph and its semi-definite relaxation, the Lov'asz `-function. We deduce an improved approximation algorithm for the...
Explicit Ramsey graphs and orthonormal labelings (1994)
Noga Alon Submitted, Noga Alon
We describe an explicit construction of triangle-free graphs with no independent sets of size m and with\Omega\Gamma m 3=2 ) vertices, improving a sequence of previous constructions by various...
Explicit Ramsey graphs and orthonormal labelings (1994)
We describe an explicit construction of triangle-free graphs with no independent sets of size m and with\Omega\Gamma m 3=2 ) vertices, improving a sequence of previous constructions by various...
Matching Nuts and Bolts (Extended Abstract) (1994)
Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky
) Noga Alon y Manuel Blum z Amos Fiat x Sampath Kannan -- Moni Naor k Rafail Ostrovsky Abstract We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of...
Dominic Welsh Received, Noga Alon, Dominic Welsh
. The Tutte-Grothendieck 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...
Explicit Ramsey graphs and orthonormal labelings (1994)
We describe an explicit construction of triangle-free graphs with no independent sets of size man dwith#( m 3/2 ) vertices, improving a sequence of previous constructions by various authors. As a...
Repeated Communication and Ramsey Graphs (1994)
We study the savings afforded by repeated use in two zero-error communication problems. Channel coding: We show that some channels can communicate exponentially more bits in two uses than they can in...
Linear Extensions Of A Random Partial Order (1994)
Noga Alon, Béla Bollobás, Graham Brightwell, Svante Janson
. We study asymptotics of the number of linear extensions of the random Gn;p partial order, where p is fixed and n !1. In particular, it is shown that the distribution is asymptotically log-normal....
Matching Nuts and Bolts (1994)
Noga Alon, Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor, Rafail Ostrovsky
) Noga Alon Manuel Blum y Amos Fiat z Sampath Kannan x Moni Naor -- Rafail Ostrovsky k Abstract We describe a procedure which may be helpful to any disorganized carpenter who has a mixed pile of...
A Spectral Technique for Coloring Random 3-Colorable Graphs (1994)
Let G 3n;p;3 be a random 3-colorable graph on a set of 3n vertices generated as follows. First, split the vertices arbitrarily into three equal color classes and then choose every pair of vertices of...
Small sample spaces with almost independent random variables are applied to design efficient sequential deterministic algorithms for two problems. The first algorithm, motivated by the attempt to...
Extended Abstract, Noga Alon, Raphy Yuster, Uri Zwick
Noga Alon yz Institute for Advanced Study and Tel Aviv University Raphy Yuster Uri Zwick Tel Aviv University Abstract We describe a novel randomized method, the method of color-coding for nding...
Restricted colorings of graphs (1993)
The problem of properly coloring the vertices (or edges) of a graph using for each vertex (or edge) a color from a prescribed list of permissible colors, received a considerable amount of attention....
A disjoint system of type (∀, ∃, k, n) is a collection C = {A1,..., Am} of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered pair...
Coin-flipping games immune against linear-sized coalitions (1993)
Perfect information coin-flipping and leader-election games arise naturally in the study of fault toler-ant distributed computing and have been con-sidered in many different scenarios. Answering a...
Zero-sum sets of prescribed size (1993)
Erdős, Ginzburg and Ziv proved that any sequence of 2n−1 integers contains a subsequence of cardinality n the sum of whose elements is divisible by n. We present several proofs of this result,...
Can Visibility Graphs Be Represented Compactly? (1993)
Pankaj K. Agarwal, Pankaj K. Agarwal, Noga Alon, Noga Alon, Boris Aronov, Boris Aronov, ...
We consider the problem of representing the visibility graph of line segments as a union of cliques and bipartite cliques. Given a graph G, a family G = fG 1 ; G 2 ; : : : ; G k g is called a clique...
A disjoint system of type (8; 9; k; n) is a collection C = fA 1 ; : : : ; Am g of pairwise disjoint families of k-subsets of an n-element set satisfying the following condition. For every ordered...
Matching Nuts and Bolts (1993)
Exte Nd Ed, Noga Alon, Manuel Blum, Sampath Kannan, Moni Naor, Rafail Ostrovsky
) Noga Alon y Manuel Blum z Amos Fiat x Sampath Kannan -- Moni Naor k Rafail Ostrovsky TR-93-075 Novemeber, 1993 Abstract We describe a procedure which may be helpful to any disorganized carpenter...
On-line Steiner Trees in the Euclidean Plane (1993)
Suppose we are given a sequence of n points in the Euclidean plane, and our objective is to construct, on-line, a connected graph that connects all of them, trying to minimize the total sum of...
Coin-flipping games immune against linear-sized coalitions (1993)
Perfect information coin-flipping and leader-election games arise naturally in the study of fault tolerant distributed computing and have been considered in many different scenarios. Answering a...
On-line Steiner trees in the Euclidean plane (1993)
Suppose we are given a sequence of n points in the Euclidean plane, and our objective is to construct, on-line, a connected graph that connects all of them, trying to minimize the total sum of...
Alon, Noga, Kleitman, Daniel J.
A family of sets has the $(p,q)$ property if among any $p$ members of the family some $q$ have a nonempty intersection. It is shown that for every $p\ge q\ge d+1$ there is a $c=c(p,q,d)
Alon, Noga, Bruck, Jehoshua, Naor, Joseph, Naor, Moni, Roth, Ron M.
A novel technique, based on the pseudo-random properties of certain graphs known as expanders, is used to obtain novel simple explicit constructions of asymptotically good codes. In one of the...
Spanning subgraphs of random graphs, Research problems, Graphs and Combin (1992)
We propose a problem concerning the determination of the threshold function for the edge probability that guarantees, almost surely, the existence of various sparse spanning subgraphs in random...
Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (1992)
Noga Alon, Gil Kalai, Moty Ricklin, Larry Stockmeyer
1 We prove a lower bound of Ω(log n / log log n) on the competitive ratio of any (deterministic or randomized) distributed algorithm for solving the mobile user problem introduced by Awerbuch and...
Simple Constructions of Almost k-wise Independent Random Variables (1992)
Noga Alon, Oded Goldreich, René Peralta
We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is...
Choice numbers of graphs; a probabilistic approach (1992)
The choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v...
Point selections and weak ε-nets for convex hulls (1992)
Noga Alon, Imre Bárány, Cowles Foundation
Abstract. One of our results: Let X be a finite set on the plane, 0 < ε < 1. Then there exists a set F (a weak ε-net) of size at most 7/ε 2 such that every convex set containing at least...
Noga Alon, Edward R. Scheinerman
Harary [8] calls a finite, simple graph G a sum graph if one can assign to each vi ∈ V (G) a label xi so that {vi, vj} ∈ E(G) iff xi + xj = xk for some k. We generalize this notion by replacing...
Simple Constructions of Almost k-wise Independent Random Variables (1992)
Noga Alon, Oded Goldreich, Johan Håstad, René Peralta
We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is...
Comparison-Sorting and Selecting in Totally Monotone Matrices (1992)
An m \Theta n matrix A is called totally monotone if for all i 1 ! i 2 and j1 ! j2 , A[i1 ; j1 ] ? A[i1 ; j2 ] implies A[i2 ; j1 ] ? A[i2 ; j2 ]. We consider the complexity of comparison-based...
Noga Alon, Jehoshua Bruck, Joseph Naor, Moni Naor, Ron M. Roth
A new technique, based on the pseudo-random properties of certain graphs, known as expanders, is used to obtain new simple explicit constructions of asymptotically good codes. In one of the...
Alon, Noga, Bruck, Jehoshua, Naor, Joseph, Naor, Moni, Roth, Ron M.
A new technique, based on the pseudo-random properties of certain graphs, known as expanders, is used to obtain new simple explicit constructions of asymptotically good codes.
A parallel algorithmic version of the local lemma (1991)
The Lovász Local Lemma is a tool that enables one to show that certain events hold with pos-itive, though very small probability. It often yields existence proofs of results without supplying any...
Probabilistic Methods in Extremal Finite Set Theory (1991)
There are many known applications of the Probabilistic Method in Extremal Finite Set Theory. In this paper we describe several examples, demonstrating some of the techniques used and illustrating...
Multicolored forests in bipartite decompositions of graphs (1991)
Noga Alon, Richard A. Brualdi, Bryan L. Shader
We show that in any edge-coloring of the complete graph Kn on n vertices, such that each color class forms a complete bipartite graph, there is a spanning tree of Kn no two of whose edges have the...
A Graph-Theoretic Game and its Application to the k-Server Problem (Extended Abstract) (1991)
Noga Alon, Richard M. Karp, David Peleg
) Noga Alon Richard M. Karp y David Peleg z Douglas West x July 11, 1991 Abstract This paper investigates a zero-sum game played on a weighted connected graph G between two players, the tree player...
Generating pseudo-random permutations and maximum flow algorithms (1990)
We describe a simple construction of a family of permutations with a certain pseudo-random property. Such a family can be used to derandomize a recent randomized maximum-flow al-gorithm of Cheriyan...
Parallel linear programming in fixed dimension almost surely in constant time (1990)
Abstract. For any xed dimension d, the linear programming problem with n inequality constraints can be solved on a probabilistic CRCW PRAM with O(n) processors almost surely in constant time. The...
Non-constructive proofs in combinatorics (1990)
One of the main reasons for the fast development of Combinatorics during the recent years is certainly the widely used application of combinatorial methods in the study and the development of...
A separator theorem for graphs with an excluded minor and its applications (1990)
Noga Alon, Paul Seymour, Robin Thomas
Let G be an n-vertex graph with nonnegative weights whose sum is 1 assigned to its vertices, and with no minor isomorphic to a given h-vertex graph H. We prove that there is a set X of no more than h...
Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time (1990)
. For any fixed dimension d, the linear programming problem with n inequality constraints can be solved on a probabilistic CRCW PRAM with O(n) processors almost surely in constant time. The algorithm...
The maximum number of hamiltonian paths in tournaments. Combinatorica 10 (1990)
Ilan Adler, Noga Alon, Sheldon M. Ross
By using the probabilistic method, we show that the maximum number of directed Hamiltonian paths in a complete directed graph with n vertices is at least (e − o(1)) n! 2 n−1. 1
The maximum number of hamiltonian paths in tournaments. Combinatorica 10 (1990)
Solving an old conjecture of Szele we show that the maximum number of directed Hamiltonian paths in a tournament on n vertices is at most c · n 3/2 · n! 2 n−1, where c is a positive constant...
Degrees of freedom versus dimension for containment orders, Order 5 (1988)
Noga Alon, Edward R. Scheinerman
Given a family of sets S, where the sets in S admit k ‘degrees of freedom’, we prove that not all (k + 1)-dimensional posets are containment posets of sets in S. Our results depend on the...
Optimal preprocessing for answering on-line product queries (1987)
We examine the amount of preprocessing needed for answering certain on-line queries as fast as possible. We start with the following basic problem. Suppose we are given a semigroup (S,°). Let s...
Universality and Tolerance at the Turn of the Millennium (1985)
Noga Alon, Michael Capalbo, Yoshiharu Kohayakawa, Vojtech Rodl, Andrzej Rucinski, Endre Szemeredi
) Noga Alon Michael Capalbo y Yoshiharu Kohayakawa z Vojtech Rodl x Andrzej Rucinski { Endre Szemeredi k Abstract For every r 2 and n > n 0 (r), we construct explicitly a graph on n vertices with...
Refining the Graph Density Condition for the Existence of Almost K-factors
Alon and Yuster [4] have proven that if a fixed graph K on g vertices is (h + 1)-colorable, then any graph G with n vertices and minimum degree at least h h+1 n contains at least (1 \Gamma ffl) n g...
The Polynomial Method and Restricted Sums of Congruence Classes
Noga Alon, Melvyn B. Nathanson, Imre Z. Ruzsa
We present a simple and general algebraic technique for obtaining results in Additive Number Theory, and apply it to derive various new extensions of the Cauchy-Davenport Theorem. In particular we...
Efficient Testing of Large Graphs
Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy
Let P be a property of graphs. An ffl-test for P is a randomized algorithm which, given the ability to make queries whether a desired pair of vertices of an input graph G with n vertices are adjacent...
List Coloring of Random and Pseudo-Random Graphs
Noga Alon, Michael Krivelevich, Benny Sudakov
The choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v...
Coloring Graphs with Sparse Neighborhoods
Noga Alon, Michael Krivelevich, Benny Sudakov
It is shown that the chromatic number of any graph with maximum degree d in which the number of edges in the induced subgraph on the set of all neighbors of any vertex does not exceed d 2 =f is at...
On the Discrepancy of Combinatorial Rectangles
Noga Alon, Benjamin Doerr, Tomasz Luczak, Tomasz Schoen
Let B n denote the family which consists of all subsets S 1 S d , where S i [n], and S i 6= ;, for i = 1; : : : ; d. We n and give estimates for the L p { discrepancy of B n for 1 p 1. 1.
Maximum Cuts and Judicious Partitions in Graphs without Short Cycles
Noga Alon, Bela Bollobas, Michael Krivelevich, Benny Sudakov
We consider the bipartite cut and the judicious partition problems in graphs of girth at least 4. For the bipartite cut problem we show that every graph G with m edges, whose shortest cycle has...
This document in subdirectoryRS/97/16/ Linear Hashing
Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gábor Tardos, Noga Alon, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...
List Coloring of Random and Pseudo-Random Graphs
Noga Alon, Michael Krivelevich, Benny Sudakov
The choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v...
Biomolecular network motif counting and discovery by color coding
Alon, Noga, Dao, Phuong, Hajirasouliha, Iman, Hormozdiari, Fereydoun, Sahinalp, S. Cenk
Protein–protein interaction (PPI) networks of many organisms share global topological features such as degree distribution, k-hop reachability, betweenness and closeness. Yet, some of these...