- Gil’s Collegial Quantum Supremacy Skepticism FAQ
- Amazing! Keith Frankston, Jeff Kahn, Bhargav Narayanan, Jinyoung Park: Thresholds versus fractional expectation-thresholds
- Starting today: Kazhdan Sunday seminar: “Computation, quantumness, symplectic geometry, and information”
- The story of Poincaré and his friend the baker
- Gérard Cornuéjols’s baker’s eighteen 5000 dollars conjectures
- Noisy quantum circuits: how do we know that we have robust experimental outcomes at all? (And do we care?)
- Test Your Intuition 40: What Are We Celebrating on Sept, 28, 2019? (And answer to TYI39.)
Top Posts & Pages
- Gil's Collegial Quantum Supremacy Skepticism FAQ
- TYI 30: Expected number of Dice throws
- Lior, Aryeh, and Michael
- Elchanan Mossel's Amazing Dice Paradox (your answers to TYI 30)
- Amazing: Hao Huang Proved the Sensitivity Conjecture!
- Aubrey de Grey: The chromatic number of the plane is at least 5
- Jeff Kahn and Jinyoung Park: Maximal independent sets and a new isoperimetric inequality for the Hamming cube.
Tag Archives: Rudolph Alswede
Hardness of Approximating Vertex Cover, Polytope-Integrality-Gap, the Alswede-Kachatrian theorem, and More.
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