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 BibTeX
- Rajeev Motwani, Joseph Naor, Moni Naor:
The Probabilistic Method Yields Deterministic Parallel Algorithms.
8-13 BibTeX
- Aviad Cohen, Avi Wigderson:
Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract).
14-19 BibTeX
- Alan Siegel:
On Universal Classes of Fast High Performance Hash Functions, Their Time-Space Tradeoff, and Their Applications (Extended Abstract).
20-25 BibTeX
- Robert E. Schapire:
The Strength of Weak Learnability (Extended Abstract).
28-33 BibTeX
- 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 BibTeX
- David Haussler:
Generalizing the PAC Model: Sample Size Bounds From Metric Dimension-based Uniform Convergence Results.
40-45 BibTeX
- Sally A. Goldman, Ronald L. Rivest, Robert E. Schapire:
Learning Binary Relations and Total Orders (Extended Abstract).
46-51 BibTeX
- Bonnie Berger, John Rompel, Peter W. Shor:
Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry.
54-59 BibTeX
- Odile Marcotte, Subhash Suri:
Fast Matching Algorithms for Points on a Polygon (Extended Abstract).
60-65 BibTeX
- Greg N. Frederickson, D. J. Guan:
Ensemble Motion Planning in Trees.
66-71 BibTeX
- János Pach, William L. Steiger, Endre Szemerédi:
An Upper Bound on the Number of Planar k-Sets.
72-79 BibTeX
- Matthew Dickerson:
The Inverse of an Automorphism in Polynomial Time.
82-87 BibTeX
- Joachim von zur Gathen:
Testing Permutation Polynomials (Extended Abstract).
88-92 BibTeX
- László Babai, Lajos Rónyai:
Computing Irreducible Representations of Finite Groups.
93-98 BibTeX
- Lajos Rónyai:
Galois Groups and Factoring Polynomials over Finite Fields.
99-104 BibTeX
- Harold N. Gabow, Ying Xu:
Efficient Algorithms for Independent Assignments on Graphic and Linear Matroids.
106-111 BibTeX
- Gary L. Miller, Joseph Naor:
Flow in Planar Graphs with Multiple Sources and Sinks (Extended Abstract).
112-117 BibTeX
- Joseph Cheriyan, Torben Hagerup:
A Randomized Maximum-Flow Algorithm.
118-123 BibTeX
- Nathan Linial, Umesh V. Vazirani:
Graph Products and Chromatic Numbers.
124-128 BibTeX
- Cheng Ng:
Lower Bounds for the Stable Marriage Problem and its Variants.
129-133 BibTeX
- Leslie A. Hall, David B. Shmoys:
Approximation Schemes for Constrained Scheduling Problems.
134-139 BibTeX
- Miklós Ajtai, Yuri Gurevich:
Datalog vs. First-Order Logic.
142-147 BibTeX
- Martín Abadi, Joseph Y. Halpern:
Decidability and Expressiveness for First-Order Logics of Probability (Extended Abstract).
148-153 BibTeX
- Stephen A. Cook, Bruce M. Kapron:
Characterizations of the Basic Feasible Functionals of Finite Type (Extended Abstract).
154-159 BibTeX
- Leszek Pacholski, Wieslaw Szwast:
The 0-1 Law Fails for the Class of Existential Second Order Gödel Sentences with Equality.
160-163 BibTeX
- Rajeev Alur, Thomas A. Henzinger:
A Really Temporal Logic.
164-169 BibTeX
- James R. Russell:
Full Abstraction for Nondeterministic Dataflow Networks.
170-175 BibTeX
- Michael T. Goodrich, S. Rao Kosaraju:
Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation (Preliminary Version).
190-195 BibTeX
- Omer Berkman, Uzi Vishkin:
Recursive *-Tree Parallel Data-Structure (Extended Abstract).
196-202 BibTeX
- Ker-I Ko:
Computational Complexity of Roots of Real Functions (Extended Abstract).
204-209 BibTeX
- Karl R. Abrahamson, John A. Ellis, Michael R. Fellows, Manuel E. Mata:
On the Complexity of Fixed Parameter Problems (Extended Abstract).
210-215 BibTeX
- Mark W. Krentel:
Structure in Locally Optimal Solutions (Extended Abstract).
216-221 BibTeX
- Russell Impagliazzo, Gábor Tardos:
Decision Versus Search Problems in Super-Polynomial Time.
222-227 BibTeX
- Russell Impagliazzo, Michael Luby:
One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract).
230-235 BibTeX
- Russell Impagliazzo, Moni Naor:
Efficient Cryptographic Schemes Provably as Secure as Subset Sum.
236-241 BibTeX
- Michael Kharitonov, Andrew V. Goldberg, Moti Yung:
Lower Bounds for Pseudorandom Number Generators.
242-247 BibTeX
- Russell Impagliazzo, David Zuckerman:
How to Recycle Random Bits.
248-253 BibTeX
- Nick Littlestone, Manfred K. Warmuth:
The Weighted Majority Algorithm.
256-261 BibTeX
- Wolfgang Maass, György Turán:
On the Complexity of Learning From Counterexamples (Extended Abstract).
262-267 BibTeX
- Wen-Guey Tzeng:
The Equivalence and Learning of Probabilistic Automata (Extended Abstract).
268-273 BibTeX
- Amos Fiat, Shahar Moses, Adi Shamir, Ilan Shimshoni, Gábor Tardos:
Planning and Learning in Permutation Groups.
274-279 BibTeX
- Vijaya Ramachandran, John H. Reif:
An Optimal Parallel Algorithm for Graph Planarity (Extended Abstract).
282-287 BibTeX
- Samir Khuller, Baruch Schieber:
Efficient Parallel Algorithms for Testing Connectivity and Finding Disjoint s-t Paths in Graphs (Extended Summary).
288-293 BibTeX
- Lefteris M. Kirousis, Maria J. Serna, Paul G. Spirakis:
The Parallel Complexity of the Subgraph Connectivity Problem.
294-299 BibTeX
- 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 BibTeX
- Andrew Chi-Chih Yao:
Lower Bounds for Algebraic Computation Trees with Integer Inputs.
308-313 BibTeX
- Susan Landau:
Simplification of Nested Radicals.
314-319 BibTeX
- Bettina Just:
Generalizing the Continued Fraction Algorithm to Arbitrary Dimensions.
320-324 BibTeX
- Yishay Mansour, Baruch Schieber, Prasoon Tiwari:
The Complexity of Approximating the Square Root (Extended Summary).
325-330 BibTeX
- James R. Driscoll, Dennis M. Healy Jr.:
Asymptotically Fast Algorithms for Spherical and Related Transforms.
344-349 BibTeX
- Andrew V. Goldberg, Serge A. Plotkin, David B. Shmoys, Éva Tardos:
Interior-Point Methods in Parallel Computation.
350-355 BibTeX
- Baruch Awerbuch, Yishay Mansour, Nir Shavit:
Polynomial End-To-End Communication (Extended Abstract).
358-363 BibTeX
- Baruch Awerbuch, Andrew V. Goldberg, Michael Luby, Serge A. Plotkin:
Network Decomposition and Locality in Distributed Computation.
364-369 BibTeX
- Yehuda Afek, Eli Gafni, Moty Ricklin:
Upper and Lower Bounds for Routing Schemes in Dynamic Networks (Abstract).
370-375 BibTeX
- Tao Jiang:
The Synchronization of Nonuniform Networks of Finite Automata (Extended Abstract).
376-381 BibTeX
- Frank Thomson Leighton, Bruce M. Maggs:
Expanders Might Be Practical: Fast Algorithms for Routing Around Faults on Multibutterflies.
384-389 BibTeX
- Kieran T. Herley:
Efficient Simulations of Small Shared Memories on Bounded Degree Networks (Preliminary Version).
390-395 BibTeX
- C. Greg Plaxton:
On the Network Complexity of Selection.
396-401 BibTeX
- Gene Itkis, Leonid A. Levin:
Power of Fast VLSI Models Is Insensitive to Wires' Thinness.
402-407 BibTeX
- Piotr Berman, Juan A. Garay, Kenneth J. Perry:
Towards Optimal Distributed Consensus (Extended Abstract).
410-415 BibTeX
- Eyal Kushilevitz:
Privacy and Communication Complexity.
416-421 BibTeX
- Benny Chor, Lior Moscovici:
Solvability in Asynchronous Environments (Extended Abstract).
422-427 BibTeX
- Danny Dolev, Tomás Feder:
Multiparty Communication Complexity.
428-433 BibTeX
- Giuseppe Di Battista, Roberto Tamassia:
Incremental Planarity Testing (Extended Abstract).
436-441 BibTeX
- Andrei Z. Broder:
Generating Random Spanning Trees.
442-447 BibTeX
- Greg N. Frederickson:
Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems (Preliminary Version).
448-453 BibTeX
- Elias Dahlhaus, Marek Karpinski:
An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract).
454-459 BibTeX
- Anne Condon, Richard J. Lipton:
On the Complexity of Space Bounded Interactive Proofs (Extended Abstract).
462-467 BibTeX
- Donald Beaver, Shafi Goldwasser:
Multiparty Computation with Faulty Majority (Extended Announcement).
468-473 BibTeX
- Joe Kilian, Silvio Micali, Rafail Ostrovsky:
Minimum Resource Zero-Knowledge Proofs (Extended Abstract).
474-479 BibTeX
- Cynthia Dwork, Larry J. Stockmeyer:
On the Power of 2-Way Probabilistic Finite State Automata (Extended Abstract).
480-485 BibTeX
- David P. Dobkin, Subhash Suri:
Dynamically Computing the Maxima of Decomposable Functions, with Applications.
488-493 BibTeX
- Steven Fortune:
Stable Maintenance of Point Set Triangulations in Two Dimensions.
494-499 BibTeX
- Victor Milenkovic:
Double Precision Geometry: A General Technique for Calculating Line and Segment Intersections Using Rounded Arithmetic.
500-505 BibTeX
- Ruth Kuchem, Dorothea Wagner, Frank Wagner:
Area-Optimal Three-Layer Channel Routing.
506-511 BibTeX
- Seinosuke Toda:
On the Computational Power of PP and +P.
514-519 BibTeX
- 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 BibTeX
- Milena Mihail:
Conductance and Convergence of Markov Chains-A Combinatorial Treatment of Expanders.
526-531 BibTeX
- Jin-yi Cai:
Lower Bounds for Constant Depth Circuits in the Presence of Help Bits.
532-537 BibTeX
- Cecilia R. Aragon, Raimund Seidel:
Randomized Search Trees.
540-545 BibTeX
- Kurt Mehlhorn, Stefan Näher, Monika Rauch:
On the Complexity of a Game Related to the Dictionary Problem.
546-548 BibTeX
- Guy Jacobson:
Space-efficient Static Trees and Graphs.
549-554 BibTeX
- Rajamani Sundar:
Twists, Turns, Cascades, Deque Conjecture, and Scanning Theorem.
555-559 BibTeX
- Ran Raz, Avi Wigderson:
Probabilistic Communication Complexity of Boolean Relations (Extended Abstract).
562-567 BibTeX
- Jin-yi Cai, Richard J. Lipton:
Subquadratic Simulations of Circuits by Branching Programs.
568-573 BibTeX
- Nathan Linial, Yishay Mansour, Noam Nisan:
Constant Depth Circuits, Fourier Transform, and Learnability.
574-579 BibTeX
- Eric Allender:
A Note on the Power of Threshold Circuits.
580-584 BibTeX
- Bernard Chazelle:
An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra (Detailed Abstract).
586-591 BibTeX
- Ketan Mulmuley:
On Obstructions in Relation to a Fixed Viewpoint.
592-597 BibTeX
- Mark H. Overmars, Micha Sharir:
Output-Sensitive Hidden Surface Removal.
598-603 BibTeX
- Mark D. Hansen:
Approximation Algorithms for Geometric Embeddings in the Plane with Applications to Parallel Processing Problems (Extended Abstract).
604-609 BibTeX
- Jin-yi Cai, Martin Fürer, Neil Immerman:
An Optimal Lower Bound on the Number of Variables for Graph Identification.
612-617 BibTeX
- Maciej Liskiewicz, Krzysztof Lorys:
On Reversal Complexity for Alternating Turing Machines (Extended Abstract).
618-623 BibTeX
- Stephen A. Fenner, Stuart A. Kurtz, James S. Royer:
Every Polynomial-Time 1-Degree Collapses iff P=PSPACE.
624-629 BibTeX
Copyright © Fri Sep 5 19:44:50 2008
by Michael Ley (ley@uni-trier.de)
