38. FOCS 1997: Miami Beach, Florida, USA

38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997. IEEE Computer Society

Session 1A

Andrew V. Goldberg, Satish Rao:
Beyond the Flow Decomposition Barrier. 2-11
Electronic Edition (IEEE Computer Society DL) BibTeX
Mikkel Thorup:
Undirected Single Source Shortest Path in Linear Time. 12-21
Electronic Edition (IEEE Computer Society DL) BibTeX
Bernard Chazelle:
A Faster Deterministic Algorithm for Minimum Spanning Trees. 22-31
Electronic Edition (IEEE Computer Society DL) BibTeX
Andrew V. Goldberg, Satish Rao:
Flows in Undirected Unit Capacity Networks. 32-34
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 1B:

Pascal Koiran:
Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties. 36-45
Electronic Edition (IEEE Computer Society DL) BibTeX
Tomas Sander, Mohammad Amin Shokrollahi:
Deciding Properties of Polynomials Without Factoring. 46-55
Electronic Edition (IEEE Computer Society DL) BibTeX
Saugata Basu:
An Improved Algorithm for Quantifier Elimination Over Real Closed Fields. 56-65
Electronic Edition (IEEE Computer Society DL) BibTeX
Attila Kondacs, John Watrous:
On the Power of Quantum Finite State Automata. 66-75
Electronic Edition (IEEE Computer Society DL) BibTeX

Invited Talk

Amir Pnueli:
Two Decades of Temporal Logic: Achievements and Challenges (Abstract). 78
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 2A

John Havlicek:
Computable Obstructions to Wait-free Computability. 80-89
Electronic Edition (IEEE Computer Society DL) BibTeX
Péter Gács:
Reliable Cellular Automata with Self-Organization. 90-99
Electronic Edition (IEEE Computer Society DL) BibTeX
Rajeev Alur, Thomas A. Henzinger, Orna Kupferman:
Alternating-time Temporal Logic. 100-109
Electronic Edition (IEEE Computer Society DL) BibTeX
Richard J. Lipton, Paul J. Martino, Andy Neitzke:
On the Complexity of a Set-Union Problem. 110-115
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 2B

J. Ian Munro, Venkatesh Raman:
Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs. 118-126
Electronic Edition (IEEE Computer Society DL) BibTeX
Piotr Indyk:
Deterministic Superimposed Coding with Applications to Pattern Matching. 127-136
Electronic Edition (IEEE Computer Society DL) BibTeX
Martin Farach:
Optimal Suffix Tree Construction with Large Alphabets. 137-143
Electronic Edition (IEEE Computer Society DL) BibTeX
Amihood Amir, Yonatan Aumann, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein:
Pattern Matching with Swaps. 144-153
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 3A

Tamal K. Dey:
Improved Bounds on Planar k-sets and k-levels. 165-161
Electronic Edition (IEEE Computer Society DL) BibTeX
Leonid Khachiyan, Lorant Porkolab:
Computing Integral Points in Convex Semi-algebraic Sets. 162-171
Electronic Edition (IEEE Computer Society DL) BibTeX
Joel Hass, J. C. Lagarias, Nicholas Pippenger:
The Computational Complexity of Knot and Link Problems. 172-181
Electronic Edition (IEEE Computer Society DL) BibTeX
Kasturi R. Varadarajan, Pankaj K. Agarwal:
Approximating Shortest Paths on an Nonconvex Polyhedron. 182-191
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 3B

Artur Czumaj, Volker Stemann:
Randomized Allocation Processes. 194-203
Electronic Edition (IEEE Computer Society DL) BibTeX
Dimitris Achlioptas, Michael S. O. Molloy:
The Analysis of a List-Coloring Algorithm on a Random Graph. 204-212
Electronic Edition (IEEE Computer Society DL) BibTeX
Leslie Ann Goldberg, Philip D. MacKenzie:
Contention Resolution with Guaranteed Constant Expected Delay. 213-222
Electronic Edition (IEEE Computer Society DL) BibTeX
Russ Bubley, Martin E. Dyer:
Path Coupling: A Technique for Proving Rapid Mixing in Markov Chains. 223-231
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 4A

Ran Raz, Pierre McKenzie:
Separation of the Monotone NC Hierarchy. 234-243
Electronic Edition (IEEE Computer Society DL) BibTeX
Klaus Reinhardt, Eric Allender:
Making Nondeterminism Unambiguous. 244-253
Electronic Edition (IEEE Computer Society DL) BibTeX
Maria Luisa Bonet, Toniann Pitassi, Ran Raz:
No Feasible Interpolation for TC0-Frege Proofs. 254-263
Electronic Edition (IEEE Computer Society DL) BibTeX
Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan:
Weak Random Sources, Hitting Sets, and BPP Simulations. 264-272
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 4B

Claudson F. Bornstein, Bruce M. Maggs, Gary L. Miller, R. Ravi:
Parallelizing Elimination Orders with Linear Fill. 274-283
Electronic Edition (IEEE Computer Society DL) BibTeX
Bruce M. Maggs, Friedhelm Meyer auf der Heide, Berthold Vöcking, Matthias Westermann:
Exploiting Locality for Data Management in Systems of Limited Bandwidth. 284-293
Electronic Edition (IEEE Computer Society DL) BibTeX
Matthew Andrews, Antonio Fernández, Mor Harchol-Balter, Frank Thomson Leighton, Lisa Zhang:
General Dynamic Routing with Per-Packet Delay Guarantees of O(distance + 1 / session rate). 294-302
Electronic Edition (IEEE Computer Society DL) BibTeX
Yair Bartal, John W. Byers, Danny Raz:
Global Optimization Using Local Information with Applications to Flow Control. 303-312
Electronic Edition (IEEE Computer Society DL) BibTeX

