25. FOCS 1984: West Palm Beach, Florida, USA

• Paul Beame, Stephen A. Cook, H. James Hoover:
  Log Depth Circuits for Division and Related Problems. 1-6
  
• Ravindran Kannan, Gary L. Miller, Larry Rudolph:
  Sublinear Parallel Algorithm for Computing the Greatest Common Divisor of Two Integers. 7-11
  
• Robert Endre Tarjan, Uzi Vishkin:
  Finding Biconnected Components and Computing Tree Functions in Logarithmic Parallel Time (Extended Summary). 12-20
  
• Wayne Eberly:
  Very Fast Parallel Matrix and Polynomial Arithmetic. 21-30
  
• Joachim von zur Gathen:
  Parallel Powering. 31-36
  
• Amos Fiat, Adi Shamir:
  Polymorphic Arrays: A Novel VLSI Layout for Systolic Computers. 37-45
  
• Oscar H. Ibarra, Michael A. Palis, Sam M. Kim:
  Designing Systolic Algorithms Using Sequential Machines. 46-55
  
• Friedhelm Meyer auf der Heide, Rüdiger Reischuk:
  On the Limits to Speed Up Parallel Machines by Large Hardware and Unbounded Communication. 56-64
  
• Richard Cole, Alan Siegel:
  River Routing Every Which Way, but Loose (Extended Abstract). 65-73
  
• Lenwood S. Heath:
  Embedding Planar Graphs in Seven Pages. 74-83
  
• Christos H. Papadimitriou, Jeffrey D. Ullman:
  A Communication-Time Tradeoff. 84-88
  
• Alok Aggarwal:
  A Comparative Study of X-Tree, Pyramid and Related Machines. 89-99
  
• Abbas El Gamal, Alon Orlitsky:
  Interactive Data Comparison. 100-108
  
• Prasoon Tiwari:
  Lower Bounds on Communication Complexity in Distributed Computer Networks (Preliminary Version). 109-117
  
• Ramamohan Paturi, Janos Simon:
  Probabilistic Communication Complexity (Preliminary Version). 118-126
  
• Nicholas Pippenger:
  Parallel Communication with Limited Buffers (Preliminary Version). 127-136
  
• Alon Itai, Michael Rodeh:
  The Multi-Tree Approach to Reliability in Distributed Networks. 137-147
  
• Gregory F. Sullivan:
  A Polynomial Time Algorithm for Fault Diagnosability. 148-156
  
• Andrei Z. Broder, Danny Dolev:
  Flipping coins in many pockets (Byzantine agreement on uniformly random values). 157-170
  
• Eli Upfal, Avi Wigderson:
  How to Share Memory in a Distributed System (A Preliminary Version). 171-180
  
• Thang Nguyen Bui, Soma Chaudhuri, Frank Thomson Leighton, Michael Sipser:
  Graph Bisection Algorithms with Good Average Case Behavior. 181-192
  
• Peter W. Shor:
  The Average-Case Analysis of Some On-Line Algorithms for Bin Packing. 193-200
  
• János Komlós:
  Linear Verification for Spanning Trees. 201-206
  
