Recent Comments
-
Recent Posts
- Algorithmic Game Theory: Past, Present, and Future
- Richard Stanley: Enumerative and Algebraic Combinatorics in the1960’s and 1970’s
- Igor Pak: How I chose Enumerative Combinatorics
- Quantum Computers: A Brief Assessment of Progress in the Past Decade
- Noga Alon and Udi Hrushovski won the 2022 Shaw Prize
- Oliver Janzer and Benny Sudakov Settled the Erdős-Sauer Problem
- Past and Future Events
- Joshua Hinman proved Bárány’s conjecture on face numbers of polytopes, and Lei Xue proved a lower bound conjecture by Grünbaum.
- Amazing: Jinyoung Park and Huy Tuan Pham settled the expectation threshold conjecture!
Top Posts & Pages
- Algorithmic Game Theory: Past, Present, and Future
- Amazing: Jinyoung Park and Huy Tuan Pham settled the expectation threshold conjecture!
- The Argument Against Quantum Computers - A Very Short Introduction
- Oliver Janzer and Benny Sudakov Settled the Erdős-Sauer Problem
- Combinatorics, Mathematics, Academics, Polemics, ...
- Quantum Computers: A Brief Assessment of Progress in the Past Decade
- TYI 30: Expected number of Dice throws
- Game Theory 2021
- Richard Stanley: Enumerative and Algebraic Combinatorics in the1960’s and 1970’s
RSS
Category Archives: Computer Science and Optimization
Is HQCA Possible? A conversation with Michael Brooks
Here is a short email interview from April 2021 with Michael Brooks from “New Scientist”. Dear Professor Kalai, I’m writing a short feature for New Scientist magazine on the theme “Will we ever have a useful quantum computer?”. I’m aware … Continue reading
Good Codes papers are on the arXiv
Here are some links to the breakthrough papers about error correcting codes that I mentioned in this post. The results about locally testable codes with constant rate distance and locality was achieved independently in papers 1 and 2. 1) Locally … Continue reading
Dream a Little Dream: Quantum Computer Poetry for the Skeptics (Part II, The Classics)
Quantum poetry for the skeptics had long roots, and, also here, Peter Shor along with Jennifer Shor had a pioneering role. Volker Strassen’s response is the earliest poem known to me on the skeptics’ side. We will start with Jennifer … Continue reading
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
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 Alex Lubotzky, Irit Dinur, Ron Livne, Shahar Mozes, Shai Evra
4 Comments
To cheer you up in difficult times 23: the original hand-written slides of Terry Tao’s 2015 Einstein Lecture in Jerusalem
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
The probabilistic proof that 2^400-593 is a prime: a revolutionary new type of mathematical proof, or not a proof at all?
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
Cheerful News in Difficult Times: The Abel Prize is Awarded to László Lovász and Avi Wigderson
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
Amazing: Feng Pan and Pan Zhang Announced a Way to “Spoof” (Classically Simulate) the Google’s Quantum Supremacy Circuit!
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 Feng Pan, Pan Zhang, Quantum computation
7 Comments
And the Oscar goes to: Meir Feder, Zvi Reznic, Guy Dorman, and Ron Yogev
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 Guy Dorman, Meir Feder, Ron Yogev, Zvi Reznic
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
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 Adi Shraibman, Nati Linial
3 Comments