40. FOCS 1999: New York, NY, USA

Session 1

• Kamal Jain, Vijay V. Vazirani:
  Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems. 2-13
  
• Jon M. Kleinberg, Éva Tardos:
  Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields. 14-23
  
• Lisa Fleischer:
  Approximating Fractional Multicommodity Flow Independent of the Number of Commodities. 24-31
  
• Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, Maxim Sviridenko:
  Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. 32-44
  

Session 2

• Markus Bläser:
  A 5/2 n²-Lower Bound for the Rank of n×n Matrix Multiplication over Arbitrary Fields. 45-50
  
• Eric Vigoda:
  Improved Bounds for Sampling Colorings. 51-59
  
• Miklós Ajtai:
  A Non-linear Time Lower Bound for Boolean Branching Programs. 60-70
  
• Peter Bro Miltersen, N. V. Vinodchandran:
  Derandomizing Arthur-Merlin Games Using Hitting Sets. 71-80
  
• Valerie King:
  Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs. 81-91
  

Session 3

• Timothy M. Chan:
  Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time. 92-99
  
• Sariel Har-Peled:
  Taking a Walk in a Planar Arrangement. 100-111
  

Session 4

• John Watrous:
  PSPACE Has Constant-Round Quantum Interactive Proof Systems. 112-119
  
• Silvio Micali, Michael O. Rabin, Salil P. Vadhan:
  Verifiable Random Functions. 120-130
  
• Berthold Vöcking:
  How Asymmetry Helps Load Balancing. 131-141
  
• Uriel Feige:
  Noncryptographic Selection Protocols. 142-153
  

Session 5A

• Piotr Indyk:
  A Sublinear Time Approximation Scheme for Clustering in Metric Spaces. 154-159
  
• Arnon Amir, Alon Efrat, Piotr Indyk, Hanan Samet:
  Efficient Regular Data Structures and Algorithms for Location and Proximity Problems. 160-170
  
• Martin Farach-Colton, Piotr Indyk:
  Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings. 171-180
  

Session 5B

• Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson:
  Near-Optimal Conversion of Hardness into Pseudo-Randomness. 181-190
  
• Ran Raz, Omer Reingold, Salil P. Vadhan:
  Error Reduction for Extractors. 191-201
  
• Manindra Agrawal, Somenath Biswas:
  Primality and Identity Testing via Chinese Remaindering. 202-209
  

Session 6A

• Martin E. Dyer, Alan M. Frieze, Mark Jerrum:
  On Counting Independent Sets in Sparse Graphs. 210-217
  
• Christian Borgs, Jennifer T. Chayes, Alan M. Frieze, Jeong Han Kim, Prasad Tetali, Eric Vigoda, Van H. Vu:
  Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics. 218-229
  
• Ben Morris, Alistair Sinclair:
  Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions. 230-240
  
• V. S. Anil Kumar, H. Ramesh:
  Markovian Coupling vs. Conductance for the Jerrum-Sinclair Chain. 241-252
  

Session 6B

• David Peleg, Vitaly Rubinovich:
  A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction. 253-261
  
• Yehuda Afek, Gideon Stupp, Dan Touitou:
  ong-lived Adaptive Collect with Applications. 262-272
  
• Rakesh D. Barve, Jeffrey Scott Vitter:
  A Theoretical Framework for Memory-Adaptive Algorithms. 273-284
  
• Matteo Frigo, Charles E. Leiserson, Harald Prokop, Sridhar Ramachandran:
  Cache-Oblivious Algorithms. 285-298
  

Session 7A

• Jon Feldman, Matthias Ruhl:
  The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals. 299-308
  
• David Eppstein:
  Setting Parameters by Example. 309-318
  
• Zhi-Zhong Chen, Xin He, Chun-Hsi Huang:
  Finding Double Euler Trails of Planar Graphs in Linear Time. 319-329
  
• Karsten Weihe:
  Edge-Disjoint Routing in Plane Switch Graphs in Linear Time. 330-340
  

Session 7B

• John Watrous:
  On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes. 341-351
  
• Andris Ambainis:
  A Better Lower Bound for Quantum Algorithms Searching an Ordered List. 352-357
  