• Bhubaneswar Mishra:
  An Efficient Algorithm to Find all `Bidirectional' Edges of an Undirected Graph. 207-216
  
• Matthias F. M. Stallmann, Harold N. Gabow:
  An Augmenting Path Algorithm for the Parity Problem on Linear Matroids. 217-228
  
• László Babai, Endre Szemerédi:
  On the Complexity of Matrix Group Problems I. 229-240
  
• Daniel Kornhauser, Gary L. Miller, Paul G. Spirakis:
  Coordinating Pebble Motion on Graphs, the Diameter of Permutation Groups, and Applications. 241-250
  
• Michael Kaminski:
  Mulltiplication of Polynomials over the Ring of Integers. 251-254
  
• Richard Cole:
  Slowing Down Sorting Networks to Obtain Faster Sorting Algorithms. 255-260
  
• Lenore Blum, Mike Shub:
  Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average (Extended Abstract). 261-267
  
• Ronald Fagin, Joseph Y. Halpern, Moshe Y. Vardi:
  A Model-Theoretic Analysis of Knowledge: Preliminary Report. 268-278
  
• Ketan Mulmuley:
  A Semantic Characterization of Full Abstraction for Typed Lambda Calculi. 279-288
  
• John C. Mitchell:
  Semantic Models for Second-Order Lambda Calculus. 289-299
  
• Steven Homer:
  Minimal Degrees for Honest Polynomial Reducibilities. 300-307
  
• José L. Balcázar, Ronald V. Book, Timothy J. Long, Uwe Schöning, Alan L. Selman:
  Sparse Oracles and Uniform Complexity Classes. 308-311
  
• Sergiu Hart, Micha Sharir:
  Nonlinearity of Davenport-Schinzel Sequences and of a Generalized Path Compression Scheme. 313-319
  
• Noga Alon, V. D. Milman:
  Eigenvalues, Expanders and Superconcentrators (Extended Abstract). 320-322
  
• Albert G. Greenberg, Alan Weiss:
  A Lower Bound for Probabilistic Algorithms for Finite State Machines. 323-331
  
• Shlomo Moran, Marc Snir, Udi Manber:
  Applications of Ramsey's Theorem to Decision Trees Complexity (Preliminary Version). 332-337
  
• Michael L. Fredman, Robert Endre Tarjan:
  Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms. 338-346
  
• Harold N. Gabow, Zvi Galil, Thomas H. Spencer:
  Efficient Implementation of Graph Algorithms Using Contraction. 347-357
  
• Bernard Chazelle:
  Computing on a Free Tree via Complexity-Preserving Mappings. 358-368
  
• J. Ian Munro:
  An Implicit Data Structure for the Dictionary Problem that Runs in Polylog Time. 369-374
  
• Michael J. Fischer, Mike Paterson:
  Fishspear: A Priority Queue Algorithm (Extended Abstract). 375-386
  
• David P. Dobkin, Herbert Edelsbrunner:
  Space Searching for Intersecting Objects. 387-392
  
• Hiroshi Imai, Takao Asano:
  Dynamic Segment Intersection Search with Applications. 393-402
  
• Pravin M. Vaidya:
  A fast approximation for minimum spanning trees in k-dimensional space. 403-407
  
• Jyun-Sheng Chang, Chee-Keng Yap:
  A Polynomial Solution for Potato-peeling and other Polygon Inclusion and Enclosure Problems. 408-416
  
• Robert Sedgewick, Jeffrey Scott Vitter:
  Shortest Paths in Euclidean Graphs (Extended Abstract). 417-424
  
• Manuel Blum:
  Independent Unbiased Coin Flips From a Correlated Biased Source: a Finite State Markov Chain. 425-433
  
• Miklos Santha, Umesh V. Vazirani:
  Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract). 434-440
  
• Shafi Goldwasser, Silvio Micali, Ronald L. Rivest:
  A ``Paradoxical'' Solution to the Signature Problem (Extended Abstract). 441-448
  
• Werner Alexi, Benny Chor, Oded Goldreich, Claus-Peter Schnorr:
  RSA/Rabin Bits are 1/2 + 1/poly(log N) Secure. 449-457
  
• Umesh V. Vazirani, Vijay V. Vazirani:
  Efficient and Secure Pseudo-Random Number Generation (Extended Abstract). 458-463
  
• Oded Goldreich, Shafi Goldwasser, Silvio Micali:
  How to Construct Random Functions (Extended Abstract). 464-479
  
• Alan M. Frieze, Ravi Kannan, J. C. Lagarias:
  Linear Congruential Generators Do Not Produce Random Sequences. 480-484
  
• Leonard Pitt:
  A Characterization of Probabilistic Inference. 485-494
  
• Joachim Grollmann, Alan L. Selman:
  Complexity Measures for Public-Key Cryptosystems (Preliminary Report). 495-503
  
• J. Friedman:
  Constructing O(n log n) Size Monotone Formulae for the k-th Elementary Symmetric Polynomial of n Boolean Variables. 506-515
  

Last update Sun May 26 01:52:59 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page