STOC 2005 Conference Program


List of Accepted Papers

(In the order they were submitted)

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

Conference Program

Click here to download the program.