--------------------------

Lower Bounds for Local Search by Quantum Arguments

Scott Aaronson

On sums of independent random variables with unbounded variance, and estimating the average degree in a graph.

Uriel Feige

Approximating the Cut-Norm via Grothendieck's Inequality

Noga Alon, Assaf Naor

Counting Complexity Classes for Numeric Computations II:Algebraic and Semialgebraic Sets

Peter Buergisser, Felipe Cucker

Graph Entropy and Quantum Sorting Problems

Andrew Yao

Approximating k-node connected subgraphs via critical graphs

Guy Kortsarz, Zeev Nutov

The difficulty of testing for isomorphism against a graph that is given in advance

Eldar Fischer

Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size

Ran Raz

A Conjecture about Polynomial Time Computable Lattice-Lattice Functions

Miklos Ajtai

Completeness in Two-Party Secure Computation - A Computational View

Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen

Robust PCPs of Proximity, Shorter PCPs and Applications to Coding

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil Vadhan

An approximate Konig's theorem for edge coloring weighted bipartite graphs

Jose Correa, Michel Goemans

Sharp thresholds for monotone properties in random geometric graphs

Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari

Multilinear Formulas and Skepticism of Quantum Computing

Scott Aaronson

Coresets for k-Means and k-Median Clustering and their Applications

Sariel Har-Peled, Soham Mazumdar

On the Performance of Greedy Algorithms in Packet Buffering

Susanne Albers, Markus Schmidt

Concurrent flows in O(1/epsilon) time

Daniel Bienstock, Garud Iyengar

Boosted Sampling: Approximation Algorithms for Stochastic Optimization

Anupam Gupta, Martin Pal, R. Ravi, Amitabh Sinha

A New PCP Outer Verifier with Applications to Homogeneous Linear Equations and Max-Bisection

Jonas Holmerin, Subhash Khot

Adaptive Routing with End-to-End feedback: Distributed Learning and Geometric Approaches

Baruch Awerbuch, Robert Kleinberg

The All-or-Nothing Multicommodity Flow Problem

Chandra Chekuri, Sanjeev Khanna, Bruce Shepherd

Isotopic implicit surface meshing

Jean-Daniel Boissonnat, David Cohen-Steiner, Gert Vegter

Algorithms for Dynamic Geometric Problems over Data Streams

Piotr Indyk

The Spending Constraint Model for Market Equilibrium: Algorithmic, Existence and Uniqueness results

Nikhil Devanur, Vijay Vazirani

Better Extractors for Better Codes?

Venkatesan Guruswami

Collective Asynchronous Reading with Polylogarithmic Worst-Case Overhead

Bogdan Chlebus, Dariusz Kowalski, Alexander Shvartsman

Exponential separation of quantum and classical one-way communication complexity

Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis

The quantum adiabatic optimization algorithm and local minima

Ben Reichardt

Approximate max-integral-flow/min-multicut theorems

Kenji Obata

A fully dynamic reachability algorithm for directed graphs with an almost linear update time

Liam Roditty, Uri Zwick

Sorting and searching in the presence of memory faults (without redundancy)

Irene Finocchi, Giuseppe F. Italiano

Spectral Partitioning, Eigenvalue Bounds, and Circle Packings for Graphs of Bounded Genus

Jonathan Kelner

Derandomizing Homomorphism Testing in General Groups

Amir Shpilka, Avi Wigderson

The zero-one principle for switching networks

Yossi Azar, Yossi Richter

Hit-and-run from a corner

Laszlo Lovasz, Santosh Vempala

Primal-Dual Algorithms for Deterministic Inventory Problems

Retsef Levi, Robin Roundy, David Shmoys

Typical Properties of Winners and Losers in Discrete Optimization

Rene Beier, Berthold Voecking

Asymmetric K-Center is log* n Hard to Approximate

Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor

Low Distortion Maps Between Point Sets

Claire Kenyon, Yuval Rabani, Alistair Sinclair

Bounded-Concurrent Secure Multi-Party Computation with a Dishonest Majority

Rafael Pass

A Simple Polynomial-time Rescaling Algorithm for Solving Linear Programs

John Dunagan, Santosh Vempala

(Almost) Tight Bounds and Existence Theorems for Confluent Flows

Jiangzhuo Chen, Robert Kleinberg, Laszlo Lovasz, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta

Auction Algorithms for Market Equilibrium

Sanjiv Kapoor, Rahul Garg

Approximation Algorithms for Deadline-TSP

Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson

Computing Nash Equilibria for Scheduling on Restricted Parallel Links

Martin Gairing, Thomas Luecking, Marios Mavronicolas, Burkhard Monien

Know Thy Neighbor's Neighbor: The Power of Lookahead in Randomized P2P Networks

Gurmeet Manku, Moni Naor, Udi Wieder

Multi-processor Scheduling for Minimizing Flow Time with $\eps$ Resource Augmentation

Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar

Linear FPT Reductions and Computational Lower Bounds

Jianer Chen, Xiuzhen Huang, Iyad Kanj, Ge Xia

Lower Bounds for Dynamic Connectivity

Mihai Patrascu, Erik Demaine

Finding Paths and Cycles of Superpolylogarithmic Length

Harold Gabow

Rational Secret Sharing and Multiparty Computation

Joseph Halpern, Vanessa Teague

Using Nondeterminism to Amplify Hardness

Alexander Healy, Salil Vadhan, Emanuele Viola

Quantum and Classical Query Complexities ofLocal Search are Polynomially Related

Miklos Santha, Mario Szegedy

Using Mixture Models for Collaborative Filtering

Jon Kleinberg, Mark Sandler

A new family of Cayley expanders (?)

Eyal Rozenman, Aner Shalev, Avi Wigderson

New Hardness Results for Congestion Minimization and Machine Scheduling

Julia Chuzhoy, Joseph Naor

A Decentralized Algorithm for Spectral Analysis

David Kempe, Frank McSherry

Estimating the Weight of Metric Minimum Spanning Trees in Sublinear-Time

Artur Czumaj, Christian Sohler

Bypassing the Embedding: Approximation schemes and distance labelings for growth restricted metrics

Kunal Talwar

Batch Codes and Their Applications

Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai

The Two Possible Values of the Chromatic Number of a Random Graph

Dimitris Achlioptas, Assaf Naor

Nearly-Linear Time Algorithms for Graph Partitioning, Graph Sparsification, and Solving Linear Systems

Daniel Spielman, Shang-Hua Teng

New Notions of Security: Achieving Universal Composability without Trusted Setup

Manoj Prabhakaran, Amit Sahai

Expander flows and a sqrt{log n}-approximation to sparsest cut

Sanjeev Arora, Satish Rao, Umesh Vazirani

Visibly Pushdown Languages

Rajeev Alur, P. Madhusudan

Lower Bounds for Linear Degeneracy Testing

Nir Ailon, Bernard Chazelle

The Complexity of Pure Nash Equilibria

Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar

Sublinear algorithms for testing monotone and unimodal distributions

Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld

Unconditional Lower Bounds on the Time-Approximation Tradeoffs for the Distributed Minimum Spanning Tree Problem

Michael Elkin

Dictionary matching and indexing with errors and don't cares

Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein