Category Archives: Computer Science and Optimization

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

Cup 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 , , , , , , | 1 Comment

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

The AC0 Prime Number Conjecture

Möbius randomness and computational complexity Last spring Peter Sarnak gave a thought-provoking lecture in Jerusalem. (Here are the very interesting slides of a similar lecture at I.A.S.) Here is a variation of the type of questions Peter has raised. The Prime … Continue reading

Posted in Algebra and Number Theory, Computer Science and Optimization | Tagged , , , , | 13 Comments

IPAM remote blogging: The Many Facets of Linear Programming

The many facets of Linear Programming Here is an extremely nice paper by Michael Todd from 2001. It gives useful background for many lectures and it can serve as a good base point to examine last decade’s progress. Background post for … Continue reading

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

Günter Ziegler: 1000$ from Beverly Hills for a Math Problem. (IPAM remote blogging.)

Scanned letter by Zadeh. (c) Günter M. Ziegler left-to-right: 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 | 4 Comments

IPAM Remote Blogging: Santos-Weibel 25-Vertices 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 5-prismatoids”  A prismatoid is a polytope … Continue reading

Posted in Computer Science and Optimization, Conferences, Convex polytopes | 2 Comments

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

Posted in Computer Science and Optimization, Conferences, Convex polytopes | 3 Comments

Is Backgammon in P?

  The Complexity of Zero-Sum 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

Posted in Computer Science and Optimization, Games, Open problems, Probability | 9 Comments