Gil Kalai

Last updated
Gil Kalai
Gil Kalai 2007.jpg
Kalai at Oberwolfach, 2007
Born1955 (age 6869)
Alma materHebrew University (PhD)
Scientific career
Fields Mathematics
Institutions
Doctoral advisor Micha Perles
Notable students

Gil Kalai (born 1955) is an Israeli mathematician and computer scientist. He is the Henry and Manya Noskwith Professor Emeritus of Mathematics at the Hebrew University of Jerusalem, Israel, Professor of Computer Science at the Interdisciplinary Center, Herzliya, and adjunct Professor of mathematics and of computer science at Yale University, United States. [1]

Contents

Biography

Kalai received his PhD from Hebrew University in 1983, under the supervision of Micha Perles, [2] and joined the Hebrew University faculty in 1985 after a postdoctoral fellowship at the Massachusetts Institute of Technology. [3] He was the recipient of the Pólya Prize in 1992, the Erdős Prize of the Israel Mathematical Society in 1993, and the Fulkerson Prize in 1994. [1] He is known for finding variants of the simplex algorithm in linear programming that can be proven to run in subexponential time, [4] for showing that every monotone property of graphs has a sharp phase transition, [5] for solving Borsuk's problem (known as Borsuk's conjecture) on the number of pieces needed to partition convex sets into subsets of smaller diameter, [6] and for his work on the Hirsch conjecture on the diameter of convex polytopes and in polyhedral combinatorics more generally. [7]

From 1995 to 2001, he was the Editor-in-Chief of the Israel Journal of Mathematics. In 2016, he was elected honorary member of the Hungarian Academy of Sciences. [8] In 2018 he was a plenary speaker with talk Noise Stability, Noise Sensitivity and the Quantum Computer Puzzle at the International Congress of Mathematicians in Rio de Janeiro.

Kalai's conjectures on quantum computing

Kalai is a quantum computing skeptic who argues that true (classically unattainable) quantum computing will not be achieved because the necessary quality of quantum error correction cannot be reached.

Conjecture 1 (No quantum error correction). The process for creating a quantum error-correcting code will necessarily lead to a mixture of the desired codewords with undesired codewords. The probability of the undesired codewords is uniformly bounded away from zero. (In every implementation of quantum error-correcting codes with one encoded qubit, the probability of not getting the intended qubit is at least some δ > 0, independently of the number of qubits used for encoding.)

Conjecture 2. A noisy quantum computer is subject to noise in which information leaks for two substantially entangled qubits have a substantial positive correlation.

Conjecture 3. In any quantum computer at a highly entangled state there will be a strong effect of error-synchronization.

Conjecture 4. Noisy quantum processes are subject to detrimental noise. [9] [ non-primary source needed ]

Recognition

Kalai was the winner of the 2012 Rothschild Prize in mathematics. [10] He was named to the 2023 class of Fellows of the American Mathematical Society, "for contributions to combinatorics, convexity, and their applications, as well as to the exposition and communication of mathematics". [11]

See also

Related Research Articles

<span class="mw-page-title-main">Peter Lax</span> Hungarian-born American mathematician

Peter David Lax is a Hungarian-born American mathematician and Abel Prize laureate working in the areas of pure and applied mathematics.

<span class="mw-page-title-main">Béla Bollobás</span> Hungarian mathematician

Béla Bollobás FRS is a Hungarian-born British mathematician who has worked in various areas of mathematics, including functional analysis, combinatorics, graph theory, and percolation. He was strongly influenced by Paul Erdős from the age of 14.

<span class="mw-page-title-main">László Lovász</span> Hungarian mathematician

László Lovász is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He was the president of the International Mathematical Union from 2007 to 2010 and the president of the Hungarian Academy of Sciences from 2014 to 2020.

<span class="mw-page-title-main">Richard P. Stanley</span> American mathematician

Richard Peter Stanley is an Emeritus Professor of Mathematics at the Massachusetts Institute of Technology, and an Arts and Sciences Distinguished Scholar at the University of Miami. From 2000 to 2010, he was the Norman Levinson Professor of Applied Mathematics. He received his Ph.D. at Harvard University in 1971 under the supervision of Gian-Carlo Rota. He is an expert in the field of combinatorics and its applications to other mathematical disciplines.

<span class="mw-page-title-main">David Eisenbud</span> American mathematician

David Eisenbud is an American mathematician. He is a professor of mathematics at the University of California, Berkeley and former director of the then Mathematical Sciences Research Institute (MSRI), now known as Simons Laufer Mathematical Sciences Institute (SLMath). He served as Director of MSRI from 1997 to 2007, and then again from 2013 to 2022.

<span class="mw-page-title-main">Herbert Wilf</span> American mathematician

Herbert Saul Wilf was an American mathematician, specializing in combinatorics and graph theory. He was the Thomas A. Scott Professor of Mathematics in Combinatorial Analysis and Computing at the University of Pennsylvania. He wrote numerous books and research papers. Together with Neil Calkin he founded The Electronic Journal of Combinatorics in 1994 and was its editor-in-chief until 2001.

<span class="mw-page-title-main">Daniel Kleitman</span> American mathematician (born 1934)

Daniel J. Kleitman is an American mathematician and professor of applied mathematics at MIT. His research interests include combinatorics, graph theory, genomics, and operations research.

