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.

    The work of Daniel A. Spielman. and A presentation

    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.

  • Some old and new problems in combinatorial geometry I: Around Borsuk's problem. This is a draft of a chapter for "Surveys in Combinatorics 2015," edited by Artur Czumaj, Angelos Georgakopoulos, Daniel Kral, Vadim Lozin, and Oleg Pikhurko. The final published version shall be available for purchase from Cambridge University Press
  • (with Maria Chudnovsky, Eran Nevo, Isabella Novik, and Paul Seymour) Bipartite minors.
  • (with Eran Nevo, and Isabella Novik ) Bipartite rigidity .

    • with R. Meshulam, Leray numbers of projections and a topological Helly-type theorem.

    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

  • (with Jean Bourgain and Jeff Kahn) Influential coalitions for Boolean Functions.
    • and and An (early) presentation
  • With S. Shelah, An example related to the Sauer-Shelah theorem.

    • (with Jeff Kahn) Thresholds and expectation thresholds, Combinatorics, Probability and Computing.

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

    (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

  • (with Greg Kuperberg) Contagious error sources would need time travel to prevent quantum computation.
  • (with Guy Kindler) Boson Sampling and Noise Sensitivity.

    • How quantum computers fail: Quantum codes, correlations in physical systems, and noise accumulation.

    When noise accumulates. Slides from a related lecture at IQI.

    Quantum Computers: Noise Propagation and Adversarial Noise Models

    Detrimental decoherence. and A power point presentation (prepared for QEC07 - the first international conference on quantum error correction, Los Angeles, Dec 2007).

    How quantum computers can fail.

    Thoughts on noise and quantum computing.

    Theory of Choice and Game theory:

  • (with Reshef Meir and Moshe Tennenholtz) General-sum bidding games
  • (with Uriel Feige and Moshe Tennenholtz ) Cascade auctions.
    • .

    with Elchanan Mossel Sharp Thresholds for Monotone Non Boolean Functions and Social Choice Theory.

    With E. Friedgut, N. Keller, and N. Nisan, A quantitative version of the Gibbard-Satterthwaite theorem for three alternatives.

    With E. Friedgut and N. Nisan Elections Can be Manipulated Often FOS 2009.

    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.