STOC 2005 Conference Program
Contents:
(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
Click here to download the program.