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
- 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

Last update Wed May 22 23:32:55 2013
CET by the DBLP Team —
Data released under the ODC-BY 1.0 license — See also our legal information page