Preliminary
Program of the Thirty-Fourth Annual ACM Symposium on Theory of Computing
May
19-21, 2002, Montréal, Québec, Canada
Important
Note: There will be a day long Joint Session with Computational Complexity
Theory 2002 on Tuesday, May 21, 2002.
Saturday,
May 18, 2002
7:00 pm
-9:00 pm Welcome Reception
Sunday,
May 19, 2002
Session
1A Chair: Rao Kosaraju
8:30 am
Recognizing
String Graphs in NP
Marcus
Schaefer, Eric Sedgwick and Daniel Stefankovic
8:55 am
Finding the
k Shortest Simple Paths
John
Hershberger, Subhash Suri and Amit Bhosle
9:20 am
Dynamic
Subgraph Connectivity with Geometric Applications
Timothy
M. Chan
9:45 am
New
Results on Monotone Dualization and Generating Hypergraph Transversals
Thomas Eiter,
Georg Gottlob and Kazuhisa Makino
Session
1B Chair: Michael Mitzenmacher
8:30 am
The Importance of Being Biased
Irit
Dinur and Shmuel Safra
8:55 am
On the
Advantage over a Random Assignment
Johan
Hastad and S. Venkatesh
9:20 am
The
Complexity of Choosing an H-Colouring (Nearly) Uniformly at Random
Leslie
Ann Goldberg, Steven Kelk and Mike Paterson
9:45 am
Random
Sampling in Residual Graphs
David R.
Karger and Matthew S. Levine
Coffee
Break 10:10 am - 10:30 am
Session
2A Chair: John Reif
10:30 am
On the
Complexity of Equilibria
Xiaotie
Deng, Christos Papadimitriou and Shmuel Safra
10:55 am
Competitive
Generalized Auctions
Amos
Fiat, Andrew V. Goldberg, Jason D. Hartline and Anna R. Karlin
11:20 am
Competitive
Recommendation Systems
Petros
Drineas, Iordanis Kerenidis and Prabhakar Raghavan
Session
2B Chair: Paul Spirakis
10:30 am
The
Glauber Dynamics on the Colourings of a Graph with High Girth and Maximum
Degree
Michael
Molloy
10:55 am
Clairvoyant
Scheduling of Random Walks
Peter
Gacs
11:20 am
Solving
Convex Programs by Random Walks
Dimitris
Bertsimas and Santosh Vempala
Lunch
11:50 am
1:00 pm Knuth
Prize Plenary Talk:
Session
3A Chair: Michael Mitzenmacher
2:10 pm
Improved
Online Algorithms for Transitive Closure and All-Pairs
S.
Baswana, R. Hariharan and S. Sen
2:35pm
Lower
Bounds and Competitive Algorithms for On-Line Scheduling of Unit-Size Tasks to
Related Machines
Spyros
Kontogiannis
3:00 pm
On
Randomized Online Scheduling
Susanne
Albers
Session
3B Chair: Alan Borodin
2:10 pm
On the
Complexity of Matrix Product
Ran Raz
2:35pm
Near-Optimal
Sparse Fourier Representations via Sampling
Anna C.
Gilbert, Sudipto Guha, Piotr Indyk, S. Muthukrishnan and Martin J. Strauss
3:00 pm
Fitting
Algebraic Curves to Noisy Data
Sanjeev
Arora Subhash Khot
Coffee
Break 3:25 - 4:45 pm
Session
4A Chair: Gary Miller
4:45 pm
A New
average Case Analysis for Completion Time Scheduling
Mark Scharbrodt,
Thomas Schickinger and Angelika Steger
5:10 pm
A
Unified Analysis of Hot Video Schedulers
Wun-Tat
Chan, Tak-Wah Lam, Hing-Fung Ting and Wai-Ha Wong
5:35 pm
Optimal
Rate-based Scheduling on Multiprocessors
Anand
Srinivasan and James H. Anderson
Session
4B Chair: Paul Spirakis
4:45 pm
Almost
all graphs with average degree 4 are 3-colorable
Dimitris
Achlioptas and Cristopher Moore
5:10 pm
Models
and Thresholds for Random Constraint Satisfaction Problems
Michael
Molloy
5:35 pm
Remier's
Inequality and Tardos' Conjecture
Clifford
Smyth
8:30 pm Business
Meeting
Monday,
May 20, 2002
Session
5A Chair: Alan Borodin
8:30 am
Clifford
algebras and Approximating the Permanent
Steve
Chien, Lars Rasmussen and Alistair Sinclair
8:55 am
Random Sampling
and Approximation of MAX-CSP Problems
Noga
Alon, W. Fernandez de la Vega, Ravi Kannan and Marek Karpinski
9:20 am
A
Polynomial Time Algorithm to Approximately Count Contingency
Mary
Cryan and Martin Dyer
9:45 am
Approximate
Clustering via Core-Sets
Mihai
Badoiu, Sariel Har-Peled and Piotr Indyk
Session
5B Chair: Michael Mitzenmacher
8:30 am
On
Paging with Locality of Reference
Susanne
Albers, Lene M. Favrholdt and Oliver Giel
8:55 am
Cache-Oblivious
Priority Queue and Graph Algorithm Applications
Lars
Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley and J. Ian
Munro
9:20 am
Average
Case Analysis for Batched Disk Scheduling and Increasing Sequences
E.
Bachmat
9:45 am
Selfish
Traffic Allocation for Server Farms
Artur Czumaj,
Piotr Krysta and Berthold Voecking
Coffee
Break 10:10 am -10:30 am
Session
6A Chair: Satish Rao
10:30 am
Approximation
Schemes for Preemptive Weighted Flow Time
Chandra
Chekuri and Sanjeev Khanna
10:55 am
Approximation
Algorithms for Minimum-Cost k-Vertex Connected Subgraphs
Joseph
Cheriyan, Santosh Vempala and Adrian Vetta
11:20 am
Equitable
Truth-Revealing Cost Allocations via Primal-Dual-Type
Kamal
Jain and Vijay Vazirani
Session
6B Chair: Sam Buss
10:30 am
2-Round Zero
Knowledge and Proof Auditors
Cynthia
Dwork and Larry Stockmeyer
10:55 am
Concurrent
Zero-Knowledge With Timing Revisited
Oded
Goldreich
11:20 am
Tight
Security Proofs for the Bounded-Storage Model
Stefan
Dziembowski and Ueli Maurer
Lunch
11:50 am
Session
7A Chair: Mikkel Thorup
1:00 pm
Hardness
Results for Approximate Hypergraph Coloring
Subhash
Khot
1:25 pm
Space Lower Bounds for
Distance Approximation in the Data Stream Model
Michael
Saks and Xiaodong Sun
1:50 pm
Approximate
Counting of Inversions in a Data Stream
Miklos
Ajtai, T.S. Jayram, Ravi Kumar and D. Sivakumar
2:15 pm
Similarity
Estimation Techniques from Rounding Algorithms
Moses
Charikar
2:40 pm
Fast
Small-space Algorithms for Approximate Histogram Maintenance
Anna Gilbert,
Sudipto Guha, Piotr Indyk, Yannis Kotidis, S. Muthukrishnan and Martin J.
Strauss
Session
7B Chair: Gary Miller
1:00 pm
Load
Balancing in Dynamic Adversarial Systems
Elliot
Anshelevich, David Kempe and Jon Kleinberg
1:25 pm
Tradeoffs
in Probabilistic Packet Marking for IP Traceback
Micah
Adler
1:50 pm
Crawling
on Web Graphs
Colin
Cooper and Alan Frieze
2:15 pm
The
Price of Anarchy is Independent of the Network Topology
Tim
Roughgarden
2:40 pm
Combinatorial
Logarithmic Approximation Algorithm for the Directed Telephone Broadcast
Problem
Michael
Elkin and Guy Kortsarz
Coffee
Break 3:05 - 3:30 pm
Session
8A Chair: Sam Buss
3:3 0 pm
An
Exponential Separation between Regular and General Resolution
Michael Alekhnovich,
Jan Johannsen, Toniann Pitassi and Alasdair Urquhart
3:55 pm
Size
Space Tradeoffs for Resolution
Eli
Ben-Sasson
4:10 pm
Exact
learning of DNF formulas using DNF hypotheses
Lisa Hellerstein and Vijay
Raghavan
4:35 pm
Monotonicity
Testing over General Poset Domains
Eldar
Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld and
Alex Samorodnitsky
5:00 pm
Combinatorial
Optimization Problems in Self-Assembly
Leonard
Adleman, Qi Cheng, Ashish Goel, Ming-Deh Huang, David Kempe, Pablo M. de
Moisset and Paul W. K. Rothemund
Session
8B Chair: Pankaj Agarwal
3:3 0 pm
Strict
Polynomial-time in Simulation and Extraction
Boaz
Barak and Yehuda Lindell
3:55 pm
Universally
Composable Two-party Computation
Ran Canetti and Yehuda Lindell, , Rafail Ostrovsky and Amit Sahai
4:10 pm
The
Invasiveness of Off-line Memory Checking
Miklos
Ajtai
4:35 pm
On the
Composition of Authenticated Byzantine Agreement
Ydhuda
Lindell, Anna Lysyanskaya and Tal Rabin
]5:00 pm
Wait-Free
Consensus with Infinite Arrivals
James
Aspnes, Gauri Shah and Jatin Shah
7:30
pm Banquet Plenary Talk:
Tuesday,
May 21, 2002
Session
9A (Joint Session with Complexity 2002)
Chair: Sam Buss
8:30 am
Relations
between Average Case Complexity and Approximation Complexity
Uriel
Feige
8:55 am
Vertex
Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2-epsilon
Jonas Holmerin
9:20 am
Resolution
Lower Bounds for the Weak Pigeon Hole Principle
Ran Raz
9:45 am
Hard Examples for Bounded
Depth Frege
Eli
Ben-Sasson
Session
9B Chair: Mikkel Thorup
8:30 am
Meldable
Heaps and Boolean Union-Find
Haim
Kaplan, Nira Shafrir and Robert E. Tarjan
8:55 am
Optimal
Finger Search Trees in the Pointer Machine
Gerth S.
Brodal, George Lagogiannis, Christos Makris, Athanasios Tsakalidis and Kostas
Tsichlas
9:20 am
Verifying
Candidate Matches in Sparse and Wildcard Matching
Richard Cole and Ramesh
Hariharan
9:45 am
Deterministic
Sorting in O(nloglogn) Time and Linear Space
Yijie
Han
Coffee
Break 10:10 am - 10:30 am
Session
10A (Joint Session with Complexity 2002)
Chair: Anne
Condon
10:30 am
Improved
Cryptographic Hash Functions with Worst-case/Average-case Connection
Daniele Micciancio
10:55 am
Algorithmic
Derandomization via Complexity Theory
D.
Sivakumar
11:20 am
Pseudo-Random
Generators for all Hardnesses
Christopher
Umans
Session
10B Chair: John Reif
10:30 am
Quantum
Lower Bound for the Collision Problem
Scott
Aaronson
10:55 am
Secure
Multi-party Quantum Computing
Claude
Crepeau, Daniel Gottesman and Adam Smith
11:20 am
Polynomial-Time
Quantum Algorithms for Pell's Equation and the Principal Ideal Problem
Sean
Hallgren
Lunch
11:50 am
Session
11A (Joint Session with Complexity 2002)
Chair: Michael
Saks
1:00 pm
Randomness
Conductors and Constant-Degree Expansion Beyond the Degree 2 Barrier
Michael Capalbo, Omer
Reingold, Salil Vadhan and Avi Wigderson
1:25 pm
Expanders
from Symmetric Codes
Roy Meshulam and Avi
Wigderson
1:50 pm
The
Complexity of Approximating the Entropy
Tugkan
Batu, Sanjoy Dasgupta, Ravi Kumar and Ronitt Rubinfeld
2:15 pm
Time-Space
Tradeoffs Multiparty Communication Complexity and Nearest Neighbor Problems
Paul Beame and Erik Vee
2:40 pm
On
Communication over an Entanglement-Assisted Quantum Channel
Ashwin
Nayak and Julia Salzman
Session
11B Chair: Pankaj Agarwal
1:00 pm
Girth
and Euclidean Distortion
Nathan
Linial, Avner Magen and Assaf Naor
1:25 pm
Computing
the Betti Numbers of Arrangements
Saugata
Basu
1:50 pm
Space-Efficient
Approximate Voronoi Diagrams
Sunil
Arya, Theocharis Malamatos and David M. Mount
2:15 pm
A New
Greedy Approach for Facility Location Problems
Kamal
Jain, Mohammad Mahdian and Amin Saberi
2:40 pm
Finding
Nearest Neighbors in Growth-restricted Metrics
David
Karger and Matthias Ruhl
Coffee
Break 3:00 - 3:20 pm
Session
12A (Joint Session with Complexity 2002)
Chair: Sam Buss
3:20 pm
Hardness
Amplification Within NP
Ryan
O'Donnell
3:45 pm
3-MANIFOLD
KNOT GENUS is NP-complete
Ian Agol
Joel Hass William P. Thurston
4:10 pm
On the
Power of Unique 2-Prover 1-Round Games
Subhash
Khot
4:35 pm
Learnability
Beyond AC0
Jeffrey
C. Jackson, Adam R. Klivans and Rocco A. Servedio
Session
12B Chair: Rao Kosaraju
3:20 pm
Huffman
Coding with Unequal Letter Costs
Mordecai
J. Golin Claire Kenyon Neal E. Young
3:45 pm
Approximating
The Smallest Grammar: Kolmogorov Complexity in Natural Models
Moses
Charikar, Eric Lehman, Ding Liu, Manoj Prabhakaran, April Rasala, Amit Sahai
and Abhi Shelat
4:10 pm
Limits
to List Decodability of Linear Codes
Venkatesan
Guruswami
4:35 pm
Near-optimal
Linear-Time Codes for Unique Decoding and New List-Decodable Codes Over Smaller
Alphabets
Venkatesan
Guruswami and Piotr Indyk
End
of Program