38. FOCS 1997: Miami Beach, Florida, USA

Session 1A

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

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
  
• Attila Kondacs, John Watrous:
  On the Power of Quantum Finite State Automata. 66-75
  

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
  
• Rajeev Alur, Thomas A. Henzinger, Orna Kupferman:
  Alternating-time Temporal Logic. 100-109
  
• Richard J. Lipton, Paul J. Martino, Andy Neitzke:
  On the Complexity of a Set-Union Problem. 110-115
  

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
  
• Leonid Khachiyan, Lorant Porkolab:
  Computing Integral Points in Convex Semi-algebraic Sets. 162-171
  
• 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

• Artur Czumaj, Volker Stemann:
  Randomized Allocation Processes. 194-203
  
• 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

• Ran Raz, Pierre McKenzie:
  Separation of the Monotone NC Hierarchy. 234-243
  
• Klaus Reinhardt, Eric Allender:
  Making Nondeterminism Unambiguous. 244-253
  
• 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

• Amos Fiat, Manor Mendel:
  Truly Online Paging with Locality of Reference. 326-335
  
• Sabah al-Binali:
  The Competitive Analysis of Risk Taking with Applications to Online Trading. 336-344
  
• Bala Kalyanasundaram, Kirk Pruhs:
  Minimizing Flow Time Nonclairvoyantly. 345-352
  
• 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

• Howard J. Karloff, Uri Zwick:
  A 7/8-Approximation Algorithm for MAX 3SAT? 406-415
  
• 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
  
• Amit Sahai, Salil P. Vadhan:
  A Complete Promise Problem for Statistical Zero-Knowledge. 448-457
  
• 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
  
• Jørgen Bang-Jensen, Tibor Jordán:
  Edge-Connectivity Augmentation Preserving Simplicity. 486-495
  
• Christopher Umans, William Lenhart:
  Hamiltonian Cycles in Solid Grid Graphs. 496-505
  

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, Baruch Schieber:
  Improved Approximations for Shallow-Light Spanning Trees. 536-541
  
• Baruch Awerbuch, Yossi Azar:
  Buy-at-Bulk Network Design. 542-547
  
• 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

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

Last update Fri May 25 08:14:15 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page