- List of Accepted Papers
- Conference Program (in Word, pdf and plain text format)

Quadratic forms on graphs

Noga Alon, Konstantin Makarychev, Yuri Makarychev, Assaf Naor

Representing Hard Lattices with O(n log n) Bits

Miklos Ajtai

Locally Decodable Codes with 2 queries and Polynomial Identity Testing for depth 3 circuits

Zeev Dvir, Amir Shpilka

Balanced Boolean functions that can be evaluated so that every input bit is unlikely to be read

Itai Benjamini, Oded Schramm, David B. Wilson

Worst-case update times for fully-dynamic all-pairs shortest paths

Mikkel Thorup

Every Monotone Graph Property is Testable

Noga Alon, Asaf Shapira

On Dynamic Range Reporting in One Dimension

Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu

Every 2-CSP allows nontrivial approximation

Johan Hastad

Computing the first Betti number and the connected components of semi-algebraic sets

Saugata Basu, Richard Pollack, Marie-Francoise Roy

Polynomial Time Algorithm for Computing the Top Betti Numbers of Semi-algebraic Sets

Saugata Basu

Extractors with Weak Random Seeds

Ran Raz

On Algorithms for Discrete and Approximate Brouwer Fixed Points

Xi Chen, Xiaotie Deng

Spectral norm of random matrices

V. Vu

On random $\pm 1$ matrices: Singularity and Determinant

T. Tao, V. Vu.

Testing versus Estimation of Graph Properties

Eldar Fischer, Ilan Newman

Euclidean distortion and the Sparsest Cut

Sanjeev Arora, James R. Lee, Assaf Naor

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography

Oded Regev

Approximately counting integral flows and cell-bounded contingency tables

Mary Cryan, Martin Dyer, Dana Randall

Key Agreement from Weak Bit Agreement

Thomas Holenstein

Undirected ST-Connectivity in Log-Space

Omer Reingold

How to Spread Adversarial Nodes? Rotate!

Christian Scheideler

Simple PCPs with Poly-log Rate and Query Complexity

Eli Ben-Sasson, Madhu Sudan

A New Strategy for Querying Priced Information

Ferdinando Cicalese, Eduardo Sany Laber

On the average case performance of some facility location heuristics

Abraham D. Flaxman, Alan M. Frieze, Juan C. Vera

Efficient testing of groups

Katalin Friedl, Gabor Ivanyos, Miklos Santha

Improved approximation algorithms for minimum-weight vertex separators

Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee

Bounded-depth circuits: separating wires from gates

Michal Koucky, Pavel Pudlak, Denis Therien

Approximation Algorithms for Network Design with Metric Costs

Joseph Cheriyan, Adrian Vetta

On Uniform Amplification of Hardness in NP

Luca Trevisan

Computing Correlated Equilibria in Multiplayer Games

Christos H. Papadimitriou

A O(log n log log n) Space Algorithm for Undirected Connectivity

Vladimir Trifonov

Lower-Stretch Spanning Trees

Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng

Cooperative Asynchronous Update of Shared Memory

Bogdan Chlebus, Dariusz Kowalski

Collusion-free protocols

Matt Lepinksi, Silvio Micali, abhi shelat

Optimal Approximations of the Frequency Moments

Piotr Indyk, David Woodruff

Multicommodity flow, well-linked terminals, and routing problems

Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd

Limits to List Decoding Reed-Solomon Codes

Venkatesan Guruswami, Atri Rudra

Low-Distortion EMbeddings of General Metrics Into the Line

Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos

Lower bounds for $k$-DNF Resolution on random 3-CNFs

Michael Alekhnovich

Low Distortion Embeddings for Edit Distance

Rafail Ostrovsky, Yuval Rabani

On the mixing time for the Thorp shuffle

Ben Morris

Edge partition of planar graphs into two outerplanar graphs

Daniel Gonçalves

Saving an $e$: A 2-approximation for the $k$-MST problem in graphs

Naveen Garg

The Price of Routing Unsplittable Flow

B. Awerbuch, Y. Azar, A. Epstein

Convex Programming for Scheduling Unrelated Parallel Machines

