Gil Kalai

According to our database, Gil Kalai authored at least 66 papers between 1979 and 2023.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2023

The Success Probability in Levine's Hat Problem, and Independent Sets in Graphs.

Noga Alon, Ehud Friedgut, Gil Kalai, Guy Kindler

SIAM J. Discret. Math., December, 2023

Erdős-Szekeres Theorem for k-Flats.

Imre Bárány, Gil Kalai, Attila Pór

Discret. Comput. Geom., June, 2023

Questions and Concerns About Google's Quantum Supremacy Claim.

Gil Kalai, Yosef Rinott, Tomer Shoham

CoRR, 2023

2022

Google's 2019 "Quantum Supremacy" Claims: Data, Documentation, and Discussion.

Gil Kalai, Yosef Rinott, Tomer Shoham

CoRR, 2022

Conjecture C Still Stands.

Gil Kalai

CoRR, 2022

Quantum Computers, Predictability, and Free Will.

Gil Kalai

CoRR, 2022

2020

On symmetric intersecting families.

David Ellis, Gil Kalai, Bhargav P. Narayanan

Eur. J. Comb., 2020

Intersection Patterns of Planar Sets.

Gil Kalai, Zuzana Patáková

Discret. Comput. Geom., 2020

Guest Editors' Foreword.

Gil Kalai, Bojan Mohar, Isabella Novik

Discret. Comput. Geom., 2020

The Argument against Quantum Computers, the Quantum Laws of Nature, and Google's Supremacy Claims.

Gil Kalai

CoRR, 2020

Statistical Aspects of the Quantum Supremacy Demonstration.

Yosef Rinott, Tomer Shoham, Gil Kalai

CoRR, 2020

2019

The Argument against Quantum Computers.

Gil Kalai

CoRR, 2019

2018

Chvátal's conjecture and correlation inequalities.

Ehud Friedgut, Jeff Kahn, Gil Kalai, Nathan Keller

J. Comb. Theory, Ser. A, 2018

Bidding games and efficient allocations.

Reshef Meir, Gil Kalai, Moshe Tennenholtz

Games Econ. Behav., 2018

Three Puzzles on Mathematics, Computation, and Games.

Gil Kalai

CoRR, 2018

2016

On the correlation of increasing families.

Gil Kalai, Nathan Keller, Elchanan Mossel

J. Comb. Theory, Ser. A, 2016

Bipartite minors.

Maria Chudnovsky, Gil Kalai, Eran Nevo, Isabella Novik, Paul D. Seymour

J. Comb. Theory, Ser. B, 2016

2015

Sharp Thresholds for Monotone Non-Boolean Functions and Social Choice Theory.

Gil Kalai, Elchanan Mossel

Math. Oper. Res., 2015

Some old and new problems in combinatorial geometry I: Around Borsuk's problem.

Gil Kalai

CoRR, 2015

Some old and new problems in combinatorial geometry I: around Borsuk's problem.

Gil Kalai

Proceedings of the Surveys in Combinatorics 2015, 2015

2014

Gaussian Noise Sensitivity and BosonSampling.

Gil Kalai, Guy Kindler

CoRR, 2014

2013

General-sum Bidding Games.

Gil Kalai, Reshef Meir, Moshe Tennenholtz

CoRR, 2013

Functions without influential coalitions.

Jeff Kahn, Gil Kalai

CoRR, 2013

The Cascade Auction - A Mechanism for Deterring Collusion in Auctions.

Uriel Feige, Gil Kalai, Moshe Tennenholtz

Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence, 2013

2011

A Quantitative Version of the Gibbard-Satterthwaite Theorem for Three Alternatives.

Ehud Friedgut, Gil Kalai, Nathan Keller, Noam Nisan

SIAM J. Comput., 2011

How Quantum Computers Fail: Quantum Codes, Correlations in Physical Systems, and Noise Accumulation

Gil Kalai

CoRR, 2011

2008

Neighborly Embedded Manifolds.

Gil Kalai, Avi Wigderson

Discret. Comput. Geom., 2008

Elections Can be Manipulated Often.

Ehud Friedgut, Gil Kalai, Noam Nisan

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Thresholds and Expectation Thresholds.

Jeff Kahn, Gil Kalai

Comb. Probab. Comput., 2007

2006

Intersections of Leray complexes and regularity of monomial ideals.

Gil Kalai, Roy Meshulam

J. Comb. Theory, Ser. A, 2006

A law of large numbers for weighted majority.

Olle Häggström, Gil Kalai, Elchanan Mossel

Adv. Appl. Math., 2006

Threshold Phenomena and Influence: Perspectives from Mathematics, Computer Science, and Economics.

Gil Kalai, Shmuel Safra

