30. FOCS 1989: Research Triangle Park, North Carolina, USA

• 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