### Recent Comments

dinostraurio on Seven Problems Around Tverberg… Matthew Cory on The Quantum Computer Puzzle @… Matthew Cory on The Quantum Computer Puzzle @… The Quantum Computer… on A Breakthrough by Maryna Viazo… The Quantum Computer… on Stefan Steinerberger: The Ulam… The Quantum Computer… on Polymath10-post 4: Back to the… Philip Gibbs on Stefan Steinerberger: The Ulam… Philip Gibbs on Stefan Steinerberger: The Ulam… Daniel on Stefan Steinerberger: The Ulam… Philip Gibbs on Stefan Steinerberger: The Ulam… Gil Kalai on Stefan Steinerberger: The Ulam… Gabriel Nivasch on Stefan Steinerberger: The Ulam… -
### Recent Posts

- The Erdős Szekeres polygon problem – Solved asymptotically by Andrew Suk.
- The Quantum Computer Puzzle @ Notices of the AMS
- Three Conferences: Joel Spencer, April 29-30, Courant; Joel Hass May 20-22, Berkeley, Jean Bourgain May 21-24, IAS, Princeton
- Math and Physics Activities at HUJI
- Stefan Steinerberger: The Ulam Sequence
- TYI 26: Attaining the Maximum
- A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24
- Polymath10-post 4: Back to the drawing board?
- News (mainly polymath related)

### Top Posts & Pages

- The Erdős Szekeres polygon problem - Solved asymptotically by Andrew Suk.
- A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24
- Why Quantum Computers Cannot Work: The Movie!
- The Quantum Computer Puzzle @ Notices of the AMS
- Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
- Polymath10-post 4: Back to the drawing board?
- Polymath10: The Erdos Rado Delta System Conjecture
- Greatest Hits
- Two Math Riddles

### RSS

# Category Archives: Computer Science and Optimization

## 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

## 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

## 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 Avi Wigderson, Codes, Greg Kuperberg, Sylvester-Gallai
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

## 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

## 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

## 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

## 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

## 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 Linear programming
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