39. FOCS 1998: Palo Alto, California, USA

39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8-11, 1998, Palo Alto, California, USA. IEEE Computer Society, 1998

Tutorial I

Jirí Matousek:
Geometric Computation and the Art of Sampling. 2
Electronic Edition (IEEE Computer Society DL) BibTeX

Tutorial II

Michael J. Kearns:
Theoretical Issues in Probabilistic Artificial Intelligence. 4
Electronic Edition (IEEE Computer Society DL) BibTeX

Tutorial III

Andrei Z. Broder, Monika Rauch Henzinger:
Information Retrieval on the Web. 6
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 1A

Venkatesan Guruswami, Daniel Lewin, Madhu Sudan, Luca Trevisan:
A Tight Characterization of NP with 3 Query PCPs. 8-17
Electronic Edition (IEEE Computer Society DL) BibTeX
Madhu Sudan, Luca Trevisan:
Probabilistically Checkable Proofs with Low Amortized Query Complexity. 18-27
Electronic Edition (IEEE Computer Society DL) BibTeX
Venkatesan Guruswami, Madhu Sudan:
Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. 28-39
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 1B

Matthew Andrews, Lisa Zhang:
The Access Network Design Problem. 40-59
Electronic Edition (IEEE Computer Society DL) BibTeX
Yishay Mansour, Boaz Patt-Shamir:
Jitter Control in QoS Networks. 50-59
Electronic Edition (IEEE Computer Society DL) BibTeX
David Gamarnik:
Stability of Adversarial Queues via Fluid Models. 60-70
Electronic Edition (IEEE Computer Society DL) BibTeX
Susanne Albers, Moses Charikar, Michael Mitzenmacher:
Delayed Information and Action in On-line Algorithms. 71-81
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 2A

Walter Unger:
The Complexity of the Approximation of the Bandwidth Problem. 82-91
Electronic Edition (IEEE Computer Society DL) BibTeX
Daniele Micciancio:
The Shortest Vector in a Lattice is Hard to Approximate to Within Some Constant. 92-98
Electronic Edition (IEEE Computer Society DL) BibTeX
Irit Dinur, Guy Kindler, Shmuel Safra:
Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard. 99-111
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 2B

Claudio Gutiérrez:
Satisfiability of Word Equations with Constants is in Exponential Space. 112-119
Electronic Edition (IEEE Computer Society DL) BibTeX
Géraud Sénizergues:
Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree. 120-129
Electronic Edition (IEEE Computer Society DL) BibTeX
Zakaria Bouziane:
A Primitive Recursive Algorithm for the General Petri Net Reachability Problem. 130-136
Electronic Edition (IEEE Computer Society DL) BibTeX
Mario Szegedy:
Algorithms to Tile the Infinite Grid with Finite Clusters. 137-147
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 3A

Piotr Indyk:
On Approximate Nearest Neighbors in Non-Euclidean Spaces. 148-155
Electronic Edition (IEEE Computer Society DL) BibTeX
David E. Cardoze, Leonard J. Schulman:
Pattern Matching for Spatial Point Sets. 156-165
Electronic Edition (IEEE Computer Society DL) BibTeX
Piotr Indyk:
Faster Algorithms for String Matching Problems: Matching the Convolution Bound. 166-173
Electronic Edition (IEEE Computer Society DL) BibTeX
Martin Farach, Paolo Ferragina, S. Muthukrishnan:
Overcoming the Memory Bottleneck in Suffix Tree Construction. 174-185
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 3B

Markus Bläser:
Bivariate Polynomial Multiplication. 186-191
Electronic Edition (IEEE Computer Society DL) BibTeX
Vadim Olshevsky, Victor Y. Pan:
A Unified Superfast Algorithm for Boundary Rational Tangential Interpolation Problems and for Inversion and Factorization of Dense Structured Matrices. 192-201
Electronic Edition (IEEE Computer Society DL) BibTeX
Alan R. Woods:
Unsatisfiable Systems of Equations, Over a Finite Field. 202-211
Electronic Edition (IEEE Computer Society DL) BibTeX
Arnold Schönhage:
Multiplicative Complexity of Taylor Shifts and a New Twist of the Substitution Method. 212-217
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 4A

