Category Archives: Computer Science and Optimization

Igor Pak: What if they are all wrong?

Posted on January 19, 2021 by Gil Kalai

Originally posted on Igor Pak's blog:
Conjectures are a staple of mathematics. They are everywhere, permeating every area, subarea and subsubarea. They are diverse enough to avoid a single general adjective. They come in al shapes and sizes. Some…

Posted in Combinatorics, Computer Science and Optimization, Geometry, What is Mathematics | Tagged | 5 Comments

Open problem session of HUJI-COMBSEM: Problem #5, Gil Kalai – the 3ᵈ problem

Posted on January 10, 2021 by Gil Kalai

This post continues to describe problems presented at our open problems session back in November 2020. Here is the first post in the series.  Today’s problem was presented by me, and it was an old 1989 conjecture of mine. A … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Geometry, Open problems | 5 Comments

The Argument Against Quantum Computers – A Very Short Introduction

Posted on December 29, 2020 by Gil Kalai

Left: Gowers’s book Mathematics a very short introduction. Right C. elegans; Boson Sampling can be seen as the C. elegans of quantum computing. (See, this paper.) Update (January 6, 2021): Tomorrow January, 7, 8:30 AM Israel time, I give a … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Physics, Probability, Quantum | Tagged , | 7 Comments

To Cheer You Up in Difficult Times 15: Yuansi Chen Achieved a Major Breakthrough on Bourgain’s Slicing Problem and the Kannan, Lovász and Simonovits Conjecture

Posted on December 21, 2020 by Gil Kalai

This post gives some background to  a recent amazing breakthrough  paper: An Almost Constant Lower Bound of the Isoperimetric Coefficient in the KLS Conjecture by Yuansi Chen. Congratulations Yuansi! The news Yuansi Chen gave an almost constant bounds for Bourgain’s … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Convexity, Geometry | Tagged | 2 Comments

Open problem session of HUJI-COMBSEM: Problem #3, Ehud Friedgut – Independent sets and Lionel Levine’s infamous hat problem.

Posted on December 12, 2020 by Gil Kalai

Here are the two problems presented by Ehud Friedgut. The first arose by Friedgut, Kindler, and me in the context of studying  Lionel Levine’s infamous hat problem. The second is Lionel Levine’s infamous hat problem. Ehud Friedgut with a few … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Probability | Tagged , , | 6 Comments

To cheer you up in difficult times 4: Women In Theory present — I will survive

Posted on May 11, 2020 by Gil Kalai

An amazing video (Update, May18 2020). I failed to explain what WIT is and this may have caused some misunderstanding. Here is a description from the Simons Institute site. “The Women in Theory (WIT) Workshop is intended for graduate and … Continue reading →

Posted in Academics, Combinatorics, Computer Science and Optimization, Convexity, Games, Philosophy, Poetry, What is Mathematics, Women in science | 14 Comments

To cheer you up in difficult times 3: A guest post by Noam Lifshitz on the new hypercontractivity inequality of Peter Keevash, Noam Lifshitz, Eoin Long and Dor Minzer

Posted on May 8, 2020 by Gil Kalai

This is a guest post kindly contributed by Noam Lifshitz. My short introduction: There is nothing like a new hypercontractivity inequality to cheer you up in difficult times and this post describes an amazing new hypercontractivity inequality.  The post describes … Continue reading →

Posted in Analysis, Combinatorics, Computer Science and Optimization, Guest post, Poetry, Probability | Tagged , , , , | 4 Comments

To cheer you up in difficult times II: Mysterious matching news by Gal Beniamini, Naom Nisan, Vijay Vazirani and Thorben Tröbst!

Posted on April 19, 2020 by Gil Kalai

Matching is one of the richest gold mines for ideas and results in mathematics, computer science and other areas.  Today I want to briefly tell you about a curious, surprising, mysterious, and cheerful recent result by Gal Beniamini and Noam … Continue reading →

Posted in Combinatorics, Computer Science and Optimization | Tagged , , , | 10 Comments

Game Theory – on-line Course at IDC, Herzliya

Posted on March 29, 2020 by Gil Kalai

Game theory, a graduate course at IDC, Herzliya; Lecturer: Gil Kalai; TA: Einat Wigderson,  ZOOM mentor: Ethan. Starting Tuesday March 31, I am giving an on-line course (in Hebrew) on Game theory at IDC, Herzliya (IDC English site; IDC Chinese … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Economics, Games, Rationality, Teaching | Tagged , | 2 Comments

Kelman, Kindler, Lifshitz, Minzer, and Safra: Towards the Entropy-Influence Conjecture

Posted on March 22, 2020 by Gil Kalai

Let me briefly report on a remarkable new paper by Esty Kelman, Guy Kindler, Noam Lifshitz, Dor Minzer, and Muli Safra, Revisiting Bourgain-Kalai and Fourier Entropies. The paper describes substantial progress towards the Entropy-Influence conjecture, posed by Ehud Friedgut and … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Open problems | Tagged , , , , | 1 Comment