Workshop on Beyond Worst-Case Analysis
September 19-21, 2011, Mackenzie Room, Huang Engineering Center, Stanford University |

September 19-21, 2011, Mackenzie Room, Huang Engineering Center, Stanford University.

September | |||
---|---|---|---|

9:00-9:30 | Breakfast and opening remarks |
Breakfast (provided) |
Breakfast (provided) |

9:30-10:30 | Avrim Blum | Uri Feige | Michael Mitzenmacher |

10:30-11:00 | Coffee (provided) | ||

11:00-12:00 | Nicole Immorlica Nina Balcan |
Kevin Leyton-Brown Short talks: Awasthi, Zadimoghaddam |
Short talks: Yan,
Daniely, Lopez-Ortiz, Mahoney |

12:00-1:00 | Lunch (provided) | ||

1:00-2:00 | Dan Spielman | Richard Karp | Shang-Hua Teng |

2:00-2:30 | Coffee (provided) | ||

2:30-4:00 | Andrea Montanari Andrew Goldberg |
Susanne Albers
Anupam Gupta C. Seshadri |
Ryan Williams
Ankur Moitra David Freeman |

4:00-4:30 | Coffee (provided) | ||

4:30-5:30 | Luca Trevisan | Panel Discussion | Bernard Chazelle |

5:30- | Workshop reception |

Video of all lectures and the panel discussion are here (through Stanford) or here (through youtube).

**Nicole Immorlica:** *PASS Approximation -- A Framework for Analyzing and Designing Heuristics*

Joint work with Uri Feige, Vahab Mirrokni, and Hamid Nazerzadeh.

**Dan Spielman:** *Smoothed Analysis of Numerical Algorithms*

**Andrea Montanari:** *The Set of Solutions of Random XORSAT Formulae*

**Andrew Goldberg:** *Shortest Path Algorithms: Theory and Practice*

Joint work with Ittai Abraham, Daniel Delling, Amos Fiat, Andreas Nowatzyk, and Renato Werneck.

**Luca Trevisan:** *Average-case Complexity -- A Survey*

We will talk about questions such as:

- What is going on in Levin's famously concise one-page paper on average-case NP-complete problems?

**Uri Feige:** *Universal Factor Graphs*

**Richard Karp:** *Effective Heuristics for NP-Hard Problems*

As a step in this direction we describe the evolution and validation of three heuristic algorithms.

**Susanne Albers:** *Competitive Analysis and Beyond*

**Anupam Gupta:** *Solving Optimization Problems Online, with Random Demands*

**C. Seshadri:** *Self-improving algorithms*

Joint work with Nir Ailon, Ken Clarkson, Bernard Chazelle, Ding Liu, and Wolfgang Mulzer.

**Michael Mitzenmacher:** *Worst Case Analysis : Our Strength is Our Weakness*

**Shang-Hua Teng:** *Optimization, Machine Learning, and Game Theory: From the Lens of Smoothed Analysis*

**Ryan Williams:** *Backdoors to Typical Case Complexity*

**Ankur Moitra:** *Pareto Optimal Solutions for Smoothed Analysts*

This is joint work with Ryan O'Donnell.

**David Freeman:** *Homomorphic Signatures: Message Integrity for Network Coding and Beyond*

This talk will cover joint research with Dan Boneh, Jon Katz, and Brent Waters.

**Bernard Chazelle:** *What Are Natural Algorithms?*

One of the main reasons for wanting to compute a Nash equilibrium of a game is to predict how players will play. However, if the game has multiple equilibria that are far apart, or approximate-equilibria that are far in variation distance from the true Nash equilibrium strategies, then this prediction may not be possible even in principle. Motivated by this, we define the notion of games that are approximation stable, meaning that all epsilon-approximate equilibria are contained inside a small ball of radius delta around a true equilibrium, and investigate a number of their properties. Many natural small games such as matching pennies and rock-paper-scissors are indeed approximation stable. We show furthermore there exist 2-player n-by-n approximation-stable games in which the Nash equilibrium and all approximate equilibria have support Omega(log n). On the other hand, we show all (epsilon,delta) approximation-stable games must have an epsilon-equilibrium of small support yielding an algorithm which improves over the bound of Lipton et al. for games satisfying this condition. We in addition give improved bounds for the case that epsilon and delta are sufficiently close together.

**Amit Daniely:** *Are stable instances easier?*

This is joint work with Nati Linial.

**Alex Lopez-Ortiz:** *Parameterized Analysis of On-line Algorithms*

It is well-established that input sequences for paging and list update have locality of reference.

**Michael Mahoney:** *Approximate computation and implicit
regularization in large-scale data analysis*

**Qiqi Yan:** *Prior-Independent Mechanisms via Resource Augmentation*

Based on joint work with Inbal Talgam-Cohen and Tim Roughgarden.

This is based on joint work with Vahab Mirrokni and Shayan Oveis Gharan.

Three nearby hotels are the Sheraton, the Westin, and Hotel Keen. Ask for Stanford University or corporate rate.

The workshop venue is in the Huang Center, see the map here. The Mackenzie Room is the "top of the octogon".

You have various options to get to the Huang Center. One is take the Marguerite (Stanford's free shuttle). See here for instructions. Note that the recommended hotels are all very close to the main (University Ave) Palo Alto Caltrain station. A second option is to park at the meters in closest parking lot, see here. We will also have a very limited number of "C" permits available for that lot.