Category Archives: Computer Science and Optimization

Lionel Pournin found a combinatorial proof for Sleator-Tarjan-Thurston diameter result

I just saw in Claire Mathieu’s blog  “A CS professor blog” that a simple proof of the Sleator-Tarjan-Thurston’s diameter result for the graph of the associahedron was found by Lionel Pournin! Here are slides of his lecture “The diameters of associahedra” … Continue reading

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

The Quantum Debate is Over! (and other Updates)

Quid est noster computationis mundus? Nine months after is started, (much longer than expected,) and after eight posts on GLL, (much more than planned,)  and almost a thousand comments of overall good quality,   from quite a few participants, my … Continue reading

Posted in Combinatorics, Computer Science and Optimization, Controversies and debates, Updates | Tagged , , | 3 Comments

The Quantum Fault-Tolerance Debate Updates

In a couple of days, we will resume the debate between Aram Harrow and me regarding the possibility of universal quantum computers and quantum fault tolerance. The debate takes place over GLL (Godel’s Lost Letter and P=NP) blog. The Debate Where were … Continue reading

Posted in Computer Science and Optimization, Controversies and debates, Physics, Updates | Tagged , | 5 Comments

Greg Kuperberg: It is in NP to Tell if a Knot is Knotted! (under GRH!)

Wolfgang Haken found an algorithm to tell if a knot is trivial, and, more generally with Hemion, if two knots are equivalent. Joel Hass, Jeff Lagarias and Nick Pippinger proved in 1999 that telling that a knot is unknotted is … Continue reading

Posted in Computer Science and Optimization, Geometry | Tagged | 9 Comments

Updates, Boolean Functions Conference, and a Surprising Application to Polytope Theory

The Debate continues The debate between Aram Harrow and me on Godel Lost letter and P=NP (GLL) regarding quantum fault tolerance continues. The first post entitled Perpetual  motions of the 21th century featured mainly my work, with a short response by Aram. … Continue reading

Posted in Art, Computer Science and Optimization, Controversies and debates, Convex polytopes, Updates | Tagged | Leave a comment

A Discussion and a Debate

Heavier than air flight of the 21 century? The very first post on this blog entitled “Combinatorics, Mathematics, Academics, Polemics, …” asked the question “Are mathematical debates possible?” We also had posts devoted to debates and to controversies. A few days ago, … Continue reading

Posted in Computer Science and Optimization, Controversies and debates, Information theory, Physics | Tagged , , | 5 Comments

Fractional Sylvester-Gallai

Avi Wigderson was in town and gave a beautiful talk about an extension of Sylvester-Gallai theorem. Here is a link to the paper: Rank bounds for design matrices with applications to combinatorial geometry and locally correctable codes by Boaz Barak, Zeev … Continue reading

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

Ryan O’Donnell: Analysis of Boolean Function

Ryan O’Donnell has begun writing a book about Fourier analysis of Boolean functions and  he serializes it on a blog entiled Analysis of Boolean Function.  New sections appear on Mondays, Wednesdays, and Fridays. Besides covering the basic theory, Ryan intends to describe applications … Continue reading

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

Cap Sets, Sunflowers, and Matrix Multiplication

This post follows a recent paper On sunflowers  and matrix multiplication by Noga Alon, Amir Spilka, and Christopher Umens (ASU11) which rely on an earlier paper Group-theoretic algorithms for matrix multiplication, by Henry Cohn, Robert Kleinberg, Balasz Szegedy, and Christopher Umans (CKSU05), … Continue reading

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

Projections to the TSP Polytope

Michael Ben Or told me about the following great paper Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds by Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary and Ronald de Wolf. The paper solves an old conjecture … Continue reading

Posted in Computer Science and Optimization, Convex polytopes | Tagged , , , | 1 Comment