8:55 am Pseudo-random functions and factoring
Moni Naor, Omer Reingold, and Alon Rosen
9:20 am Satisfiability of equations in free groups is in PSPACE
Claudio Gutierrez
9:45 am Setting 2 variables at a time yields a new lower bound for random 3-SAT
Dimitris Achlioptas
8:55 am A deterministic polynomial-time algorithm for approximating mixed
discriminant and mixed volume
Leonid Gurvits and Alex Samorodnitsky
9:20 am Randomized metarounding
Robert Carr and Santosh Vempala
9:45 am Isomorphism testing for embeddable graphs through definability
Martin Grohe
10:55 am On the efficiency of local decoding procedures for error-correcting
codes
Jonathan Katz and Luca Trevisan
11:20 am Statistical mechanics, three-dimensionality and NP-completeness
Sorin Istrail
10:55 am Improved algorithms for submodular function minimization and
submodular flow
Lisa Fleischer and Satoru Iwata
11:20 am On dual minimum cost flow algorithms
Jens Vygen
2:45pm Approximating the domatic number
Uriel Feige, Magnus M Halldorsson, and Guy Kortsarz
3:10 pm The value of strong inapproximability results for clique
Aravind Srinivasan
2:45 pm The small-world phenomenon: an algorithmic perspective
Jon Kleinberg
3:10 pm A random graph model for massive graphs
William Aiello, Fan Chung, and Linyuan Lu
4:20 pm A PCP characterization of NP with optimal amortized query complexity
Alex Samorodnitsky and Luca Trevisan
4:45 pm On transformations of interactive proofs that preserve the prover's
complexity
Salil Vadhan
4:20 pm Sharing the cost of multicast transmissions
Joan Feigenbaum, Christos Papadimitriou, and Scott Shenker
4:45 pm The risk profile problem for stock portfolio optimization
Ming-Yang Kao and Andreas Nolte and Stephen R Tate
8:55 am Complete characterization of security notions for probabilistic
private-key encryption
Jonathan Katz and Moti Yung
9:20 am On zero-knowledge proofs: "from membership to decision"
Giovanni Di Crescenzo, Kouichi Sakurai, and Moti Yung
9:45 am Finding smooth integers in short intervals using CRT decoding
Dan Boneh
8:55 am Hard-potato routing
Costas Busch, Maurice Herlihy, and Roger Wattenhofer
9:20 am Approximation algorithms for geometric shortest path problems
Lyudmil Aleksandrov, Anil Maheshwari, and Jorg-Rudiger Sack
9:45 am Improved approximations of crossings in graph drawings and VLSI layout
areas
Guy Even, Sudipto Guha, and Baruch Schieber
10:55 am More general completeness theorems for secure two-party computation
Joe Kilian
11:20 am On the complexity of verifiable secret sharing and multiparty
computation
Ronald Cramer, Ivan Damgard, and Stefan Dziembowski
10:55 am Near-optimal fully-dynamic graph connectivity
Mikkel Thorup
11:20 am A new NC-algorithm for finding a perfect matching in bipartite planar
and small genus graphs
Meena Mahajan and Kasturi R Varadarajan
1:45 pm A new proof of the weak pigeonhole principle
Alexis Maciel, Toniann Pitassi, and Alan R Woods
2:10 pm Higher lower bounds on monotone size
Danny Harnik and Ran Raz
2:35 pm Tighter lower bounds for nearest neighbor search and related problems
in the cell probe model
Omer Barkol and Yuval Rabani
1:45 pm Faster suffix tree construction with missing suffix links
Richard Cole and Ramesh Hariharan
2:10 pm Approximate nearest neighbors and sequence comparison with block
operations
S Muthukrishnan and Suleyman Cenk Sahinalp
2:35 pm Near optimal multiple alignment within a band in polynomial time
Ming Li, Bin Ma, and Lusheng Wang
3:45 pm More theory revision with queries
Judy Goldsmith and Robert H Sloan
4:10 pm Are bitvectors optimal?
H Buhrman and PB Miltersen and J Radhakrishnan and S Venkatesh
3:45 pm Shortest path queries in planar graphs
Danny Z Chen and Jinhui Xu
4:10 pm How tall is a tree?
Bruce Reed
8:55 am From partial consistency to global broadcast
Matthias Fitzi and Ueli Maurer
9:20 am Connectivity and inference problems for temporal networks
David Kempe, Jon Kleinberg, and Amit Kumar
9:45 am Strictly non-blocking WDM cross-connects for heterogeneous networks
April Rasala and Gordon Wilfong
9:20 am A matter of degree: Improved approximation algorithms
for degree-bounded minimum spanning trees
J Konemann and R Ravi
9:45 am Clustering for edge-cost minimization
Leonard J Schulman
10:55 am ffl-optimization schemes and L-bit precision: alternative perspectives
in combinatorial optimization
James B Orlin, Andreas S Schulz, and Sudipta Sengupta
11:20 am Matrix-vector product for confluent Cauchy-like matrices with
application to confluent rational interpolation
Vadim Olshevsky and Amin Shokrollahi
10:55 am A guessing game and randomized online algorithms
Steven S Seiden
11:20 am Computing the median with uncertainty
Tomas Feder, Rajeev Motwani, Rina Panigrahy, Chris Olston, and Jennifer Widom
1:45 pm Rapid sampling through quantum computing
Lov K Grover
2:10 pm Normal subgroup reconstruction and quantum computation using group
representations
Sean Hallgren, Alexander Russell, and Amnon Ta-Shma
2:35 pm Quantum lower bounds by quantum arguments
Andris Ambainis
3:00 pm On quantum and probabilistic communication: Las Vegas and one-way
protocols
Hartmut Klauck
1:45 pm Polynomial-time approximation scheme for data broadcast
Claire Kenyon, Nicolas Schabanel, and Neal Young
2:10 pm Approximating permanents of complex matrices
Martin Furer
2:35 pm Combining fairness with throughput: Online routing with multiple
objectives
Ashish Goel, Adam Meyerson, and Serge Plotkin
3:00 pm Improvements in throughput maximization for real-time scheduling
Piotr Berman and Bhaskar DasGupta
4:05 pm Computing with highly mixed states
Andris Ambainis, Leonard J Schulman, and Umesh V Vazirani
4:30 pm Quantum bit escrow
Dorit Aharonov, Amnon Ta-Shma, Umesh Vazirani and Andrew C Yao
4:55 pm A proof of security of quantum key distribution
Eli Biham, Michel Boyer, P Oscar Boykin, Tal Mor, and Vwani Roychowdhury
4:05 pm A unified approach to approximating resource allocation and scheduling
Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Se Naor,
and Baruch Schieber
4:30 pm Balanced allocations: the heavily loaded case
Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vocking
End of Program