Gil Kalai - On-Line Papers

  • Mailing address: Institute of Mathematics, Hebrew University, Givat-Ram, Jerusalem 91904, Israel
  • Telephone numbers: Office (972)2-6584729, Home (972)2-6536301, Fax (972)2-5630702.
  • Email addresses: kalai@math.huji.ac.il, my home page

    Survey articles

    (with Muli Safra) Threshold Phenomena and Influence, in: Computational Complexity and Statistical Physics, A.G. Percus, G. Istrate and C. Moore, eds. (Oxford University Press, New York, 2006), pp. 25-60.

    Combinatorics with a Geometric Flavor GAFA special volume(2000) Vol. II, 742-791.

    Combinatorics and convexity, Proc. ICM - Zurich, 1363-1374, Birkhauser 1995.

    Linear programming, the simplex algorithm and simple polytopes , Math. Prog. (Ser. B) 79(1997), 217-234.

    Algebraic shifting

    Algebraic shifting , in: "Computational Commutative Algebra and Combinatorics", Advanced studies in pure mathematics 33 (2002), 121-163.

    Polytopes, Convexity, Helly-type theorems, and relations with commutative algebra and topology.

    with G. Friedman, A multiperversity generalization of intersection homology, Pure and Applied Math Quarterly, Volume 3, Number 1, 2007.

    With Roy Meshulam, Intersection of Leray complexes and regularity of monomial ideals, J. Comb. Th (Ser A), J. Combin. Theory Ser. A 113 (2006), 1586-1592.

    With Roy Meshulam, A topological colorfull Helly theorem , Advances in Mathematics, 191 (2005), 305-311.

    Second edition 2002: Polytope skeletons and paths,

    in: Handbook of Discrete and Computational Geometry (Goodman and O'Rourke, eds.).

    Transversal Numbers for Hypergraphs Arising in Geometry With Noga Alon, Jiri Matousek and Roy Meshulam, Adv. in Appl. Math., 29 (2002), 79--101.

    ( with G\"unter Meisinger and Peter Kleinschmidt) Three theorems on three-dimensional faces and quotients of higher dimensional polytopes with computer-aided proofs, . Discrete and Computational Geometry 24 (2000), 413--420.

    (with Jirka Matousek) Guarding galleries in which every point can see a large area, Isr. J. of Math. 101(1997), 125-139.

    Some aspects of the combinatorial theory of convex polytopes,

    in : Polytopes, Abstract Convex and Computational, (T. Bisztriczky et alls, eds) pp. 205-230.

    Flag numbers and FLAGTOOL with G\"unter Meisinger and Peter Kleinschmidt. DMV Sem.,29, Birkhouser, Basel, 2000.

    Influences, threshold phenomena, Fourier transform of boolean functions and noise sensitivity

  • Is the universe noise sensitive? and A power point presentation .

    (with Jeff Kahn) Thresholds and expectation thresholds, Combinatorics, Probability and Computing, to appear

    (with I. Benjamini and O. Schramm) Improved variance bounds for first passage percolation, , Ann. Probab. 31 (2003), no. 4, 1970--1978.

    Boolean functions whose Fourier transform is concentrated on the first two levels, (with Ehud Friedgut and Assaf Naor) Adv. in Appl. Math., 29(2002), 427-437.

    (with Itai Benjamini and Oded Schramm) Noise Sensitivity of Boolean Functions And Applications to Percolation, Publ. I.H.E.S. 90 (1999), 5-43

    (with J. Bourgain) Influences of variables and threshold intervals under group symmetries, GAFA 7 (1997), 438-461.

    (with E. Friedgut) Every Monotone Graph Property has a Sharp Threshold Proc. AMS 124(1996), 2993-3002

    (with N. Linial) On the distance distribution of binary codes, IEEE J. Information Th. 1995

    (With N. Linial and J. Kahn) The influence of variables on Boolean functions, Proc. 29-th Annual Symposium on Foundations of Computer Science, 68-80, Computer Society Press, 1988.

    Problems concerning the fourier transforms of Boolean functions, in progress.

    Quantum Computation

  • Detrimental decoherence.

    How quantum computers can fail.

    Thoughts on noise and quantum computing.

    Theory of Choice and Game theory:

    Science, beliefs and knowledge: a personal reflection on Robert J. Aumann's approach.

    Noise sensitivity and chaos in social choice theory.

    (with Olle Haggstrom and Elchanan Mossel) A Law of Large Numbers for Weighted Majority, . Adv. in Appl. Math. 37 (2006), no. 1, 112--123.

    Social Indeterminacy, Econometrica, 72 (2004), 1565-1581.

    A Fourier-Theoretic Perspective for the Condorcet Paradox and Arrow's theorem, Adv. in Appl. Math. 29(2002), 412-426.

    Learnability and Rationality of Choice, J. Econom. Theory 113 (2003), no. 1, 104--117.

    Rationalizing choice functions by multiple rationals, (with Ariel Rubinstein and Rani Spiegler), Econometrica, 70 (2002), 2481-2488.