Proceedings of the Computational Complexity and Statistical Physics., 2006

2004

Polytope Skeletons and Paths.

Gil Kalai

Proceedings of the Handbook of Discrete and Computational Geometry, Second Edition., 2004

2003

Learnability and rationality of choice.

Gil Kalai

J. Econ. Theory, 2003

2002

A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.

Gil Kalai

Adv. Appl. Math., 2002

Boolean functions whose Fourier transform is concentrated on the first two levels.

Ehud Friedgut, Gil Kalai, Assaf Naor

Adv. Appl. Math., 2002

Transversal numbers for hypergraphs arising in geometry.

Noga Alon, Gil Kalai, Jirí Matousek, Roy Meshulam

Adv. Appl. Math., 2002

2000

Three Theorems, with Computer-Aided Proofs, on Three-Dimensional Faces and Quotients of Polytopes.

Günter Meisinger, Peter Kleinschmidt, Gil Kalai

Discret. Comput. Geom., 2000

Guest Editors' Foreword.

Gil Kalai, Victor Klee

Discret. Comput. Geom., 2000

Fractional Helly theorem, weak epsilon nets and geometric piercing.

Gil Kalai

Proceedings of the 12th Canadian Conference on Computational Geometry, 2000

1997

Linear programming, the simplex algorithm and simple polytopes.

Gil Kalai

Math. Program., 1997

1995

On the distance distribution of codes.

Gil Kalai, Nathan Linial

IEEE Trans. Inf. Theory, 1995

Bounding the Piercing Number.

Noga Alon, Gil Kalai

Discret. Comput. Geom., 1995

1994

Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling.

Noga Alon, Gil Kalai, Moty Ricklin, Larry J. Stockmeyer

Theor. Comput. Sci., 1994

A Problem of Füredi and Seymour on Covering Intersecting Families by Pairs.

Jeff Kahn, Gil Kalai

J. Comb. Theory, Ser. A, 1994

1992

Upper Bounds for the Diameter and Height of Graphs of Convex Polyhedra.

Gil Kalai

Discret. Comput. Geom., 1992

A Subexponential Randomized Simplex Algorithm (Extended Abstract)

Gil Kalai

Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract)

Noga Alon, Gil Kalai, Moty Ricklin, Larry J. Stockmeyer

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

1990

Symmetric matroids.

Gil Kalai

J. Comb. Theory, Ser. B, 1990

On low-dimensional faces that high-dimensional polytopes must have.

Gil Kalai

Comb., 1990

The Diameter of Graphs of Convex Polytopes and f-Vector Theory.

Gil Kalai

Proceedings of the Applied Geometry And Discrete Mathematics, 1990

Extended Euler-Poincare Relations for Cell Complexes.

Anders Björner, Gil Kalai

Proceedings of the Applied Geometry And Discrete Mathematics, 1990

1989

The number of faces of centrally-symmetric polytopes.

Gil Kalai

Graphs Comb., 1989

1988

A simple way to tell a simple polytope from its graph.

Gil Kalai

J. Comb. Theory, Ser. A, 1988

A new basis of polytopes.

Gil Kalai

J. Comb. Theory, Ser. A, 1988

Many Triangulated Spheres.

Gil Kalai

Discret. Comput. Geom., 1988

The Influence of Variables on Boolean Functions (Extended Abstract)

Jeff Kahn, Gil Kalai, Nathan Linial

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

1986

Characterization of f-vectors of families of convex sets in R^<i>d</i> part II: Sufficiency of Eckhoff's conditions.

Gil Kalai

J. Comb. Theory, Ser. A, 1986

1985

A new approach to Turán's conjecture.

Gil Kalai

Graphs Comb., 1985

Hyperconnectivity of graphs.

Gil Kalai

Graphs Comb., 1985

A Simple Proof of the Upper Bound Theorem.

Noga Alon, Gil Kalai

Eur. J. Comb., 1985

f-Vectors of acyclic complexes.

Gil Kalai

Discret. Math., 1985

1984

Every 4-regular graph plus an edge contains a 3-regular subgraph.

Noga Alon, Shmuel Friedland, Gil Kalai

J. Comb. Theory, Ser. B, 1984

Regular subgraphs of almost regular graphs.

Noga Alon, Shmuel Friedland, Gil Kalai

J. Comb. Theory, Ser. B, 1984

1983

בעיות קומבינטוריות בקמירות וקומבינטוריקה של קומפלכסים סימפליציאליים (Combinatorial problems in convexity and the combinatorics of simplicial complexes.).

Gil Kalai

PhD thesis, 1983

1979

A Note on an Evaluation of Abel Sums.

Gil Kalai

J. Comb. Theory, Ser. A, 1979