default search action
38th 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, ISBN 0-8186-8197-7
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
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
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
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 J. Lenhart:
Hamiltonian Cycles in Solid Grid Graphs. 496-505
Session 7B
- Santosh S. 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-23 19:18 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: