SESSION CHAIRS Sun AM A Lenore Cowen Sun AM B Sorin Istrail Sun PM A Ronald Fagin/Jon Kleinberg Sun PM B Amos Fiat Mon AM A Jon Kleinberg Mon AM B Shang-Hua Teng Mon PM A Shang-Hua Teng/Lenore Cowen Mon PM B Phil Gibbons Tue AM A Joan Feigenbaum Tue AM B Burkhard Monien Tue PM A Ronald Fagin Tue PM B Sorin Istrail SCHEDULE: SATURDAY 8-11pm STOC Opening Reception SUNDAY 9:00 Slot 1 (S1) A: A Constant-Factor Approximation Algorithm for the k-Median Problem Moses Charikar and Sudipto Guha and \'{E}va Tardos and David Shmoys B: PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability I. Dinur and E. Fischer and G. Kindler and R. Raz and S. Safra 9:25 S2 A: A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow Kevin D. Wayne B: Fast Approximate PCPs Funda Erg\"{u}n and Ravi Kumar and Ronitt Rubinfeld 9:50 S3 A: Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. Venkatesan Guruswami and Sanjeev Khanna and Rajmohan Rajaraman and Bruce Shepherd and Mihalis Yannakakis. B: Approximate Testing with Relative Error Marcos Kiwi and Fr\'{e}d\'{e}ric Magniez and Miklos Santha 10:10 Break 10:35 S4 A: All Pairs Lightest Shortest Paths Uri Zwick B: Improved Upper Bounds on Information-Theoretic Private Information Retrieval Yuval Ishai and Eyal Kushilevitz 11:00 S5 A: Unique Maximum Matching Algorithms Harold N. Gabow and Haim Kaplan and Robert E. Tarjan B: One-way Functions are Essential for Single-Server Private Information Retrieval Amos Beimel and Yuval Ishai and Eyal Kushilevitz and Tal Malkin 11:30 FCRC Plenary talk: Shafi Goldwasser (MIT and Weizmann Institute). "Testing Global Properties using Random, Local Data: the Peleontologist approach to computer science" 12:30 lunch 2:00 S6 A: On targeting Markov segments Moses Charikar and Ravi Kumar and Prabhakar Raghavan and Sridhar Rajagopalan and Andrew Tomkins B: Construction of Extractors Using Pseudo-Random Generators Luca Trevisan 2:25 S7 A: Exploiting Regularities in Web Traffic Patterns for Cache Replacement Edith Cohen and Haim Kaplan B: Extracting all the Randomness and Reducing the Error in Trevisan's Extractors Ran Raz and Omer Reingold and Salil Vadhan 2:50 S8 A: Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns Gen-Huey Chen and Ming-Yang Kao and Yuh-Dauh Lyuu and Hsing-Kuo Wong B: On Recycling the Randomness of States in Space Bounded Computation Ran Raz, Omer Reingold 3:15 S9 A: Algorithmic Mechanism Design Noam Nisan and Amir Ronen B: Security-Preserving Hardness-Amplification for Any Regular One-Way Function Giovanni Di Crescenzo and Russell Impagliazzo 3:35 Break 4:00 S10 A: Scheduling in the Dark Jeff Edmonds B: Chinese Remaindering with Errors Oded Goldreich and Dana Ron and Madhu Sudan 4:25 S11 A: Scheduling Data Transfers in a Network and the Set Scheduling Problem Ashish Goel and Monika R. Henzinger and Serge Plotkin and Eva Tardos B: A Displacement Approach to Efficient Decoding of Algebraic-Geometric Codes. Vadim Olshevsky and M. Amin Shokrollahi 4:50 S12 A: Minimizing the Flow Time without Migration B. Awerbuch and Y. Azar and S. Leonardi and O. Regev B: Oblivious Transfer and Polynomial Evaluation Moni Naor and Benny Pinkas 5:15 S13 A: Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queuing Networks David Gamarnik B: Secure Computation with Honest-Looking Parties: What if Nobody is Truly Honest? Ran Canetti and Rafail Ostrovsky 5:40 S14 A: From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols Christian Scheideler and Berthold Voecking B: Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings Yefim Dinitz and Shlomo Moran and Sergio Rajsbaum 6:00 Mixer MONDAY 9:00 S15 A: Lifting Markov Chains to Speed up Mixing Fang Chen and L\'{a}szl\'{o} Lov\'{a}sz and Igor Pak B: Optimal Bounds for the Predecessor Problem Paul Beame and Faith Fich 9:25 S16 A: Faster Mixing Via Average Conductance L\'{a}szl\'{o} Lov\'{a}sz and Ravi Kannan B: A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube Amit Chakrabarti and Bernard Chazelle and Benjamin Gum and Alexey Lvov 9:50 S17 A: Majorizing estimators and the approximation of #P-complete problems Leonard J. Schulman and Vijay V. Vazirani B: Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems Allan Borodin and Rafail Ostrovsky and Yuval Rabani 10:10 Break 10:35 S18 A: Molecular Scale Heat Engines and Scalable Quantum Computation Leonard J. Schulman and Umesh Vazirani B: Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model Alexander Russell and Michael Saks and David Zuckerman 11:00 S19 A: Quantum Fourier Sampling Simplified Lisa Hales and Sean Hallgren B: A Theorem on Sensitivity and Applications in Private Computation Anna G\'{a}l and Adi Ros\'{e}n 11:30 FCRC Lecture 12:30 lunch 2:00 S20 A: Exponential Separation of Quantum and Classical Communication Complexity Ran Raz B: Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme Klaus Jansen and R. Solis-Oba and Maxim I. Sviridenko 2:25 S21 A: Undecidability on Quantum Finite Automata Masami Amano and Kazuo Iwama B: A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines M. Skutella and G.J. Woeginger 2:50 S22 A: Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata Andris Ambainis and Ashwin Nayak and Amnon Ta-Shma and Umesh Vazirani B: Improved Approximation Schemes for Scheduling Unrelated Parallel Machines Klaus Jansen and Lorant Porkolab 3:15 S23 A: The Quantum Query Complexity of Approximating the Median and Related Statistics Ashwin Nayak and Felix Wu B: A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling Jianer Chen and Antonio Miranda 3:35 Break 4:00 S24 A: Sublinear Time Algorithms for Metric Space Problems Piotr Indyk B: Finding Similar Regions In Many Strings Ming Li and Bin Ma and Lusheng Wang 4:25 S25 A: Subquadratic Approximation Algorithms For Clustering Problems in High Dimensional Spaces Allan Borodin and Rafail Ostrovsky and Yuval Rabani B: Multi-Method Dispatching: A Geometric Approach with Applications to String Matching Problems. P. Ferragina and S. Muthukrishnan and M. de Berg 4:50 S26 A: Covering Rectilinear Polygons with Axis-Parallel Rectangles V.S.Anil Kumar and H. Ramesh B: A Fully Dynamic Algorithm for Maintaining the Transitive Closure Valerie King and Garry Sagert 5:15 S27 A: Compact Grid Layouts of Multi-Level Networks S. Muthukrishnan, M. S. Paterson, S. C. Sahinalp, T. Suel B: Worst-case and Amortised Optimality in Union-Find Stephen Alstrup and Amir M. Ben-Amram and Theis Rauhe 5:40 S28 A: Complexity of Graph Partition Problems Tomas Feder and Pavol Hell and Sulamita Klein and Rajeev Motwani B: The Complexity of the Matrix Eigenproblem Victor Y. Pan and Z. Chen 6:00 Mixer 9:00 Business Meeting TUESDAY 8:35 S29 A: Short Proofs are Narrow - Resolution made Simple Eli Ben-Sasson and Avi Wigderson B: Packet Routing with Arbitrary End-to-End Delay Requirements Matthew Andrews and Lisa Zhang 9:00 S30 A: On the Complexity of Diophantine Geometry in Low Dimensions J. Maurice Rojas B: Static and Dynamic Evaluation of QoS Properties Gopal Pandurangan and Eli Upfal 9:25 S31 A: Pseudorandom Generators without the XOR Lemma Madhu Sudan and Luca Trevisan and Salil Vadhan B: Efficient Recovery from Power Outage Sudipto Guha and Anna Moss and Joseph (Seffi) Naor and Baruch Schieber 9:50 S32 A: Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes Sam Buss and Dima Grigoriev and Russell Impagliazzo and Toniann Pitassi B: Nonmonotonic Phenomena in Packet Routing Uriel Feige 10:10 Break 10:35 S33 A: Graph Ramsey Theory and the Polynomial Hierarchy Marcus Schaefer B: Connection Caching Edith Cohen and Haim Kaplan and Uri Zwick 11:00 S34 A: The communication complexity of pointer chasing, Applications of entropy and sampling Stephen J. Ponzio and Jaikumar Radhakrishnan and S. Venkatesh B: Approximating the Throughput of Multiple Machines Under Real-Time Scheduling Amotz Bar-Noy and Sudipto Guha and Joseph (Seffi) Naor and Baruch Schieber 11:30 FCRC Lecture 12:30 lunch 2:00 S35 A: Determinism versus Non-Determinism for Linear Time RAMs with Memory Miklos Ajtai B: Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut David R. Karger and Philip Klein and Cliff Stein and Mikkel Thorup and Neal E. Young 2:25 S36 A: Robust Logics Leslie G Valiant B: Outward rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems Uri Zwick 2:50 S37 A: Hypergraph Isomorphism and Structural Equivalence of Boolean Functions Eugene M. Luks B: Approximation Schemes for Minimum Latency Problems. Sanjeev Arora and George Karakostas. 3:15 S38 A: Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses Adam R. Klivans and Dieter van Melkebeek B: Embedding Tree Metrics into Low Dimensional Euclidean Spaces Anupam Gupta 3:35 Break 4:00 S39 A: Computational Sample Complexity and Attribute-Efficient Learning Rocco A. Servedio B: Small Universal Graphs Michael R. Capalbo and S. Rao Kosaraju 4:25 S40 A: On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice Johannes Bl\"{o}mer and Jean-Pierre Seifert B: Designing Networks with Bounded Pairwise Distance Yevgeniy Dodis and Sanjeev Khanna 4:50 S41 A: Satisfiability of word equations with constants is in NEXPTIME Wojciech Plandowski B: Random Sampling of Large Planar Maps and Convex Polyhedra Gilles Schaeffer 5:15 S42 A: Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time Jin-Yi Cai and Ajay Nerurkar and D.Sivakumar B: Efficient Computation of Geodesic Shortest Paths Sanjiv Kapoor 5:40 S43 A: Interpolation of Symmetric Functions and a New Type of Combinatorial Design Piotr Indyk B: Backing up in Singly Linked Lists Amir M. Ben-Amram and Holger Petersen 6:00 Mixer