Gil Kalai

Hebrew University of Jerusalem

Einstein Institute of Mathematics, Hebrew University, Givat-Ram, Jerusalem 91904, Israel

  • Telephone numbers: Office (972)2-6584729, Home (972)3-9300001, Fax (972)2-5630702.
  • Email address: kalai at math.huji.ac.il,
  • Reichman University, Herzliya

    Efi Arazy School of Computer Science, IDC, Herzliya 4610101, Israel.

    Weblog: Combinatorics and more .


    Popular article: (Hebrew):

    Nati Linial and Gil Kalai, Ten Landmarks in the Story of Mathematics , to appear in "Galileo".

    Popular talk (in Hebrew): Geometry in more than three dimensions.

    Click here for a link to "Madua (=why)" program and lectures.

    Main areas of interest: Combinatorics and convexity.

    Papers and lectures:

    Online papers

    Papers and writings: very recent items :

  • Imre Barany and Gil Kalai, Erdos-Szekeres theorem for k-flats .
  • Ehud Friedgut, Gil Kalai, and Guy Kindler, The success probability in Lionel Levine's hat problem is strictly decreasing with the number of players, and this is related to interesting questions regarding Hamming powers of Kneser graphs and independent sets in random subgraphs .
  • Gil Kalai, The Argument against Quantum Computers, the Quantum Laws of Nature, and Google's Supremacy Claims .
  • Yosef Rinott, Tomer Shoham, and Gil Kalai, Statistical Aspects of the Quantum Supremacy Demonstration.
  • Gil Kalai and Roy Meshulam, Relative Leray numbers via spectral sequences.
  • Gil Kalai, Three Puzzles on Mathematics, Computation, and Games. (ICM 2018)
  • Gil Kalai and Zuzana Patakova, Intersection patterns of planar sets .
  • Gil Kalai and Leonard Schulman, Quasi-random multilinear polynomials .
  • Gil Kalai and Eran Nevo, TurĂ¡n, involution and shifting .
  • Gil Kalai, Boolean functions, Influence, threshold, and Noise (ECM 2016).
  • Papers and writings: recent items :

  • (with Itai Benjamini) Around two theorems and a lemma by Lucio Russo.
  • (with David Ellis and Bhargav Narayanan) On symmetric intersecting families .
  • Boolean functions: Influence, threshold and noise .
  • (with Ehud Friedgut, Jeff Kahn, and Nathan Keller) Chv\'atal's conjecture and correlation inequalities .
  • Designs exists! (after P. Keevash) .
  • (with Nathan Keller and Elchanan Mossel) On the Correlation of Increasing Families .
  • (with Imre Barany and Roy Meshulam) A Tverberg type theorem for matroids.
  • . The quantum compute puzzle, Notices AMS, May 2016. . The quantum compute puzzle (an expanded version)
  • Some old and new problems in combinatorial geometry I: Around Borsuk's problem.
  • (with Greg Kuperberg) Contagious error sources would need time travel to prevent quantum computation.
  • (with Guy Kindler) Boson Sampling and Noise Sensitivity.
  • (with Maria Chudnovsky, Eran Nevo, Isabella Novik, and Paul Seymour) Bipartite minors.
  • (with Eran Nevo, and Isabella Novik ) Bipartite rigidity .
  • (with Reshef Meir and Moshe Tennenholtz) General-sum bidding games
  • Some old and new problems in combinatorics and geometry.
  • (A presentation)
  • (with Jean Bourgain and Jeff Kahn) Influential coalitions for Boolean Functions.
  • and and An (early) presentation
  • (with Uriel Feige and Moshe Tennenholtz ) Cascade auctions.
  • .
  • (with Elchanan Mossel) Sharp Thresholds for Monotone Non Boolean Functions and Social Choice Theory.
  • How quantum computers fail: Quantum codes, correlations in physical systems, and noise accumulation.
  • When noise accumulates. Slides from a related lecture at IQI.
  • with M. Safra, Threshold phenomena and influences.
  • My list of publications

    Slides of lectures

    Graduate students and post-docs.

    My Own Supervisor was Micha A. Perles (Both for M.Sc and Ph. D). My host for Post-Doctoral studies was Richard Stanley .

    Ph. D. Students: Graduated: Ron Adin (with Micha A. Perles), Ehud Friedgut , Isabella Novik , Rom Pinchasi (with Micha A. Perles and (unofficially) Janos Pach), Hagit Last, Romina Zigdon, Eyal Beigman, Eran Nevo, Nathan Keller , Noa Nitzan (with Micha A. Perles), Moti Novick, Ilan Karpas, Noam Lifshitz (with Guy Kindler), Moshe White. Currently: Gabriel Gendler,

    M. Sc Students: Graduated: Oded Schramm , Eran London, Yuri Rabinovich , Alex Samorodnitsky , Yuval Roichman , Isabella Novik, Moshe Litvin, Akiva Kadari, Yoav Kirsch, Shachar Lovett, , Eran Nevo, Yuval Salant, Yonathan Samet, Eyal Novinsky, Ilan Nehama, Moti Novick, Aviv Sheyn, Uri Leder, Yannai Gonczarowski, Yuval Peled, and Michael Simkin, Moshe White, Ran Adi.

    Post-doctorate researchers: Helena Jorge, David Garbiner, Hein van der Holst, Guy Kindler , Mathieu Detour, Frank Valentin , Uli Wagner, Shakhar Smorodinsky, Elad Dokow, Mark Kozdoba, Yilun Shang, Karim Adiprasito, Gonzalo Fiz Pontiveros, Evan DeCorte, Sonia Balagopalan (with Eran Nevo), Pavel Patak (with Karim Adiprasito), Zuzana Patakova (with Karim Adiprasito), Ferdinand Ihringer, Roman Glebov, Reut Levi.

    Coauthors and collaborators

    Coauthors: Michael Maschler, Guillermo Owen, Noga Alon, Shmuel Friedland, Anders Bjorner, Peter Frankl, Zoltan Furedi, Jeff Kahn, Nati Linial, Jean Bourgain, Yitzhak Katznelson, Daniel Kleitman, Motty Ricklin, Larry Stockmayer, Ehud Friedgut, Jirka Matousek, Itai Benjamini, Oded Schramm, Branden McKay, Maya Bar-Hillel, Dror Bar-Natan, Gunter Meisinger, Peter Kleinschmidt, Roy Meshulam, Ariel Rubinstein, Ran Spiegler, Assaf Naor, Muli Safra, Helene Barcelo, Gunter M. Ziegler, Amnon Shashua, Lior Wolf, Anat Levin, Elchanan Mossel, Olle Haggstrom, Greg Friedman, Saharon Shelah, Avi Wigderson, Irit Dinur, Noam Nisan, Imre Barany, Nathan Keller, Moshe Tennelholtz, Uri Feige, Reshef Meir, Maria Chudnovsky, Eran Nevo, Isabella Novik, Paul Seymour, Greg Kuperberg, Guy Kindler, Leonard Schulman, David Ellis, Bhargav Narayanan, Zuzana Patakova, Barry Simon, Nir Avni, Jonathan Breuer, Yosi Rinott, Tomer Shoham .

    Other frequent collaborators:

    (definition: Not from the above lists, on more than one occasion we were seriously working on a project with the potential of leading to a joint research paper.)

    Micha Perles, Richard Stanley, Mike Saks, Lou Billera, Karanbir Sarkaria, Yuval Peres, Alex Lubotzky, Eric Babson, Sergiu Hart, Laci Lovasz, Francesco Brenti, Ravi Kannan, Janos Pach, Doron Zeilberger, Motty Perry, Yishay Mansour, Michal Feldman, Aviad Rubinshtein, Gady Kozma, Tammy Ziegler, Karim Adiprasito, Robert Aumann, Ron Adin, Joshua David Paik, Ferdinand Ihringer.

    homepages of some past graduate classes

    Assignement for the Course "Combinatorics" SPRING 2013 The assinments.

    Fall 2007, Yale University: Topic in discrete mathematics: Social Choice Theory.

    Fall 2004 (Jeusalem) Algebraic Topology

    Fall 2004 - Course at Yale: Boolean functions

    Kalle Karu proved the nonnegativity of toric h-vectors for general polytopes. The seminar (Fall 2003 HU, with David Kazhdan) Convex polytopes and Toric Varieties , was devoted to studying parts of this proof and related issues.

    Spring 2003:

    (with Avi Wigderson) Mathematical problems in computer science

    Classes 2006/2007

    Fall 2006, Yale University:

  • Topic in discrete mathematics: Mathematical problems arising from theoretical computer science. MW 11:30-12:45, AKW 400.
  • Fall 2005, Yale University - Topic in discrete mathematics:
  • Convexity and Linear Programming
  • Fall 2004, Yale University - Topic in discrete mathematics: Analysis of Boolean function
  • Spring 2004, Yale University - Topic in discrete mathematics: Combinaorics.
  • Past special semesters, Conferences, workshops and season-schools.

    ___s_p_r_i_n_g______2_0_0_7___________J_e_r_u_s_a_l_e_m____________________

    Special Semester in Jerusalem:

    Combinatorics of Polytopes and Complexes: Relations with Topology and Algebra

    1 March 2007- 31 August 2007

    Toric varieties, polytope duality, mirror symmetry and Kozsul duality day, Sunday, 18 March. Speakers: Tom Braden, Sasha Zvonkin, Victor Batyrev.

    Valuations day: (organizer: Semyon Alesker), Wednesday, April 11, 2007, speakers: Semyon Alesker, Gil Kalai, Andreas Bernig.

    Midrasha Matematicae: Spring School in Jerusalem: Polytopes, Graphs and Convexity, 6-11 May, 2007.

    Back-to-back mini-workshops:

  • Convexity, Random polytopes, random complexes, random spaces: (co-organizer: Chris Hoffman) June 14,15 and 18, 2007.
  • Combinatorics and Topology: (co-organizer: Rade Zivaljevic) June, 18 - June 21, 2007
  • Workshop on Graph Rigidity, Monday, July 9, 10:30. Main speaker, Bob Connelly.

    Thursday August 2 2007, Metric DAY, Lectures by Henry Cohn and Igor Pak.

    ___s_p_r_i_n_g______2_0_0_7___________J_e_r_u_s_a_l_e_m____________________

    Fall 2004

    WORLSHOP ON BOOLEAN FUNCTIONS: Spet 27-29 2004.

    Yale discrete mathematics seminar Mondays 16:30 AKW-200

  • Spring School 2003 PROGRAM
  • Past and Available computer projects
  • Math problems, Math news, Non-math problems (under construction)

    Research interest and projects

  • Face numbers and related invariants of polytopes and complexes
  • The combinatorics of the simplex algorithm
  • Influences, threshold phenomena and random graphs
  • Pictures (before 2005).

    Top right: lecturing in a discrete geometry meeting Ascona , 1999 (taken by: Emo Welzl), left: with Mazi, Lior, Neta and Hagai, Jerusalem 2005, Below: With Itai Benjamini and Oded Schramm, Beit Belgia, Dec 2004 (Tselil Schramm). Below: Listening with Michael Ben-Or and Sergiu Hart to Elchanan Ben-Porath, 2002 (Yaakov Bergman). Below: the joint class with Avi, lecture on evasiveness, 2003 (Boas Barak). Below: right, with Shahar Mozes 2001 (Dror Bar-Natan), left, 24th CCCC (Cambridge Combinatorics and Coffee Club) 2004, Below right: with Yisrael Aumann, 2002 (Yaakov Bergman), left: with Jirka Matousek, 1999 (Emo Welzl).

    Pictures 2005

    Pictures 2006