30. FOCS 1989:
Research Triangle Park,
North Carolina
30th Annual Symposium on Foundations of Computer Science,
Research Triangle Park, North Carolina, 30 October - 1 November 1989. IEEE Computer Society
- 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
- 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
- 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
Copyright © Mon Nov 9 23:28:18 2009
by Michael Ley (ley@uni-trier.de)
