default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID30th 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, ISBN 0-8186-1982-1
- Bonnie Berger, John Rompel:
Simulating (log ^c n)-wise Independence in NC. 2-7 - 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 - Greg N. Frederickson, D. J. Guan:
Ensemble Motion Planning in Trees. 66-71 - 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 - László Babai
, Lajos Rónyai:
Computing Irreducible Representations of Finite Groups. 93-98 - 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 - Joseph Cheriyan, Torben Hagerup:
A Randomized Maximum-Flow Algorithm. 118-123 - Nathan Linial, Umesh V. Vazirani:
Graph Products and Chromatic Numbers. 124-128 - Cheng Ng:
Lower Bounds for the Stable Marriage Problem and its Variants. 129-133 - Leslie A. Hall, David B. Shmoys:
Approximation Schemes for Constrained Scheduling Problems. 134-139 - Miklós Ajtai, Yuri Gurevich:
Datalog vs. First-Order Logic. 142-147 - 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 - Rajeev Alur, Thomas A. Henzinger:
A Really Temporal Logic. 164-169 - 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 - Omer Berkman, Uzi Vishkin:
Recursive *-Tree Parallel Data-Structure (Extended Abstract). 196-202 - 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 - Russell Impagliazzo, David Zuckerman:
How to Recycle Random Bits. 248-253 - Nick Littlestone, Manfred K. Warmuth:
The Weighted Majority Algorithm. 256-261 - 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 - Gene Itkis, Leonid A. Levin:
Power of Fast VLSI Models Is Insensitive to Wires' Thinness. 402-407 - Piotr Berman, Juan A. Garay, Kenneth J. Perry:
Towards Optimal Distributed Consensus (Extended Abstract). 410-415 - Eyal Kushilevitz:
Privacy and Communication Complexity. 416-421 - Benny Chor, Lior Moscovici:
Solvability in Asynchronous Environments (Extended Abstract). 422-427 - Danny Dolev, Tomás Feder:
Multiparty Communication Complexity. 428-433 - Giuseppe Di Battista, Roberto Tamassia:
Incremental Planarity Testing (Extended Abstract). 436-441 - 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 - Ruth Kuchem, Dorothea Wagner, Frank Wagner:
Area-Optimal Three-Layer Channel Routing. 506-511 - 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 - Cecilia R. Aragon, Raimund Seidel:
Randomized Search Trees. 540-545 - 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 - Jin-yi Cai, Richard J. Lipton:
Subquadratic Simulations of Circuits by Branching Programs. 568-573 - 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 H. Overmars, Micha Sharir:
Output-Sensitive Hidden Surface Removal. 598-603 - 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
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 2025-11-02 21:03 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:
