Category Archives: Computer Science and Optimization

To Cheer you up in difficult times 30: Irit Dinur, Shai Evra, Ron Livne, Alex Lubotzky, and Shahar Mozes Constructed Locally Testable Codes with Constant Rate, Distance, and Locality

Posted on September 17, 2021 by Gil Kalai

The Simons Institute announces an October 6, 2021 lecture by Irit Dinur with the result in the title. This is a wonderful breakthrough. I am glad to mention that I have altogether 170 combined years of friendships with the authors. … Continue reading →

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

To cheer you up in difficult times 23: the original hand-written slides of Terry Tao’s 2015 Einstein Lecture in Jerusalem

Posted on May 14, 2021 by Gil Kalai

In 2015 Terry Tao gave the Einstein lecture of the Israeli Academy for Science and Humanities. We got hold of the original signed hand-written slides of Terry’s lecture and we are happy to share them with you. The title of … Continue reading →

Posted in Analysis, Applied mathematics, Computer Science and Optimization, Physics, What is Mathematics | Tagged | Leave a comment

The probabilistic proof that 2^400-593 is a prime: a revolutionary new type of mathematical proof, or not a proof at all?

Posted on April 22, 2021 by Gil Kalai

Avi Wigderson gave a great CS colloquium talk at HUJI on Monday (a real auditorium talk with an audience of about 200 people). The title of the talk was The Value of Errors in Proofs – a fascinating journey from … Continue reading →

Posted in Computer Science and Optimization, Controversies, Philosophy, What is Mathematics | Tagged , , | 15 Comments

Cheerful News in Difficult Times: The Abel Prize is Awarded to László Lovász and Avi Wigderson

Posted on March 17, 2021 by Gil Kalai

The Abel Prize was awarded earlier today to László Lovász and Avi Wigderson “for their foundational contributions to theoretical computer science and discrete mathematics, and their leading role in shaping them into central fields of modern mathematics.” Congratulations to Laci … Continue reading →

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

Amazing: Feng Pan and Pan Zhang Announced a Way to “Spoof” (Classically Simulate) the Google’s Quantum Supremacy Circuit!

Posted on March 10, 2021 by Gil Kalai

Feng Pan and Pan Zhang uploaded a new paper on the arXive  “Simulating the Sycamore supremacy circuits.” with an amazing announcement. Abstract: We propose a general tensor network method for simulating quantum circuits. The method is massively more efficient in … Continue reading →

Posted in Computer Science and Optimization, Physics, Quantum | Tagged , , | 1 Comment

And the Oscar goes to: Meir Feder, Zvi Reznic, Guy Dorman, and Ron Yogev

Posted on February 16, 2021 by Gil Kalai

My mother Carmela Kalai often said that if there was something she is thankful for it was that she was born in the era of movies. Indeed, she loved movies from a very early age throughout her life.  So, I … Continue reading →

Posted in Computer Science and Optimization, Information theory, Movies | Tagged , , , | 1 Comment

To cheer you up in difficult times 19: Nati Linial and Adi Shraibman construct larger corner-free sets from better numbers-on-the-forehead protocols

Posted on February 3, 2021 by Gil Kalai

What will be the next polymath project? click here for our previous post.  Number on the forehead, communication complexity, and additive combinatorics Larger Corner-Free Sets from Better NOF Exactly-N Protocols, by Nati Linial and Adi Shraibman Abstract: A subset of … Continue reading →

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

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 | 7 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