Category Archives: Computer Science and Optimization

Ann Lehman’s Sculpture Based on Herb Scarf’s Maximal Lattice Free Convex Bodies

Maximal lattice-free convex bodies introduced by Herb Scarf and the related complex of maximal lattice free simplices (also known as the Scarf complex) are remarkable geometric constructions with deep connections to combinatorics, convex geometry, integer programming, game theory, fixed point computations, … Continue reading

Posted in Art, Computer Science and Optimization, Economics, Games | Tagged , | 3 Comments

Symplectic Geometry, Quantization, and Quantum Noise

Over the last two meetings of our HU quantum computation seminar we heard two talks about symplectic geometry and its relations to quantum mechanics and quantum noise. Yael Karshon: Manifolds, symplectic manifolds, Newtonian mechanics, quantization, and the non squeezing theorem. … Continue reading

Posted in Computer Science and Optimization, Geometry, Physics | Tagged , , , , , , | 6 Comments

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 | 8 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 , , , | 3 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