Recent Comments

Recent Posts
 Jirka
 AviFest, AviStories and Amazing Cash Prizes.
 Polymath 10 post 6: The ErdosRado sunflower conjecture, and the Turan (4,3) problem: homological approaches.
 Polymath 10 Emergency Post 5: The ErdosSzemeredi Sunflower Conjecture is Now Proven.
 Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem!
 More Math from Facebook
 The Erdős Szekeres polygon problem – Solved asymptotically by Andrew Suk.
 The Quantum Computer Puzzle @ Notices of the AMS
 Three Conferences: Joel Spencer, April 2930, Courant; Joel Hass May 2022, Berkeley, Jean Bourgain May 2124, IAS, Princeton
Top Posts & Pages
 The Erdős Szekeres polygon problem  Solved asymptotically by Andrew Suk.
 Polymath 10 Emergency Post 5: The ErdosSzemeredi Sunflower Conjecture is Now Proven.
 Believing that the Earth is Round When it Matters
 Extremal Combinatorics III: Some Basic Theorems
 A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24
 Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
 Mind Boggling: Following the work of Croot, Lev, and Pach, Jordan Ellenberg settled the cap set problem!
 Combinatorics, Mathematics, Academics, Polemics, ...
 יופיה של המתמטיקה
RSS
Category Archives: Computer Science and Optimization
Günter Ziegler: 1000$ from Beverly Hills for a Math Problem. (IPAM remote blogging.)
Scanned letter by Zadeh. (c) Günter M. Ziegler lefttoright: David Avis, Norman Zadeh, Oliver Friedmann, and Russ Caflish (IPAM director). Photo courtesy Eddie Kim. Update: The slides for Friedmann’s talk are now available. The conference schedule page contains now the slides for … Continue reading
Posted in Computer Science and Optimization, Conferences, Guest blogger
Tagged Linear programming
4 Comments
IPAM Remote Blogging: SantosWeibel 25Vertices Prismatoid and Prismatoids with large Width
Here is a web page by Christope Weibel on the improved counterexample. The IPAM webpage contains now slides of some of the lectures. Here are Santos’s slides. The last section contains some recent results on the “width of 5prismatoids” A prismatoid is a polytope … Continue reading
Remote Blogging: Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?
Here are some links and posts related to some of the talks in IPAM’s workshop “Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?” I will be happy to add links to pdf’s of the presentations and to relevant papers. Descriptions and … Continue reading
Is Backgammon in P?
The Complexity of ZeroSum Stochastic Games with Perfect Information Is there a polynomial time algorithm for chess? Well, if we consider the complexity of chess in terms of the board size then it is fair to think that the answer is … Continue reading
To Life, to Science and to Innovations
ICS2011 at ITCS, Tsinghua University, Beijing, China The title of this post “To life, to Science and to Innovations” was Silvio Micali’s toast at the second conference on Innovations in Computer Science and Silvio’s words have a good chance of becomeing the official toast of … Continue reading
Analysis of Boolean Functions
I discovered a vidiotaped lecture I gave at the Open University on the 3rd Israeli Theory Day. Enjoy! http://www.youtube.com/watch?v=xbJe7ioCISM Posts related to this lecture: Noise Stability and threshold circuits; Noise stability lecture and tales; Nati’s influence.
Posted in Computer Science and Optimization
3 Comments
Aaronson and Arkhipov’s Result on Hierarchy Collapse
Scott Aaronson gave a thoughtprovoking lecture in our Theory seminar three weeks ago. (Actually, this was eleven months ago.) The slides are here . The lecture discussed two results regarding the computational power of quantum computers. One result from this paper gives an … Continue reading
Octonions to the Rescue
Xavier Dahan and JeanPierre Tillich’s Octonionbased Ramanujan Graphs with High Girth. Update (February 2012): Non associative computations can be trickier than we expect. Unfortunately, the paper by Dahan and Tillich turned out to be incorrect. Update: There is more to … Continue reading
Subexponential Lower Bound for Randomized Pivot Rules!
Oliver Friedmann, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form for the following two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding … Continue reading
IPAM Workshop – Efficiency of the Simplex Method: Quo vadis Hirsch conjecture?
Workshop at IPAM: January 18 – 21, 2011 Here is the link to the IPAM conference.