Ehud Friedgut

CENTER FOR THE STUDY (2008)

reasonable to assume that most mathematicians would be puzzled to find these three terms as, say, key words for the same mathematical paper. (Just in case this puzzlement is a result of being...

Ehud Friedgut, Gil Kalai, Noam Nisan, Ehud Friedgut, Gil Kalai, Noam Nisan

The Gibbard-Satterthwaite theorem states that every non-trivial voting method between at least 3 alternatives can be strategically manipulated. We prove a quantitative version of the...

On the Number of Hamiltonian Cycles in a Tournament, preprint (2007)

Ehud Friedgut, Je Kahn

Let P (n) and C(n) denote, respectively, the maximum possible numbers of Hamiltonian paths and Hamiltonian cycles in a tournament on n vertices. The study of P (n) was suggested by Szele [14], who...

Sharp thresholds for certain Ramsey properties of random graphs (2007)

Ehud Friedgut, Michael Krivelevich

In a series of papers culminating in [11] Rodl, Rucinski and others study the thresholds of Ramsey properties of random graphs i.e. for a given graph H, when does a random graph almost surely have...

Sharp Thresholds for Ramsey Properties of Random Graphs. (2007)

Ehud Friedgut, Michael Krivelevich

In a series of papers culminating in [11] Rodl, Ruci'nski and others study the thresholds of Ramsey properties of random graphs and hypergraphs, i.e. for a given graph H, when does a random...

Let Vn (p) = f0; 1g n (2007)

Ehud Friedgut, Gil Kalai

Abstract. In their seminal work which initiated random graph theory Erdos and R'enyi discovered that many graph properties have sharp thresholds as the number of vertices tends to infinity. We...

Boolean Functions With Low Average Sensitivity (2007)

Depend On Few, Ehud Friedgut

f0; 1g. The sensitivity of a point v 2 f0; 1g ) = 1gj, i.e. the number of neighbors of the point in the discrete cube on which the value of f differs. The average sensitivity of f is the average of...

Hypergraphs, Entropy, and Inequalities (2007)

Intersecting families are essentially contained in juntas (2007)

this paper we wish to point out a common underlying information-theoretic theme that can be found in many well-known inequalities. The formulation of this principle is combinatorial and follows from...

Irit Dinur, Ehud Friedgut

A family J of subsets of {1,..., n} is called a j-junta if there exists J ⊆ {1,..., n}, with |J | = j, such that the membership of a set S in J depends only on S ∩ J. In this paper we provide a...

Intersecting families are essentially contained in juntas (2007)

Irit Dinur, Ehud Friedgut

A family J of subsets of {1,..., n} is called a j-junta if there exists J ⊆ {1,..., n}, with |J | = j, such that the membership of a set S in J depends only on S ∩ J. In this paper we provide a...

Abstract (2006)

Irit Dinur, Guy Kindler, Ehud Friedgut

A theorem of Bourgain [4] on Fourier tails states that if f: {−1, 1} n → {−1, 1} is a booleanvalued function on the discrete cube such that for any k> 0, |S|>k ˆf(S) 2 < k...

Independent sets in graph powers are almost contained in juntas (2006)

Irit Dinur, Ehud Friedgut, Oded Regev

Let G = (V, E) be a simple undirected graph. Define G n, the n-th power of G, as the graph on the vertex set V n in which two vertices (u1,..., un) and (v1,..., vn) are adjacent if and only if ui is...

On the Fourier tails of bounded functions over the discrete cube. Manuscript (2006)

Independent sets in graph powers are almost contained in juntas (2006)

In this paper we consider bounded real-valued functions over the discrete cube, f: {−1, 1} n → [−1, 1]. Such functions arise naturally in theoretical computer science, combinatorics, and the...

Irit Dinur, Ehud Friedgut, Oded Regev

Let G = (V, E) be a simple undirected graph. Define G n, the n-th power of G, as the graph on the vertex set V n in which two vertices (u1,..., un) and (v1,..., vn) are adjacent if and only if ui is...

On the Fourier tails of bounded functions over the discrete cube. Manuscript (2006)

On the Fourier tails of bounded functions over the discrete cube. Manuscript (2006)

In this paper we consider the class of bounded functions over the discrete cube, f: {−1, 1} n → [−1, 1]. Such functions arise naturally in theoretical computer science, combinatorics, and the...

Independent sets in graph powers are almost contained in juntas (2006)

In this paper we consider bounded real-valued functions over the discrete cube, f: {−1,1} n → [−1,1]. Such functions arise naturally in theoretical computer science, combinatorics, and the...

Irit Dinur, Ehud Friedgut, Oded Regev

Let G = (V, E) be a simple undirected graph. Define G n, the n-th power of G, as the graph on the vertex set V n in which two vertices (u1,..., un) and (v1,..., vn) are adjacent if and only if ui is...

On the Fourier tails of bounded functions over the discrete cube. Manuscript (2006)

On the Fourier tails of bounded functions over the discrete cube. Manuscript (2006)

In this paper we present a sufficient condition for a bounded function f: {−1, 1} n → R to be approximable by a function which depends on few coordinates. The condition is that the Fourier...

Hunting for Sharp Thresholds (2005)

In this paper we consider bounded real-valued functions over the discrete cube, f: {−1, 1} n → [−1, 1]. Such functions arise naturally in theoretical computer science, combinatorics, and the...

Graph products, fourier analysis and spectral techniques (2004)

A basic phenomenon in random structures such as random graphs is the threshold phenomenon, where a system undergos a swift qualitative change as result of a small change in a parameter guiding its...

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

Büchi Complementation Made Tighter (2004)