Invited Talk

Shafi Goldwasser:
New Directions in Cryptography: Twenty Some Years Later. 314-324
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 5A

Amos Fiat, Manor Mendel:
Truly Online Paging with Locality of Reference. 326-335
Electronic Edition (IEEE Computer Society DL) BibTeX
Sabah al-Binali:
The Competitive Analysis of Risk Taking with Applications to Online Trading. 336-344
Electronic Edition (IEEE Computer Society DL) BibTeX
Bala Kalyanasundaram, Kirk Pruhs:
Minimizing Flow Time Nonclairvoyantly. 345-352
Electronic Edition (IEEE Computer Society DL) BibTeX
Jon M. Kleinberg, Rajeev Motwani, Prabhakar Raghavan, Suresh Venkatasubramanian:
Storage Management for Evolving Databases. 353-362
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 5B

Eyal Kushilevitz, Rafail Ostrovsky:
Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. 364-373
Electronic Edition (IEEE Computer Society DL) BibTeX
Mihir Bellare, Russell Impagliazzo, Moni Naor:
Does Parallel Repetition Lower the Error in Computationally Sound Protocols? 374-383
Electronic Edition (IEEE Computer Society DL) BibTeX
Yair Frankel, Peter Gemmell, Philip D. MacKenzie, Moti Yung:
Optimal Resilience Proactive Public-Key Cryptosystems. 384-393
Electronic Edition (IEEE Computer Society DL) BibTeX
Mihir Bellare, Anand Desai, E. Jokipii, Phillip Rogaway:
A Concrete Security Treatment of Symmetric Encryption. 394-403
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 6A

Howard J. Karloff, Uri Zwick:
A 7/8-Approximation Algorithm for MAX 3SAT? 406-415
Electronic Edition (IEEE Computer Society DL) BibTeX
Aravind Srinivasan:
Improved Approximations for Edge-Disjoint Paths, Unsplittable Flow, and Related Routing Problems. 416-425
Electronic Edition (IEEE Computer Society DL) BibTeX
Stavros G. Kolliopoulos, Clifford Stein:
Improved Approximation Algorithms for Unsplittable Flow Problems. 426-435
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 6B

Marc Fischlin:
Lower Bounds for the Signature Size of Incremental Schemes. 438-447
Electronic Edition (IEEE Computer Society DL) BibTeX
Amit Sahai, Salil P. Vadhan:
A Complete Promise Problem for Statistical Zero-Knowledge. 448-457
Electronic Edition (IEEE Computer Society DL) BibTeX
Moni Naor, Omer Reingold:
Number-theoretic Constructions of Efficient Pseudo-random Functions. 458-467
Electronic Edition (IEEE Computer Society DL) BibTeX
Jin-yi Cai, Ajay Nerurkar:
An Improved Worst-Case to Average-Case Connection for Lattice Problems. 468-477
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 7A

Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, Kristina Vuskovic:
Finding an Even Hole in a Graph. 480-485
Electronic Edition (IEEE Computer Society DL) BibTeX
Jørgen Bang-Jensen, Tibor Jordán:
Edge-Connectivity Augmentation Preserving Simplicity. 486-495
Electronic Edition (IEEE Computer Society DL) BibTeX
Christopher Umans, William Lenhart:
Hamiltonian Cycles in Solid Grid Graphs. 496-505
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 7B

Santosh Vempala:
A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces. 508-513
Electronic Edition (IEEE Computer Society DL) BibTeX
Edith Cohen:
Learning Noisy Perceptrons by a Perceptron in Polynomial Time. 514-523
Electronic Edition (IEEE Computer Society DL) BibTeX
Andris Ambainis, Richard Desper, Martin Farach, Sampath Kannan:
Nearly Tight Bounds on the Learnability of Evolution. 524-533
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 8A

Joseph Naor, Baruch Schieber:
Improved Approximations for Shallow-Light Spanning Trees. 536-541
Electronic Edition (IEEE Computer Society DL) BibTeX
Baruch Awerbuch, Yossi Azar:
Buy-at-Bulk Network Design. 542-547
Electronic Edition (IEEE Computer Society DL) BibTeX
Joseph Naor, Leonid Zosin:
A 2-Approximation Algorithm for the Directed Multiway Cut Problem. 548-553
Electronic Edition (IEEE Computer Society DL) BibTeX
Sanjeev Arora:
Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems. 554-563
Electronic Edition (IEEE Computer Society DL) BibTeX

Session 8B

Ramamohan Paturi, Pavel Pudlák, Francis Zane:
Satisfiability Coding Lemma. 566-574
Electronic Edition (IEEE Computer Society DL) BibTeX
Edith Hemaspaandra, Gerd Wechsung:
The Minimization Problem for Boolean Formulas. 575-584
Electronic Edition (IEEE Computer Society DL) BibTeX
Jaikumar Radhakrishnan, Amnon Ta-Shma:
Tight Bounds for Depth-two Superconcentrators. 585-594
Electronic Edition (IEEE Computer Society DL) BibTeX
Jin-yi Cai, D. Sivakumar, Martin Strauss:
Constant Depth Circuits and the Lutz Hypothesis. 595-604
Electronic Edition (IEEE Computer Society DL) BibTeX