<span class="mw-page-title-main">Borsuk's conjecture</span> Can every bounded subset of Rn be partitioned into (n+1) smaller diameter sets?

The Borsuk problem in geometry, for historical reasons incorrectly called Borsuk's conjecture, is a question in discrete geometry. It is named after Karol Borsuk.

<span class="mw-page-title-main">Hirsch conjecture</span> On lengths of shortest paths in convex polytopes

In mathematical programming and polyhedral combinatorics, the Hirsch conjecture is the statement that the edge-vertex graph of an n-facet polytope in d-dimensional Euclidean space has diameter no more than n − d. That is, any two vertices of the polytope must be connected to each other by a path of length at most n − d. The conjecture was first put forth in a letter by Warren M. Hirsch to George B. Dantzig in 1957 and was motivated by the analysis of the simplex method in linear programming, as the diameter of a polytope provides a lower bound on the number of steps needed by the simplex method. The conjecture is now known to be false in general.

Polyhedral combinatorics is a branch of mathematics, within combinatorics and discrete geometry, that studies the problems of counting and describing the faces of convex polyhedra and higher-dimensional convex polytopes.

<i>Discrete & Computational Geometry</i> Academic journal

Discrete & Computational Geometry is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geometry.

<span class="mw-page-title-main">Alexander Lubotzky</span> Israeli mathematician and former politician

Alexander Lubotzky is an Israeli mathematician and former politician who is currently a professor at the Weizmann Institute of Science and an adjunct professor at Yale University. He served as a member of the Knesset for The Third Way party between 1996 and 1999. In 2018 he won the Israel Prize for his accomplishments in mathematics and computer science.

<span class="mw-page-title-main">Jeff Kahn (mathematician)</span> American mathematician

Jeffry Ned Kahn is a professor of mathematics at Rutgers University notable for his work in combinatorics.

<span class="mw-page-title-main">Irit Dinur</span> Israeli computer scientist

Irit Dinur is an Israeli computer scientist. She is professor of computer science at the Weizmann Institute of Science. In 2024 she was appointed a permanent faculty member in the School of Mathematics of the Institute for Advanced Study. Her research is in foundations of computer science and in combinatorics, and especially in probabilistically checkable proofs and hardness of approximation.

In geometry, more specifically in polytope theory, Kalai's 3d conjecture is a conjecture on the polyhedral combinatorics of centrally symmetric polytopes, made by Gil Kalai in 1989. It states that every d-dimensional centrally symmetric polytope has at least 3d nonempty faces.

<span class="mw-page-title-main">Isabella Novik</span> Israeli mathematician

Isabella Novik is a mathematician who works at the University of Washington as the Robert R. & Elaine F. Phelps Professor in Mathematics. Her research concerns algebraic combinatorics and polyhedral combinatorics.

Shmuel Friedland is an Israeli-American mathematician.

Dietmar Arno Salamon is a German mathematician.

Read's conjecture is a conjecture, first made by Ronald Read, about the unimodality of the coefficients of chromatic polynomials in the context of graph theory. In 1974, S. G. Hoggar tightened this to the conjecture that the coefficients must be strongly log-concave. Hoggar's version of the conjecture is called the Read–Hoggar conjecture.

In theoretical computer science, a function is said to exhibit quasi-polynomial growth when it has an upper bound of the form for some constant , as expressed using big O notation. That is, it is bounded by an exponential function of a polylogarithmic function. This generalizes the polynomials and the functions of polynomial growth, for which one can take . A function with quasi-polynomial growth is also said to be quasi-polynomially bounded.

References

  1. 1 2 Profile at Yale CS department Archived 2008-05-10 at the Wayback Machine .
  2. Gil Kalai at the Mathematics Genealogy Project.
  3. Profile at the Technical University of Eindhoven Archived 2009-07-13 at the Wayback Machine as an instructor of a minicourse on polyhedral combinatorics.
  4. Kalai, Gil (1992), "A subexponential randomized simplex algorithm", Proc. 24th ACM Symp. Theory of Computing (STOC 1992), pp. 475–482.
  5. Friedgut, Ehud; Kalai, Gil (1996), "Every monotone graph property has a sharp threshold", Proceedings of the American Mathematical Society , 124 (10): 2993–3002, doi: 10.1090/S0002-9939-96-03732-X .
  6. Kahn, Jeff; Kalai, Gil (1993), "A counterexample to Borsuk's conjecture", Bulletin of the American Mathematical Society , 29: 60–62, arXiv: math.MG/9307229 , doi:10.1090/S0273-0979-1993-00398-7, S2CID   119647518 .
  7. Kalai, Gil; Kleitman, Daniel J. (1992), "A quasi-polynomial bound for the diameter of graphs of polyhedra", Bulletin of the American Mathematical Society, 26 (2): 315–316, arXiv: math/9204233 , Bibcode:1992math......4233K, doi:10.1090/S0273-0979-1992-00285-9, S2CID   37821778 .
  8. "A Magyar Tudományos Akadémia újonnan megválasztott tagjai (The newly elected members of the Hungarian Academy of Sciences)". Magyar Tudományos Akadémia (mta.hu). 2 May 2016. Archived from the original on 5 May 2016. Retrieved 2 May 2016.
  9. How Quantum Computers Fail by Gil Kalai (2011)
  10. Yad Hanadiv, Rothschild Prize.
  11. "2023 Class of Fellows". American Mathematical Society. Retrieved 2022-11-09.