Y. Azar, A. Epstein

Learning Nonsingular Phylogenies and Hidden Markov Models

Elchanan Mossel, Sebastien Roch

On Strip Packing with Rotations

Klaus Jansen, Rob van Stee

Concurrent General Composition of Secure Protocols in the Timing Model

Yael Kalai, Yehuda Lindell, Manoj Prabhakaran

Fast Quantum Algorithms for Computing the Unit Group and Class Group of a Number Field

Sean Hallgren

Tensor Decomposition and Approximation Schemes for CSP

W.F.dela Vega, R. Kannan, M. Karpinski, S. Vempala

Approximation Techniques for Utilitarian Mechanism Design

Patrick Briest, Piotr Krysta, Berthold Voecking

Balanced Metric Labeling

Joseph (Seffi) Naor, Roy Schwartz

Learning with Attribute Costs

Haim Kaplan, Eyal Kushilevitz, Yishay Mansour

Market Equilibrium via the Excess Demand Function

Bruno Codenotti, Benton McCune, Kasturi Varadarajan

Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders

Shahar Dobzinski, Noam Nisan, Michael Schapira

Testing Monotone High-Dimensional Distributions

Ronitt Rubinfeld, Rocco A. Servedio

The Complexity of Agreement

Scott Aaronson

Aggregating Inconsistent Information: Ranking and Clustering

Nir Ailon, Moses Charikar, Alantha Newman

Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors

Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson

O(\sqrt{log n}) approximation algorithms for Min UnCut, Min 2CNF Deletion, and directed cut problems

Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev

Fast Quantum Byzantine Agreement

Michael Ben-Or, Avinatan Hassidim

Pseudorandom generators for low degree polynomials

Andrej Bogdanov

From a Static Impossibility to an Adaptive Lower Bound: The Complexity of Early Deciding Set Agreement

Eli Gafni, Rachid Guerraoui, Bastian Pochon

On Non-uniform Multicommodity Buy-at-Bulk Network Design

Moses Charikar, Adriana Karagiozova

Promise Hierarchies

Lance Fortnow, Rahul Santhanam, Luca Trevisan

Hardness of the Undirected Edge-Disjoint Paths Problem

Matthew Andrews, Lisa Zhang

Hardness of the Undirected Congestion Minimization Problem

Matthew Andrews, Lisa Zhang

Universal Approximations for TSP, Steiner Tree and Set Cover

Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram

On Obfuscating Point Functions

Hoeteck Wee

Coresets in dynamic geometric data streams

Gereon Frahling, Christian Sohler

Tensor norms and the classical communication complexity of nonlocal quantum measurement

Yaoyun Shi

Oblivious Routing in Directed Graphs with Random Demands

Mohammad T. Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Raecke

The price of anarchy of finite congestion games

George Christodoulou, Elias Koutsoupias

Covert Two-Party Computation

Luis von Ahn, Nicholas J. Hopper, John Langford

New and Improved Constructions of Non-Malleable Cryptographic Protocols

Rafael Pass, Alon Rosen

Towards Asymptotic Optimality in Probabilistic Packet Marking

Micah Adler, Jeff Edmonds, Jiri Matousek

Polynomial Time Quantum Algorithm for the Computation of the Unit Group of a Number Field

Arthur Schmidt, Ulrich Vollmer

Derandomization of Auctions

Gagan Aggarwal, Amos Fiat, Andrew Goldberg, Jason Hartline, Nicole Immorlica, Madhu Sudan

An Optimal Multi-Writer Snapshot Algorithm

Prasad Jayanti

Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy

Mikhail Alekhnovich, Sanjeev Arora, Iannis Tourlakis

The Round Complexity of Two-Party Random Selection

Saurabh Sanghvi, Salil Vadhan

Tree-Walking Automata Do Not Recognize All Regular Languages

Mikolaj Bojanczyk, Thomas Colcombet

On the Bias of Traceroute Sampling, or: Why almost every network looks like it has a power law

Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore

Correcting Errors Without Leaking Partial Information

Yevgeniy Dodis, Adam Smith