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 1997
Session 1A
- Mikkel Thorup: Undirected Single Source Shortest Path in Linear Time. 12-21
- Bernard Chazelle: A Faster Deterministic Algorithm for Minimum Spanning Trees. 22-31
Session 1B:
- Pascal Koiran: Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties. 36-45
- Tomas Sander, Mohammad Amin Shokrollahi: Deciding Properties of Polynomials Without Factoring. 46-55
- Saugata Basu: An Improved Algorithm for Quantifier Elimination Over Real Closed Fields. 56-65
Invited Talk
- Amir Pnueli: Two Decades of Temporal Logic: Achievements and Challenges (Abstract). 78
Session 2A
- John Havlicek: Computable Obstructions to Wait-free Computability. 80-89
- Péter Gács: Reliable Cellular Automata with Self-Organization. 90-99
Session 2B
- J. Ian Munro, Venkatesh Raman: Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs. 118-126
- Piotr Indyk: Deterministic Superimposed Coding with Applications to Pattern Matching. 127-136
- Martin Farach: Optimal Suffix Tree Construction with Large Alphabets. 137-143
- Amihood Amir, Yonatan Aumann, Gad M. Landau, Moshe Lewenstein, Noa Lewenstein: Pattern Matching with Swaps. 144-153
Session 3A
- Tamal K. Dey: Improved Bounds on Planar k-sets and k-levels. 156-161
- Joel Hass, J. C. Lagarias, Nicholas Pippenger: The Computational Complexity of Knot and Link Problems. 172-181
- Kasturi R. Varadarajan, Pankaj K. Agarwal: Approximating Shortest Paths on an Nonconvex Polyhedron. 182-191
Session 3B
- Dimitris Achlioptas, Michael S. O. Molloy: The Analysis of a List-Coloring Algorithm on a Random Graph. 204-212
- Leslie Ann Goldberg, Philip D. MacKenzie: Contention Resolution with Guaranteed Constant Expected Delay. 213-222
- Russ Bubley, Martin E. Dyer: Path Coupling: A Technique for Proving Rapid Mixing in Markov Chains. 223-231
Session 4A
- Maria Luisa Bonet, Toniann Pitassi, Ran Raz: No Feasible Interpolation for TC0-Frege Proofs. 254-263
- Alexander E. Andreev, Andrea E. F. Clementi, José D. P. Rolim, Luca Trevisan: Weak Random Sources, Hitting Sets, and BPP Simulations. 264-272
Session 4B
- Claudson F. Bornstein, Bruce M. Maggs, Gary L. Miller, R. Ravi: Parallelizing Elimination Orders with Linear Fill. 274-283
- 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
- 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
- Yair Bartal, John W. Byers, Danny Raz: Global Optimization Using Local Information with Applications to Flow Control. 303-312
Invited Talk
- Shafi Goldwasser: New Directions in Cryptography: Twenty Some Years Later. 314-324
Session 5A
- Sabah al-Binali: The Competitive Analysis of Risk Taking with Applications to Online Trading. 336-344
- Jon M. Kleinberg, Rajeev Motwani, Prabhakar Raghavan, Suresh Venkatasubramanian: Storage Management for Evolving Databases. 353-362
Session 5B
- Eyal Kushilevitz, Rafail Ostrovsky: Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. 364-373
- Mihir Bellare, Russell Impagliazzo, Moni Naor: Does Parallel Repetition Lower the Error in Computationally Sound Protocols? 374-383
- Yair Frankel, Peter Gemmell, Philip D. MacKenzie, Moti Yung: Optimal Resilience Proactive Public-Key Cryptosystems. 384-393
- Mihir Bellare, Anand Desai, E. Jokipii, Phillip Rogaway: A Concrete Security Treatment of Symmetric Encryption. 394-403
Session 6A
- Aravind Srinivasan: Improved Approximations for Edge-Disjoint Paths, Unsplittable Flow, and Related Routing Problems. 416-425
- Stavros G. Kolliopoulos, Clifford Stein: Improved Approximation Algorithms for Unsplittable Flow Problems. 426-435
Session 6B
- Marc Fischlin: Lower Bounds for the Signature Size of Incremental Schemes. 438-447
- Moni Naor, Omer Reingold: Number-theoretic Constructions of Efficient Pseudo-random Functions. 458-467
- Jin-yi Cai, Ajay Nerurkar: An Improved Worst-Case to Average-Case Connection for Lattice Problems. 468-477
Session 7A
- Michele Conforti, Gérard Cornuéjols, Ajai Kapoor, Kristina Vuskovic: Finding an Even Hole in a Graph. 480-485
Session 7B
- Santosh Vempala: A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces. 508-513
- Edith Cohen: Learning Noisy Perceptrons by a Perceptron in Polynomial Time. 514-523
- Andris Ambainis, Richard Desper, Martin Farach, Sampath Kannan: Nearly Tight Bounds on the Learnability of Evolution. 524-533
Session 8A
- Joseph Naor, Leonid Zosin: A 2-Approximation Algorithm for the Directed Multiway Cut Problem. 548-553
- Sanjeev Arora: Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems. 554-563
Session 8B
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-19T203413 by the dblp team