### 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 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)
- Polymath 10 Post 3: How are we doing?

### Top Posts & Pages

- A Breakthrough by Maryna Viazovska Leading to the Long Awaited Solutions for the Densest Packing Problem in Dimensions 8 and 24
- Seven Problems Around Tverberg's Theorem
- The Quantum Computer Puzzle @ Notices of the AMS
- Stefan Steinerberger: The Ulam Sequence
- Answer: Lord Kelvin, The Age of the Earth, and the Age of the Sun
- Three Conferences: Joel Spencer, April 29-30, Courant; Joel Hass May 20-22, Berkeley, Jean Bourgain May 21-24, IAS, Princeton
- Polymath10-post 4: Back to the drawing board?
- Polymath10: The Erdos Rado Delta System Conjecture
- Can Category Theory Serve as the Foundation of Mathematics?

### RSS

# Category Archives: Computer Science and Optimization

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

## 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 thought-provoking 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 Jean-Pierre Tillich’s Octonion-based 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.

## Drunken Time and Drunken Computation

The problem We are used to computer programs or models for computations that perform at time step , . Suppose that time is drunk, so instead of running these steps in their correct order, we apply at time step , where … Continue reading

Posted in Computer Science and Optimization
10 Comments

## Noise Stability and Threshold Circuits

The purpose of this post is to describe an old conjecture (or guesses, see this post) by Itai Benjamini, Oded Schramm and myself (taken from this paper) on noise stability of threshold functions. I will start by formulating the conjectures and … Continue reading