Ehud Friedgut, Orna Kupferman, Moshe Vardi

The complementation problem for nondeterministic word automata has numerous applications in formal verification. In particular, the language-containment problem, to which many verification problems...

Büchi Complementation Made Tighter (2004)

Ehud Friedgut, Orna Kupferman, Moshe Y. Vardi

The complementation problem for nondeterministic word automata has numerous applications in formal verification. In particular, the language-containment problem, to which many verification problems...

A sharp threshold for random graphs with a monochromatic triangle in every edge coloring (2003)

Friedgut, Ehud, Rodl, Vojtech, Rucinski, Andrzej, Tetali, Prasad

Let $\R$ be the set of all finite graphs $G$ with the Ramsey property that every coloring of the edges of $G$ by two colors yields a monochromatic triangle. In this paper we establish a sharp...

Ramsey games against a one-armed bandit (2003)

Ehud Friedgut, Yoshiharu Kohayakawa, Vojtech Rödl, Andrzej Ruciński, Prasad Tetali

We study the following one-person game against a random graph: the Player's goal is to 2-colour a random sequence of edges e1, e2,... of a complete graph on n vertices, avoiding a monochromatic...

A Sharp Threshold for Random Graphs with a Monochromatic Triangle in Every Edge Coloring (2003)

Ehud Friedgut, Vojtech Rödl, Andrzej Rucinski, Prasad Tetali

Let R be the set of all nite graphs G with the Ramsey property that every coloring of the edges of G by two colors yields a monochromatic triangle. In this paper we establish a sharp threshold for...

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

A sharp threshold for random graphs with monochromatic triangle (2002)

Ehud Friedgut, Vojtech Rödl, Andrzej Ruciński, Prasad Tetali

Let R be the set of all finite graphs G with the Ramsey property that every coloring of the edges of G by two colors yields a monochromatic triangle. In this paper we establish a sharp threshold for...

Computing Graph Properties By Randomized Subcube Partitions (2002)

Ehud Friedgut, Jeff Kahn, Avi Wigderson

We prove a new lower bound on the randomized decision tree complexity of monotone graph properties. For a monotone property A of graphs on n vertices, let p = p(A) denote the threshold probability of...

Computing Graph Properties by Randomized Subcube Partitions (2002)

Ehud Friedgut, Jeff Kahn, Avi Wigderson

We prove a new lower bound on the randomized decision tree complexity of monotone graph properties. For a monotone property A of graphs on n vertices, let p = p(A) denote the threshold probability of...

Boolean Functions whose Fourier Transform is Concentrated on the First Two Levels (2001)

Ehud Friedgut, Gil Kalai, Assaf Naor

In this note we describe Boolean functions f(x 1 ; x 2 ; : : : ; xn ) whose Fourier coecients are concentrated on the lowest two levels. We show that such a function is close to a constant function...

Proof of a Hypercontractive Estimate via Entropy (2001)

Ehud Friedgut, Vojtech Rödl, Let T (f

with the uniform (=product) measure.

On the number of permutations avoiding a given pattern (1999)

Noga Alon, Ehud Friedgut

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

A sharp threshold for k-colorability (1999)

Sharp thresholds of graph properties, and the k-sat problem (1999)

Let k be a fixed integer and f k (n; p) denote the probability that the random graph G(n; p) is k-colorable. We show that for every k 3, there exists d k (n) such that for any ffl? 0, lim n!1 f k (n;...

On the number of permutations avoiding a given pattern (1999)

Given a monotone graph property P, consider p (P), the probability that a random graph with edge probability p will have P. The function d p (P)=dp is the key to understanding the threshold behavior...

Noga Alon, Ehud Friedgut

Let oe 2 S k and 2 S n be permutations. We say contains oe if there exist

Sharp thresholds of graph properties, and the k-sat problem (1999)

Ehud Friedgut, Jean Bourgain

Consider G(n, p) to be the probability space of random graphs on n vertices with edge probability p. We will be considering subsets of this space defined by monotone graph properties. A monotone...

A Sharp (1997)

A Sharp Threshold for k-Colorability (1997)

ABSTRACT: Let k be a fixed integer and f Ž n, p. k denote the probability that the random graph Gn, Ž p. is k-colorable. We show that for k�3, there exists d Ž n. k such that for any ��0, ž...

A Sharp Threshold for k-Colorability (1997)

Let k be a xed integer and f k (n; p) denote the probability that the random graph G(n; p) is k-colorable. We show that for k 3, there exists d k (n) such that for any > 0, lim n!1 f k (n; d k (n)...

Every monotone graph property has a sharp threshold (1996)

Let f k (n; p) denote the probability that the random graph G(n; p) is k-colorable. We show that for every k 3, there exists d k (n) such that for any ffl ? 0, lim n!1 f k (n; d k (n) \Gamma ffl n )...

Ehud Friedgut, Gil Kalai

Abstract. In their seminal work which initiated random graph theory Erdös and Rényi discovered that many graph properties have sharp thresholds as the number of vertices tends to infinity. We prove...

Pricing congestible network resources (1995)

Ehud Friedgut, Jeff Kahn

another

Elections Can be Manipulated Often

Ehud Friedgut, Gil Kalai, Noam Nisan

The Gibbard-Satterthwaite theorem states that every non-trivial voting method between at least 3 alternatives can be strategically manipulated. We prove a quantitative version of the...

Elections Can be Manipulated Often

Ehud Friedgut, Gil Kalai, Noam Nisan

Elections Can be Manipulated Often

Ehud Friedgut, Gil Kalai, Noam Nisan

Influences in Product Spaces: KKL and BKKKL Revisited