Quantum Computers: Noise Propagation and Adversarial Noise Models (2009)
In this paper we consider adversarial noise models that will fail quantum error correction and fault-tolerant quantum computation. We describe known results regarding high-rate noise, sequential...
Elections Can be Manipulated Often Draft – Comments Welcome (2009)
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...
Threshold Phenomena and Influence with some perspectives from Mathematics (2008)
“Threshold phenomena ” refer to settings in which the probability for an event to occur changes rapidly as some underlying parameter varies. Thresh-old phenomena play an important role in...
Boolean functions whose Fourier transform is concentrated on the first two levels (2008)
Ehud Friedgut, Gil Kalai, Assaf Naor
x2;:::; xn) whose Fourier coefficients are concentrated on the lowest two levels. We show that such a function is close to a constant function or to a function of the form f = xk or f = 1 \Gamma xk....
How quantum computers can fail (2008)
We propose and discuss two postulates on the nature of errors in highly correlated noisy physical stochastic systems. The first postulate asserts that errors for a pair of substantially correlated...
Detrimental Decoherence (2008)
We propose and discuss two conjectures on the nature of information leaks (decoherence) for quantum computers. These conjectures, if (or when) they hold, are damaging for quantum error-correction as...
Threshold Phenomena and Influence with some perspectives from Mathematics (2008)
“Threshold phenomena ” refer to settings in which the probability for an event to occur changes rapidly as some underlying parameter varies. Thresh-old phenomena play an important role in...
How quantum computers can fail (2008)
We propose and discuss two postulates on the nature of errors in highly correlated noisy physical stochastic systems. The first postulate asserts that errors for a pair of substantially correlated...
Threshold Phenomena and Influence with some perspectives from Mathematics (2008)
Threshold phenomena refer to settings in which the probability for an event to occur changes rapidly as some underlying parameter varies. Threshold phenomena play an important role in probability...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2008)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
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...
Leray numbers of projections and a topological Helly-type theorem (2008)
Let X be a simplicial complex on the vertex set V. The rational Leray number of X is the minimal d, such that for all induced subcomplexes Y ⊂ X and i ⩾ d. Suppose that is a partition of...
Transversal numbers for hypergraphs arising in geometry (2007)
Noga Alon, Gil Kalai, Roy Meshulam
Ji r ' i Matou sek y
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...
The Influence of Variables on Boolean Functions (Extended Abstract) (2007)
Jeff Kahn, Gil Kalai, Nathan Linial
This paper applies methods from harmonic analysis to prove some general theorems on boolean functions. The result that is easiest to describe says that "Boolean functions always have small...
Leray numbers of projections and a topological Helly type theorem (2007)
Let X be a simplicial complex on the vertex set V. The rational Leray number L(X) of X is the minimal d such that the rational reduced homology of any induced subcomplex of X vanishes in dimensions d...
Is the Universe Noise-Sensitive? (2007)
The dichotomy between noise-stable and (completely) noise-sensitive stochastic models is of recent interest in probability theory. Of particular interest is the study of lattice models coming from...
Detrimental Decoherence (2007)
Gil Kalai, Dorit Aharonov, Michael Ben-or, Greg Kuperberg
We propose and discuss two conjectures on the nature of informa-tion leaks (decoherence) for quantum computers. These conjectures, if (or when) they hold, are damaging for quantum error-correction as...
Leray numbers of projections and a topological Helly type theorem (2007)
Let X be a simplicial complex on the vertex set V. The rational Leray number L(X) of X is the minimal d such that ˜ Hi(Y; Q) = 0 for all induced subcomplexes Y ⊂ X and i ≥ d. Suppose V = �m...
How Quantum Computers Can Fail (2006)
We propose and discuss two postulates on the nature of errors in highly correlated noisy physical stochastic systems. The first postulate asserts that errors for a pair of substantially correlated...
Thresholds and expectation thresholds (2006)
Consider a random graph G in G(n,p) and the graph property: G contains a copy of a specific graph H. (Note: H depends on n; a motivating example: H is a Hamiltonian cycle.) Let q be the minimal value...
Intersections of Leray complexes and regularity of monomial ideals (2006)
For a simplicial complex X and a field K, let h_i(X)=\dim \tilde{H}_i(X;K). It is shown that if X,Y are complexes on the same vertex set, then for all k h_{k-1}(X\cap Y) \leq \sum_{\sigma \in Y}...
Thoughts on Noise and Quantum Computation (2005)
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quantum computation. We consider stochastic models of quantum...
Intersections of Leray Complexes and Regularity of Monomial Ideals (2005)
For a simplicial complex X and a field K, let ˜ hi(X) = dim ˜ Hi(X; K). It is shown that if X, Y are complexes on the same vertex set, then for k ≥ 0 ˜hk−1(X ∩ Y) ≤ � � ˜hi−1(X[σ])...
Thoughts on noise and quantum computing (2005)
Gil Kalai, Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
A multiperversity generalization of intersection homology (2005)
We define a generalization of intersection homology based on considering a set of perversities rather than a single perversity and explore some of its properties. The question whether these...
Michael Ben-Or, Greg Kuperberg, and Boris Tsirelson for helpful discussions, and to (2005)
Gil Kalai, Daniel Gottesman, Pierfrancesco La Mura, Nati Linial, Simon Litsyn, Yuval Peres, ...
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quan-tum computation. We consider stochastic models of quantum...
Noise sensitivity and chaos in social choice theory, preprint (2005)
In this paper we study the social preferences obtained from monotone neutral social welfare functions for random individual preferences. We identify a class of social welfare functions that...
A Law of Large Numbers for Weighted Majority (2004)
Haggstrom, Olle, Kalai, Gil, Mossel, Elchanan
Consider an election between two candidates in which the voters' choices are random and independent and the probability of a voter choosing the first candidate is $p>1/2$. Condorcet's Jury Theorem...
First passage percolation has sublinear distance variance (2003)
Benjamini, Itai, Kalai, Gil, Schramm, Oded
Let $0 < a < b < \infty$, and for each edge e of $\Z^d$ let $\omega_e=a$ or $\omega_e=b$, each with probability $1/2$, independently. This induces a random metric $\dist_\omega$ on the vertices of...
First Passage Percolation Has Sublinear Distance Variance (2002)
Benjamini, Itai, Kalai, Gil, Schramm, Oded
Let $0
On representation theory in computer vision problems (2002)
Amnon Shashua, Roy Meshulam, Lior Wolf, Anat Levin, Gil Kalai
We introduce the following general question: Let V be a complex n-dimensional space and for m k consider the GL(V)-module V (n # m # k) ae V
Algebraic shifting is a correspondence which associates to a simplicial complex K another simplicial complex (K) of a special type. In fact, there are two main variants based on symmetric algebra and...
On Representation Theory in Computer Vision (2002)
Problems Amnon Shashua, Amnon Shashua, Roy Meshulam, Lior Wolf, Anat Levin, Gil Kalai
We introduce the following general question: Let V be a complex n-dimensional space and for m k consider the GL(V )-module V (n# m# k)=f v 1 \Omega \Delta\Delta\Delta \Omega vm 2 V We would like to...
First Passage Percolation Has Sublinear Distance Variance (2002)
Itai Benjamini, Gil Kalai, Oded Schramm
Let 0 < a < b < 1, and for each edge e of Z let ! e = a or ! e = b, each with probability 1=2, independently. This induces a random metric dist ! on the vertices of Z , called rst passage...
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...
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,...
Combinatorics with a geometric flavor: some examples (2000)
In this paper I try to present my field, combinatorics, via five examples of combinatorial studies which have some geometric flavor. The first topic is Tverberg's theorem, a gem in combinatorial...
Solving the Bible Code Puzzle (1999)
Bar-Hillel, Maya, Bar-Natan, Dror, Kalai, Gil, McKay, Brendan
A paper of Witztum, Rips and Rosenberg in this journal in 1994 made the extraordinary claim that the Hebrew text of the Book of Genesis encodes events which did not occur until millennia after the...
Günter Meisinger, Peter Kleinschmidt, Gil Kalai
We prove that there is a nite list of 3-polytopes so that every rational d-polytope, d 9, contains a 3-dimensional face in the list. A similar result where "faces" are replaced by...
Flag Numbers and FLAGTOOL (1999)
Gil Kalai, Peter Kleinschmidt, Günter Meisinger
FLAGTOOL is a computer program for proving automatically theorems about the combinatorial structure of polytopes of dimensions at most 10. Its starting point is the known linear relations (equalities...
Solving The Bible Code Puzzle (1999)
Brendan Mckay, Dror Bar-natan, Maya Bar-hillel, Gil Kalai
. A paper of Witztum, Rips and Rosenberg in this journal in 1994 made the extraordinary claim that the Hebrew text of the Book of Genesis encodes events which did not occur until millennia after the...
Noise Sensitivity of Boolean Functions And Applications to Percolation (1999)
Itai Benjamini, Gil Kalai, Oded Schramm
It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the conguration with an arbitrary small percent of...
Solving The Bible Code Puzzle (1999)
Brendan Mckay Dror, Dror Bar-natan, Maya Bar-hillel, Gil Kalai
A paper of Witztum, Rips and Rosenberg in this journal in 1994 made the extraordinary claim that the Hebrew text of the Book of Genesis encodes events which did not occur until millennia after the...
Solving the Bible Code puzzle (1999)
Brendan Mckay, Dror Bar-natan, Maya Bar-hillel, Gil Kalai
Abstract. A paper of Witztum, Rips and Rosenberg in this journal in 1994 made the extraordinary claim that the Hebrew text of the Book of Genesis encodes events which did not occur until millennia...
Noise Sensitivity of Boolean Functions and Applications to Percolation (1998)
Benjamini, Itai, Kalai, Gil, Schramm, Oded
It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with an arbitrary small percent of...
Noise Sensitivity of Boolean Functions And Applications to Percolation (1998)
Itai Benjamini, Gil Kalai, Oded Schramm
It is shown that a large class of events in a product probability space are highly sensitive to noise, in the sense that with high probability, the configuration with an arbitrary small percent of...
Linear Programming, the Simplex Algorithm and Simple Polytopes (1997)
In the first part of the paper we survey some far-reaching applications of the basic facts of linear programming to the combinatorial theory of simple polytopes. In the second part we discuss some...
Polytope Skeletons And Paths (1997)
INTRODUCTION The k-dimensional skeleton of a d-polytope P is the set of all faces of the polytope of dimension at most k. The 1-skeleton of P is called the graph of P and denoted by G(P ). G(P ) can...
Every monotone graph property has a sharp threshold (1996)
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...
On the Distance Distribution of Codes (1995)
The distance distribution of a binary code C is the sequence (G i ) n i=0 defined as follows: Let G i (w) be the number of code words at distance i from the code word w, and let G i be the average of...
Combinatorics and Convexity (1995)
this paper deals with convexity in general and the second part deals with the combinatorics of convex polytopes. There are many excellent surveys [20, 9] and collections of open problems [13, 29]. I...
A counterexample to Borsuk's conjecture (1993)
Let $f(d)$ be the smallest number so that every set in $R^d$ of diameter 1 can be partitioned into $f(d)$ sets of diameter smaller than 1. Borsuk's conjecture was that $f(d)\! =\!d\!+\!1$. We prove...
Some Aspects Of The Combinatorial Theory Of Convex Polytopes (1993)
. We start with a theorem of Perles on the k-skeleton, Skel k (P ) (faces of dimension k) of d- polytopes P with d+b vertices for large d. The theorem says that for fixed b and d, if d is...
A quasi-polynomial bound for the diameter of graphs of polyhedra (1992)
Kalai, Gil, Kleitman, Daniel J.
The diameter of the graph of a $d$-dimensional polyhedron with $n$ facets is at most $n^{\log d+2}$
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...
The influence of variables on Boolean functions (1988)
Jeff Kahn, Gil Kalai, Nathan Linial
This paper applies methods from harmonic analysis to prove some general theorems on boolean functions. The result that is easiest to describe says that "Boolean functions always have small...
Learnability and Rationality of Choice
The purpose of this paper is to examine the extent to which the concepts of individual and collective choice unsed in economic theory desribe "predictable" or "learnable" behavior. Given a set X of N...
Social Choice and Threshold Phenomena
Arrow's theorem asserts that under certain conditions every non-dictatorial social choice function leads to nonrational social choice for some profiles. In other words, for the case of...
A Fourier-Theoretic Perspective for the Condorcet Paradox and Arrow's Theorem
We describe a Fourier-theoretic formula for the probability of rational outcomes for random profiles for a social choice function on three alternatives. Several applications are given.
Thoughts on Noise and Quantum Computation
We will try to explore, primarily from the complexity-theoretic point of view, limitations of error-correction and fault-tolerant quantum computation. We consider stochastic models of quantum...
Rationalizing Choice Functions by Multiple Rationales
Gil Kalai, Ariel Rubenstein, Ran Spiegler
The paper presents a notion of rationalizing choice functions that violate the “Independence of Irrelevant Alternatives” axiom. A collection of linear orderings is said to provide a...
An extension of Condorcet's paradox by McGarvey (1953) asserts that for every asymmetric relation R on a finite set of candidates there is a strict-preferences voter profile that has the relation R...
Rationalizing Choice Functions by Multiple Rationales
Gil Kalai, Ariel Rubinstein, Ran Spiegler
The paper presents a notion of rationalizing choice functions that violate the “Independence of Irrelevant Alternatives” axiom. A collection of linear orderings is said to provide a...
An extension of Condorcet's paradox by McGarvey (1953) asserts that for every asymmetric relation R on a finite set of candidates there is a strict-preferences voter profile that has the relation R...
A Law of Large Numbers for Weighted Majority
Olle Haggstrom, Gil Kalai, Elchanan Mossel
Consider an election between two candidates in which the voters’ choices are random and independent and the probability of a voter choosing the first candidate is p > 1/2. Condorcet’s Jury...
Noise Sensitivity and Chaos in Social Choice Theory
In this paper we study the social preferences obtained from monotone neutral social welfare functions for random individual preferences. It turns out that there are two extreme types of behavior. On...
Science, Beliefs and Knowledge: A Personal Reflection on Robert J. Aumann’s Approach
On the occasion of Robert J. Aumann's being awarded the 2005 Nobel Prize in Economics, this paper gives a personal view on some of Aumann's contributions, and primarily on his approach to...
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...
A review of Steven E. Landsburg's book More Sex is Safer Sex, the Unconventional Wisdom of Economics. The surprise 2005 best seller Freakonomics by Steven Levitt and Stephen Dubner launched a small...
How Quantum Computers Can Fail
We propose and discuss two postulates on the nature of errors in highly correlated noisy physical stochastic systems. The first postulate asserts that errors for a pair of substantially correlated...
INTRODUCTION The k-dimensional skeleton of a d-polytope P is the set of all faces of the polytope of dimension at most k. The 1-skeleton of P is called the graph of P and denoted by G(P ). G(P ) can...