Jeff Kahn 0001

FOCS Conference 2000 Conference Paper

The Cover Time, the Blanket Time, and the Matthews Bound

• Jeff Kahn 0001
• Jeong Han Kim
• László Lovász 0001
• Van H. Vu

We prove upper and lower bounds and give an approximation algorithm for the cover time of the random walk on a graph. We introduce a parameter M motivated by the well-known Matthews bounds (P. Matthews, 1988) on the cover time, C, and prove that M/2<C= O(M(lnlnn)/sup 2/). We give a deterministic-polynomial time algorithm to approximate M within a factor of 2; this then approximates C within a factor of O((lnlnn)/sup 2/), improving the previous bound O(lnn) due to Matthews. The blanket time B was introduced by P. Winkler and D. Zuckerman (1996): it is the expectation of the first time when all vertices are visited within a constant factor of the number of times suggested by the stationary distribution. Obviously C/spl les/B. Winkler and Zuckerman conjectured B=O(C) and proved B=O(Clnn). Our bounds above are also valid for the blanket time, and so it follows that B=O(C(lnlnn)/sup 2/).

STOC Conference 1992 Conference Paper

Entropy and Sorting

• Jeff Kahn 0001
• Jeong Han Kim

STOC Conference 1989 Conference Paper

On the Second Eigenvalue in Random Regular Graphs

• Joel Friedman
• Jeff Kahn 0001
• Endre Szemerédi

FOCS Conference 1988 Conference Paper

The Influence of Variables on Boolean Functions (Extended Abstract)

• Jeff Kahn 0001
• Gil Kalai
• Nati Linial

Methods from harmonic analysis are used to prove some general theorems on Boolean functions. These connections with harmonic analysis viewed by the authors are very promising; besides the results on Boolean functions they enable them to prove theorems on the rapid mixing of the random walk on the cube and in the extremal theory of finite sets. >

STOC Conference 1984 Conference Paper

Every Poset Has a Good Comparison

• Jeff Kahn 0001
• Michael E. Saks

We show that any finite partially ordered set P contains a pair of elements x and y such that the proportion of linear extensions of P in which x lies below y is between 3/11 and 8/11. A consequence is that the information-theoretic lower bound for sorting under partial information is tight up to a multiplicative constant. Precisely: if X is a totally ordered set about which we are given some partial information, and if e(X) is the number of total orderings of X compatible with this partial information, then it is possible to sort X using no more than c log 2 e(X) comparisons (c@@@@2.17).

FOCS Conference 1983 Conference Paper

A Topological Approach to Evasiveness

• Jeff Kahn 0001
• Michael E. Saks
• Dean Sturtevant

The complexity of a digraph property is the number of entries of the vertex adjacency matrix of a digraph which must be examined in worst case to determine whether the digraph has the property. Rivest and Vuillemin proved the result (conjectured by Aanderaa and Rosenberg) that every graph property that is monotone (preserved by addition of edges) and nontrivial (holds for some but not all graphs) has complexity θ(v2) where v is the number of vertices. Karp conjectured that every such property is evasive, i. e. , requires that every entry of the incidence matrix be examined. In this paper it is shown that Karp's conjecture follows from another conjecture concerning group actions on topological spaces. A special case of this conjecture is proved and applied to prove Karp's conjecture for the case of properties of graph and digraph properties on a prime power number of vertices.