30. FOCS 1989: Research Triangle Park, North Carolina, USA
30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989. IEEE Computer Society 1989- Rajeev Motwani, Joseph Naor, Moni Naor: The Probabilistic Method Yields Deterministic Parallel Algorithms. 8-13
- Aviad Cohen, Avi Wigderson: Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract). 14-19
- Alan Siegel: On Universal Classes of Fast High Performance Hash Functions, Their Time-Space Tradeoff, and Their Applications (Extended Abstract). 20-25
- Robert E. Schapire: The Strength of Weak Learnability (Extended Abstract). 28-33
- Ming Li, Paul M. B. Vitányi: A Theory of Learning Simple Concepts Under Simple Distributions and Average Case Complexity for the Universal Distribution (Extended Abstract). 34-39
- David Haussler: Generalizing the PAC Model: Sample Size Bounds From Metric Dimension-based Uniform Convergence Results. 40-45
- Sally A. Goldman, Ronald L. Rivest, Robert E. Schapire: Learning Binary Relations and Total Orders (Extended Abstract). 46-51
- Bonnie Berger, John Rompel, Peter W. Shor: Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry. 54-59
- Odile Marcotte, Subhash Suri: Fast Matching Algorithms for Points on a Polygon (Extended Abstract). 60-65
- János Pach, William L. Steiger, Endre Szemerédi: An Upper Bound on the Number of Planar k-Sets. 72-79
- Matthew Dickerson: The Inverse of an Automorphism in Polynomial Time. 82-87
- Joachim von zur Gathen: Testing Permutation Polynomials (Extended Abstract). 88-92
- Lajos Rónyai: Galois Groups and Factoring Polynomials over Finite Fields. 99-104
- Harold N. Gabow, Ying Xu: Efficient Algorithms for Independent Assignments on Graphic and Linear Matroids. 106-111
- Gary L. Miller, Joseph Naor: Flow in Planar Graphs with Multiple Sources and Sinks (Extended Abstract). 112-117
- Cheng Ng: Lower Bounds for the Stable Marriage Problem and its Variants. 129-133
- Martín Abadi, Joseph Y. Halpern: Decidability and Expressiveness for First-Order Logics of Probability (Extended Abstract). 148-153
- Stephen A. Cook, Bruce M. Kapron: Characterizations of the Basic Feasible Functionals of Finite Type (Extended Abstract). 154-159
- Leszek Pacholski, Wieslaw Szwast: The 0-1 Law Fails for the Class of Existential Second Order Gödel Sentences with Equality. 160-163
- James R. Russell: Full Abstraction for Nondeterministic Dataflow Networks. 170-175
- S. Rao Kosaraju: Efficient Tree Pattern Matching (Preliminary Version). 178-183
- S. Rao Kosaraju: Pipelining Computations in a Tree of Processors (Preliminary Version). 184-189
- Michael T. Goodrich, S. Rao Kosaraju: Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation (Preliminary Version). 190-195
- Ker-I Ko: Computational Complexity of Roots of Real Functions (Extended Abstract). 204-209
- Karl R. Abrahamson, John A. Ellis, Michael R. Fellows, Manuel E. Mata: On the Complexity of Fixed Parameter Problems (Extended Abstract). 210-215
- Mark W. Krentel: Structure in Locally Optimal Solutions (Extended Abstract). 216-221
- Russell Impagliazzo, Gábor Tardos: Decision Versus Search Problems in Super-Polynomial Time. 222-227
- Russell Impagliazzo, Michael Luby: One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract). 230-235
- Russell Impagliazzo, Moni Naor: Efficient Cryptographic Schemes Provably as Secure as Subset Sum. 236-241
- Michael Kharitonov, Andrew V. Goldberg, Moti Yung: Lower Bounds for Pseudorandom Number Generators. 242-247
- Wolfgang Maass, György Turán: On the Complexity of Learning From Counterexamples (Extended Abstract). 262-267
- Wen-Guey Tzeng: The Equivalence and Learning of Probabilistic Automata (Extended Abstract). 268-273
- Amos Fiat, Shahar Moses, Adi Shamir, Ilan Shimshoni, Gábor Tardos: Planning and Learning in Permutation Groups. 274-279
- Vijaya Ramachandran, John H. Reif: An Optimal Parallel Algorithm for Graph Planarity (Extended Abstract). 282-287
- Samir Khuller, Baruch Schieber: Efficient Parallel Algorithms for Testing Connectivity and Finding Disjoint s-t Paths in Graphs (Extended Summary). 288-293
- Lefteris M. Kirousis, Maria J. Serna, Paul G. Spirakis: The Parallel Complexity of the Subgraph Connectivity Problem. 294-299
- Samir Khuller, Stephen G. Mitchell, Vijay V. Vazirani: Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem, and for Finding a Kuratowski Homeomorph. 300-305
- Andrew Chi-Chih Yao: Lower Bounds for Algebraic Computation Trees with Integer Inputs. 308-313
- Susan Landau: Simplification of Nested Radicals. 314-319
- Bettina Just: Generalizing the Continued Fraction Algorithm to Arbitrary Dimensions. 320-324
- Yishay Mansour, Baruch Schieber, Prasoon Tiwari: The Complexity of Approximating the Square Root (Extended Summary). 325-330
- Pravin M. Vaidya: Speeding-Up Linear Programming Using Fast Matrix Multiplication (Extended Abstract). 332-337
- Pravin M. Vaidya: A New Algorithm for Minimizing Convex Functions over Convex Sets (Extended Abstract). 338-343
- James R. Driscoll, Dennis M. Healy Jr.: Asymptotically Fast Algorithms for Spherical and Related Transforms. 344-349
- Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos: Interior-Point Methods in Parallel Computation. 350-355
- Baruch Awerbuch, Yishay Mansour, Nir Shavit: Polynomial End-To-End Communication (Extended Abstract). 358-363
- Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, Serge A. Plotkin: Network Decomposition and Locality in Distributed Computation. 364-369
- Yehuda Afek, Eli Gafni, Moty Ricklin: Upper and Lower Bounds for Routing Schemes in Dynamic Networks (Abstract). 370-375
- Tao Jiang: The Synchronization of Nonuniform Networks of Finite Automata (Extended Abstract). 376-381
- Frank Thomson Leighton, Bruce M. Maggs: Expanders Might Be Practical: Fast Algorithms for Routing Around Faults on Multibutterflies. 384-389
- Kieran T. Herley: Efficient Simulations of Small Shared Memories on Bounded Degree Networks (Preliminary Version). 390-395
- C. Greg Plaxton: On the Network Complexity of Selection. 396-401
- Piotr Berman, Juan A. Garay, Kenneth J. Perry: Towards Optimal Distributed Consensus (Extended Abstract). 410-415
- Eyal Kushilevitz: Privacy and Communication Complexity. 416-421
- Andrei Z. Broder: Generating Random Spanning Trees. 442-447
- Greg N. Frederickson: Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems (Preliminary Version). 448-453
- Elias Dahlhaus, Marek Karpinski: An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract). 454-459
- Anne Condon, Richard J. Lipton: On the Complexity of Space Bounded Interactive Proofs (Extended Abstract). 462-467
- Donald Beaver, Shafi Goldwasser: Multiparty Computation with Faulty Majority (Extended Announcement). 468-473
- Joe Kilian, Silvio Micali, Rafail Ostrovsky: Minimum Resource Zero-Knowledge Proofs (Extended Abstract). 474-479
- Cynthia Dwork, Larry J. Stockmeyer: On the Power of 2-Way Probabilistic Finite State Automata (Extended Abstract). 480-485
- David P. Dobkin, Subhash Suri: Dynamically Computing the Maxima of Decomposable Functions, with Applications. 488-493
- Steven Fortune: Stable Maintenance of Point Set Triangulations in Two Dimensions. 494-499
- Victor Milenkovic: Double Precision Geometry: A General Technique for Calculating Line and Segment Intersections Using Rounded Arithmetic. 500-505
- Seinosuke Toda: On the Computational Power of PP and +P. 514-519
- Michael R. Fellows, Michael A. Langston: An Analogue of the Myhill-Nerode Theorem and Its Use in Computing Finite-Basis Characterizations (Extended Abstract). 520-525
- Milena Mihail: Conductance and Convergence of Markov Chains-A Combinatorial Treatment of Expanders. 526-531
- Jin-yi Cai: Lower Bounds for Constant Depth Circuits in the Presence of Help Bits. 532-537
- Kurt Mehlhorn, Stefan Näher, Monika Rauch: On the Complexity of a Game Related to the Dictionary Problem. 546-548
- Guy Jacobson: Space-efficient Static Trees and Graphs. 549-554
- Rajamani Sundar: Twists, Turns, Cascades, Deque Conjecture, and Scanning Theorem. 555-559
- Ran Raz, Avi Wigderson: Probabilistic Communication Complexity of Boolean Relations (Extended Abstract). 562-567
- Nathan Linial, Yishay Mansour, Noam Nisan: Constant Depth Circuits, Fourier Transform, and Learnability. 574-579
- Eric Allender: A Note on the Power of Threshold Circuits. 580-584
- Bernard Chazelle: An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra (Detailed Abstract). 586-591
- Ketan Mulmuley: On Obstructions in Relation to a Fixed Viewpoint. 592-597
- Mark D. Hansen: Approximation Algorithms for Geometric Embeddings in the Plane with Applications to Parallel Processing Problems (Extended Abstract). 604-609
- Jin-yi Cai, Martin Fürer, Neil Immerman: An Optimal Lower Bound on the Number of Variables for Graph Identification. 612-617
- Maciej Liskiewicz, Krzysztof Lorys: On Reversal Complexity for Alternating Turing Machines (Extended Abstract). 618-623
- Stephen A. Fenner, Stuart A. Kurtz, James S. Royer: Every Polynomial-Time 1-Degree Collapses iff P=PSPACE. 624-629
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team