Ravi Kannan, Andreas Nolte:
Local Search in Smooth Convex Sets. 218-226
Electronic Edition (IEEE Computer Society DL) BibTeX
Mao-cheng Cai, Xiaotie Deng, Wenan Zang:
A TDI System and its Application to Approximation Algorithms. 227-243
Electronic Edition (IEEE Computer Society DL) BibTeX
Warren D. Smith, Nicholas C. Wormald:
Geometric Separator Theorems & Applications. 232-243
Electronic Edition (IEEE Computer Society DL) BibTeX
Andreas Brieden, Peter Gritzmann, Ravi Kannan, Victor Klee, László Lovász, Miklós Simonovits:
Approximation of Diameters: Randomization Doesn't Help. 244-251
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 4B

Paul Beame, Michael E. Saks, Jayram S. Thathachar:
Time-Space Tradeoffs for Branching Programs. 254-263
Electronic Edition (IEEE Computer Society DL) BibTeX
Jakob Pagter, Theis Rauhe:
Optimal Time-Space Trade-Offs for Sorting. 264-268
Electronic Edition (IEEE Computer Society DL) BibTeX
Dima Grigoriev, Alexander A. Razborov:
Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields. 269-278
Electronic Edition (IEEE Computer Society DL) BibTeX
Vince Grolmusz, Gábor Tardos:
Lower Bounds for (MOD p - MOD m) Circuits. 279-289
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 5A

Yefim Dinitz, Naveen Garg, Michel X. Goemans:
On the Single-Source Unsplittable Flow Problem. 290-299
Electronic Edition (IEEE Computer Society DL) BibTeX
Naveen Garg, Jochen Könemann:
Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. 300-309
Electronic Edition (IEEE Computer Society DL) BibTeX
Uri Zwick:
All Pairs Shortest Paths in Weighted Directed Graphs ¾ Exact and Almost Exact Algorithms. 310-319
Electronic Edition (IEEE Computer Society DL) BibTeX
Kasturi R. Varadarajan:
A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane. 320-331
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 5B

Andris Ambainis, Rusins Freivalds:
1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations. 332-341
Electronic Edition (IEEE Computer Society DL) BibTeX
Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson:
The Quantum Communication Complexity of Sampling. 342-351
Electronic Edition (IEEE Computer Society DL) BibTeX
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf:
Quantum Lower Bounds by Polynomials. 352-361
Electronic Edition (IEEE Computer Society DL) BibTeX
Wim van Dam:
Quantum Oracle Interrogation: Getting All Information for Almost Half the Price. 362-367
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 6A

Alan M. Frieze, Ravi Kannan, Santosh Vempala:
Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. 370-378
Electronic Edition (IEEE Computer Society DL) BibTeX
Moses Charikar, Chandra Chekuri, Ashish Goel, Sudipto Guha, Serge A. Plotkin:
Approximating a Finite Metric by a Small Number of Tree Metrics. 379-388
Electronic Edition (IEEE Computer Society DL) BibTeX
Santosh Vempala:
Random Projection: A New Approach to VLSI Layout. 389-395
Electronic Edition (IEEE Computer Society DL) BibTeX
Mikkel Thorup:
Map Graphs in Polynomial Time. 396-405
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 6B

Avrim Blum, Carl Burch, John Langford:
On Learning Monotone Boolean Functions. 408-415
Electronic Edition (IEEE Computer Society DL) BibTeX
Tao Jiang, Paul E. Kearney, Ming Li:
Orchestrating Quartets: Approximation and Data Correction. 416-425
Electronic Edition (IEEE Computer Society DL) BibTeX
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron:
Testing Monotonicity. 426-435
Electronic Edition (IEEE Computer Society DL) BibTeX
Mary Cryan, Leslie Ann Goldberg, Paul W. Goldberg:
Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model. 436-445
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 7A

Kamal Jain:
Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. 448-457
Electronic Edition (IEEE Computer Society DL) BibTeX
Moses Charikar, Balaji Raghavachari:
The Finite Capacity Dial-A-Ride Problem. 458-467
Electronic Edition (IEEE Computer Society DL) BibTeX
Wenceslas Fernandez de la Vega, Claire Kenyon:
A Randomized Approximation Scheme for Metric MAX-CUT. 468-471
Electronic Edition (IEEE Computer Society DL) BibTeX
Martin Skutella:
Semidefinite Relaxations for Parallel Machine Scheduling. 472-481
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 7B

Joe Kilian, Erez Petrank, Charles Rackoff:
Lower Bounds for Zero Knowledge on the Internet. 484-492
Electronic Edition (IEEE Computer Society DL) BibTeX
Christian Cachin, Claude Crépeau, Julien Marcil:
Oblivious Transfer with a Memory-Bounded Receiver. 493-502
Electronic Edition (IEEE Computer Society DL) BibTeX
Dominic Mayers, Andrew Chi-Chih Yao:
Quantum Cryptography with Imperfect Apparatus. 503-509
Electronic Edition (IEEE Computer Society DL) BibTeX
Johan Håstad, Mats Näslund:
The Security of Individual RSA Bits. 510-521
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 8A

Micah Adler, Bruce M. Maggs:
Protocols for Asymmetric Communication Channels. 522-533
Electronic Edition (IEEE Computer Society DL) BibTeX
Stephen Alstrup, Thore Husfeldt, Theis Rauhe:
Marked Ancestor Problems. 534-544
Electronic Edition (IEEE Computer Society DL) BibTeX
Larry Carter, Kang Su Gatlin:
Towards an Optimal Bit-Reversal Permutation Program. 544-555
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 8B

Christopher Umans:
The Minimum Equivalent DNF Problem and Shortest Implicants. 556-563
Electronic Edition (IEEE Computer Society DL) BibTeX
Luca de Alfaro, Thomas A. Henzinger, Orna Kupferman:
Concurrent Reachability Games. 564-575
Electronic Edition (IEEE Computer Society DL) BibTeX
Alexander Russell, David Zuckerman:
Perfect Information Leader Election in log*n + O(1) Rounds. 576-583
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 9A

Timothy M. Chan:
Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions. 586-595
Electronic Edition (IEEE Computer Society DL) BibTeX
Pankaj K. Agarwal, David Eppstein, Leonidas J. Guibas, Monika Rauch Henzinger:
Parametric and Kinetic Minimum Spanning Trees. 596-605
Electronic Edition (IEEE Computer Society DL) BibTeX
Saugata Basu:
On the Combinatorial and Topological Complexity of a Single Cell. 606-616
Electronic Edition (IEEE Computer Society DL) BibTeX
János Pach, Géza Tóth:
Which Crossing Number is it, Anyway? 617-627
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 9B

Ramamohan Paturi, Pavel Pudlák, Michael E. Saks, Francis Zane:
An Improved Exponential-Time Algorithm for k-SAT. 628-637
Electronic Edition (IEEE Computer Society DL) BibTeX
Maria Luisa Bonet, Juan Luis Esteban, Nicola Galesi, Jan Johannsen:
Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems. 638-647
Electronic Edition (IEEE Computer Society DL) BibTeX
Dima Grigoriev:
Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. 648-652
Electronic Edition (IEEE Computer Society DL) BibTeX
Russell Impagliazzo, Ramamohan Paturi, Francis Zane:
Which Problems Have Strongly Exponential Complexity? 653-663
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 10A

Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, Andrew Tomkins:
Recommendation Systems: A Probabilistic Analysis. 664-673
Electronic Edition (IEEE Computer Society DL) BibTeX
Uriel Feige, Joe Kilian:
Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs. 674-683
Electronic Edition (IEEE Computer Society DL) BibTeX
Jaikumar Radhakrishnan, Aravind Srinivasan:
Improved Bounds and Algorithms for Hypergraph Two-Coloring. 684-693
Electronic Edition (IEEE Computer Society DL) BibTeX
Yuval Rabani, Alistair Sinclair, Rolf Wanka:
Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes. 694-705
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 10B

Georg Gottlob, Nicola Leone, Francesco Scarcello:
The Complexity of Acyclic Conjunctive Queries. 706-715
Electronic Edition (IEEE Computer Society DL) BibTeX
Daniel Leivant:
A Characterization of NC by Tree Recurrence. 716-724
Electronic Edition (IEEE Computer Society DL) BibTeX
John C. Mitchell, Mark Mitchell, Andre Scedrov:
A Linguistic Characterization of Bounded Oracle Computation and Probabilistic Polynomial Time. 725-733
Electronic Edition (IEEE Computer Society DL) BibTeX
Russell Impagliazzo, Avi Wigderson:
Randomness vs. Time: De-Randomization under a Uniform Assumption. 734-743
Electronic Edition (IEEE Computer Society DL) BibTeX