Category Archives: Computer Science and Optimization

Conference on High Dimensional Combinatorics, April 22-26 2018

Posted on April 7, 2018 by

Conference on High Dimensional Combinatorics Conference home-page Dates: April 22-26, 2018 Place: Israel Institute for Advanced Studies, The Hebrew University of Jerusalem Organizers: Alex Lubotzky, Tali Kaufman and Oren Becker Registration form: click here Registration deadline: April 13, 2018 Combinatorics in general and the theory … Continue reading →

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

Monday February 19: Quantum Coding and High Dimensional Expanders

Posted on February 14, 2018 by

Tonight at 8:00 Israel time TCS+ Dor Misner on 2-to-2 games.    On Monday, February 19, we will have a special day on “Quantum Coding and High Dimensional Expanders” organized by Gilles Zemor. Sandwiches will be served for lunch, alongside … Continue reading →

Posted in Combinatorics, Computer Science and Optimization, Conferences, Quantum, Updates | Tagged , | 2 Comments

My Argument Against Quantum Computers: An Interview with Katia Moskvitch on Quanta Magazine

Posted on February 8, 2018 by

Quanta Magazine published an interview with me about quantum computers. It was a pleasure discussing this issue with Katia Moskvitch and I enjoyed also the photo session with David Vaaknin who also took a video of me explaining the importance of … Continue reading →

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

Akshay Venkatesh Lectures at HUJI – Ostrowski’s Prize Celebration, January 24&25

Posted on January 23, 2018 by

Thursday January 25, 14:15-15:45 Ostrowski’s prize ceremony and Akshay Venkatesh’s prize lecture: Period maps and Diophantine problems Followed by a Basic notion lecture by Frank Calegary 16:30-17:45: The cohomology of arithmetic groups and Langlands program Wednesday January 24, 18:00-17:00: Akshay Venkatesh … Continue reading →

Posted in Algebra and Number Theory, Computer Science and Optimization, Geometry, Updates | Tagged , , | Leave a comment

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

Posted on January 21, 2018 by

Lior Silberman asked about applications of the 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 post on … Continue reading →

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

Subhash Khot, Dor Minzer and Muli Safra completed the proof of the 2-to-2 Games Conjecture

Posted on January 10, 2018 by

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

Posted on January 8, 2018 by

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 , , | 9 Comments

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

Posted on January 6, 2018 by

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

Posted on December 20, 2017 by

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

Posted on December 15, 2017 by

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