Category Archives: Computer Science and Optimization

Hardness of Approximating Vertex Cover, Polytope-Integrality-Gap, the Alswede-Kachatrian theorem, and More.

Lior Silberman asked about applications of the new Khot-Minzer-Safra 2-to-2 game theorem to hardness of approximation, and James Lee answered mentioning applications to vertex cover. Let me elaborate a little on vertex cover, and other matters. (Here is the pervious … Continue reading

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

Subhash Khot, Dor Minzer and Muli Safra proved the 2-to-2 Games Conjecture

Update: A related blog post by Boaz Barak: Unique Games Conjecture – halfway there? The 2-to-2 Games Conjecture is a somewhat weaker form of Khot’s unique game conjecture. The paper is: Pseudorandom Sets in Grassmann Graph have Near-Perfect Expansion by Subhash Khot, Dor … Continue reading

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

Cody Murray and Ryan Williams’ new ACC breakthrough: Updates from Oded Goldreich’s Choices

Thanks to Irit Dinur for telling me about the following: Oded Goldreich’s recent choice is about the paper: Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP, by Corry Murray and Ryan Williams. Ryan Williams … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Updates | Tagged , , | 8 Comments

Yael Tauman Kalai’s ICM2018 Paper, My Paper, and Cryptography

Yael Tauman Kalai: Delegating Computation via No-Signaling Strategies. Ladies and Gentelmen,  Here is, exclusively for our readers, Yael Tauman Kalai’s ICM2018 paper: Delegating Computation via No-Signaling Strategies. The opportunity to present the paper arose when a week ago I attended … Continue reading

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

Third third of my ICM 2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome

Update: Here is a combined version of all three parts: Three puzzles on mathematics computations and games. Thanks for the remarks and corrections. More corrections and comments welcome. Dear all, here is the draft of the third third of my … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Open problems, Physics, Quantum | Tagged , | 3 Comments

Second third of my ICM 2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome

Update: Here is a combined version of all three parts: Three puzzles on mathematics computations and games. Thanks for the remarks and corrections. More corrections and comments welcome. Dear all, here is the draft of the second third of my paper … Continue reading

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

First third of my ICM2018 paper – Three Puzzles on Mathematics, Computation and Games. Corrections and comments welcome

Update: Here is a combined version of all three parts: Three puzzles on mathematics computations and games. Thanks for the remarks and corrections. More corrections and comments welcome. I have a very strict December 20 deadline (self-imposed, I missed the … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Games, Updates | Tagged | 12 Comments

Must-read book by Avi Wigderson

Originally posted on Windows On Theory:
Avi Wigderson is one of the most prolific and creative theoretical computer scientists (in fact, he is one of the most prolific and creative scientists, period). Over the last several years, Avi had worked…

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

High Dimensional Combinatorics at the IIAS – Program Starts this Week; My course on Helly-type theorems; A workshop in Sde Boker

The academic year starts today. As usual it is very hectic and it is wonderful to see the ever younger and younger students. Being a TelAvivian in residence in the last few years, I plan this year to split my … Continue reading

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

If Quantum Computers are not Possible Why are Classical Computers Possible?

As most of my readers know, I regard quantum computing as unrealistic. You can read more about it in my Notices AMS paper and its extended version (see also this post) and in the discussion of Puzzle 4 from my … Continue reading

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