Author Archives: Gil Kalai

The Trifference Problem

Posted on January 24, 2023 by Gil Kalai

Originally posted on Anurag's Math Blog:
What is the largest possible size of a set of ternary strings of length , with the property that for any three distinct strings in , there is a position where they all…

Posted in Uncategorized | 2 Comments

Greatest Hits 2015-2022, Part II

Posted on January 5, 2023 by Gil Kalai

This is the second part of Greatest Hits 2015-2022, Part I. Here are popular and favorite posts published in 2019-2022. 2019 Supremacy and Sensitivity (and Sunflowers) Test your intuition 38 was contributed in March 2019 by my youngest son Lior. … Continue reading →

Posted in Uncategorized | Leave a comment

Greatest Hits 2015-2022, Part I

Posted on January 1, 2023 by Gil Kalai

In February 2015 I wrote a post on the blog’s greatest hits in the first seven years, and its time to write a similar post for the eight years that followed. Quick updates: In recent months I took part in … Continue reading →

Posted in Uncategorized | 3 Comments

Tel Aviv University Theory Fest is Starting Tomorrow

Posted on December 25, 2022 by Gil Kalai

Tel Aviv University Theory Fest, December 26-December 28 2022. Cryptography workshop @ TAU TheoryFest December 29, 2022 TAU 2022 TheoryFest, December 26-28, 2022 The Theory of Computing was born as a purely mathematical investigation into the notion of computation. From … Continue reading →

Posted in Computer Science and Optimization, Conferences | Tagged | Leave a comment

Alef’s Corner

Posted on December 19, 2022 by Gil Kalai

 

Posted in Art | Tagged | Leave a comment

A Nice Example Related to the Frankl Conjecture

Posted on November 30, 2022 by Gil Kalai

Update: Peter Frankl brought to my attention that the very same example appeared in a paper by Dynkin and Frankl “Extremal sets of subsets satisfying conditions induced by a graph“. The example As a follow up to my previous post … Continue reading →

Posted in Combinatorics, Open discussion, Open problems | Tagged , , , , , , , , , , | 7 Comments

Amazing: Justin Gilmer gave a constant lower bound for the union-closed sets conjecture

Posted on November 17, 2022 by Gil Kalai

Frankl’s conjecture (aka the union closed sets conjecture) asserts that if is a family of subsets of [n] (=: ) which is closed under union then there is an element such that Justin Gilmer just proved an amazing weaker form … Continue reading →

Posted in Combinatorics, Open problems | Tagged , , | 17 Comments

Barnabás Janzer: Rotation inside convex Kakeya sets

Posted on November 16, 2022 by Gil Kalai

Barnabás Janzer studied the following question: Suppose we have convex body in that contains a copy of a convex body in every orientation. Is it always possible to move any one copy of to another copy of , keeping inside … Continue reading →

Posted in Convexity, Test your intuition | Tagged , | 1 Comment

Inaugural address at the Hungarian Academy of Science: The Quantum Computer – A Miracle or Mirage

Posted on November 5, 2022 by Gil Kalai

(Picture: János Pach) The Quantum Computer – A Miracle or Mirage inaugural address of Gil Kalai honorary member of the MTA, Budapest, 15 June, 2022, 15:00 Abstract: On February 12, 2002, Michel Devoret’s lecture entitled “The Quantum Computers: Miracle or … Continue reading →

Posted in Academics, Computer Science and Optimization, Physics, Quantum | Tagged , , | 3 Comments

Remarkable: “Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage,” by Xun Gao, Marcin Kalinowski, Chi-Ning Chou, Mikhail D. Lukin, Boaz Barak, and Soonwon Choi

Posted on October 25, 2022 by Gil Kalai

In this post I would like to report about an important paper (posted Dec. 2021) by Xun Gao, Marcin Kalinowski, Chi-Ning Chou, Mikhail D. Lukin, Boaz Barak, and Soonwon Choi. (I am thankful to Xun Gao and  Boaz Barak for … Continue reading →

Posted in Quantum, Statistics | Tagged , , , , , | 1 Comment