• Harry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka:
  Bounds for Small-Error and Zero-Error Quantum Algorithms. 358-368
  
• Ashwin Nayak:
  Optimal Lower Bounds for Quantum Automata and Random Access Codes. 369-377
  

Session 8A

• Moses Charikar, Sudipto Guha:
  Improved Combinatorial Algorithms for the Facility Location and k-Median Problems. 378-388
  
• Naoki Katoh, Takeshi Tokuyama:
  Lovász's Lemma for the Three-Dimensional K-Level of Concave Surfaces and its Applications. 389-398
  
• Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair:
  Cuts, Trees and l₁-Embeddings of Graphs. 399-409
  

Session 8B

• Uwe Schöning:
  A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems. 410-414
  
• Eli Ben-Sasson, Russell Impagliazzo:
  Random CNF's are Hard for the Polynomial Calculus. 415-421
  
• Maria Luisa Bonet, Nicola Galesi:
  A Study of Proof Search Algorithms for Resolution and Polynomial Calculus. 422-432
  

Session 9A

• S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes Gehrke:
  Online Scheduling to Minimize Average Stretch. 433-442
  
• Elias Koutsoupias:
  Weak Adversaries for the k-Server Problem. 444-449
  
• Avrim Blum, Carl Burch, Adam Kalai:
  Finely-Competitive Paging. 450-458
  

Session 9B

• Richard J. Lipton, Anastasios Viglas:
  On the Complexity of SAT. 459-464
  
• Christopher Umans:
  Hardness of Approximating Sigma₂^p Minimization Problems. 465-474
  
• Ilya Dumer, Daniele Micciancio, Madhu Sudan:
  Hardness of Approximating the Minimum Distance of a Linear Code. 475-485
  

Session 10A

• P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani P. Roychowdhury, Farrokh Vatan:
  On Universal and Fault-Tolerant Quantum Computing: A Novel Basis and a New Constructive Proof of Universality for Shor's Basis. 486-494
  
• Wojciech Plandowski:
  Satisfiability of Word Equations with Constants is in PSPACE. 495-500
  
• Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan:
  An Approximate L¹-Difference Algorithm for Massive Data Streams. 501-511
  
• Deborah Goldman, Sorin Istrail, Christos H. Papadimitriou:
  Algorithmic Aspects of Protein Structure Similarity. 512-522
  

Session 10B

• Cynthia Dwork, Moni Naor, Omer Reingold, Larry J. Stockmeyer:
  Magic Functions. 523-534
  
• Jeong Han Kim, Daniel R. Simon, Prasad Tetali:
  Limits on the Efficiency of One-Way Permutation-Based Hash Functions. 535-542
  
• Amit Sahai:
  Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security. 543-553
  
• Tomas Sander, Adam Young, Moti Yung:
  Non-Interactive CryptoComputing For NC¹. 554-567
  

Session 11A

• Jon M. Kleinberg, Yuval Rabani, Éva Tardos:
  Fairness in Routing and Load Balancing. 568-578
  
• Ashish Goel, Piotr Indyk:
  Stochastic Load Balancing and Related Problems. 579-586
  
• Malwina J. Luczak, Eli Upfal:
  Reducing Network Congestion and Blocking Probability Through Balanced Allocation. 587-595
  
• Roman M. Kolpakov, Gregory Kucherov:
  Finding Maximal Repetitions in a Word in Linear Time. 596-604
  
• Avi Shoshan, Uri Zwick:
  All Pairs Shortest Paths in Undirected Graphs with Integer Weights. 605-615
  

Session 11B

• Rosa I. Arriaga, Santosh Vempala:
  An Algorithmic Theory of Learning: Robust Concepts and Random Projection. 616-623
  
• Adam Klivans, Rocco A. Servedio:
  Boosting and Hard-Core Sets. 624-633
  
• Sanjoy Dasgupta:
  Learning Mixtures of Gaussians. 634-644
  
• Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy:
  Regular Languages Are Testable with a Constant Number of Queries. 645-655
  
• Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy:
  Efficient Testing of Large Graphs. 656-666