26. FOCS 1985: Portland, Oregon, USA

Session 1

• Andrew Chi-Chih Yao:
  Separating the Polynomial-Time Hierarchy by Oracles (Preliminary Version). 1-10
  
• Miklós Ajtai, Avi Wigderson:
  Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version). 11-19
  
• Ravi B. Boppana:
  Amplification of Probabilistic Boolean Formulas. 20-29
  
• Nicholas Pippenger:
  On Networks of Noisy Gates. 30-38
  
• David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis:
  How Easy Is Local Search? (Extended Abstract). 39-42
  
• Joseph JáJá:
  Identification Is Easier Than Decoding. 43-50
  
• Klaus Ambos-Spies:
  Three Theorems on Polynomial Degrees of NP-Sets. 51-55
  
• Ming Li:
  Simulating Two Pushdown Stores by One Tape in O(n^1.5 sqrt(log n)) Time. 56-64
  
• Friedhelm Meyer auf der Heide:
  Nondeterministic versus Probabilistic Linear Search Algorithms. 65-73
  
• Christos H. Papadimitriou, David Wolfe:
  The Complexity of Facets Resolved. 74-78
  

Session 2

• Dorit S. Hochbaum, David B. Shmoys:
  Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results. 79-89
  
• Harold N. Gabow:
  A Scaling Algorithm for Weighted Matching on General Graphs. 90-100
  
• Alistair Moffat, Tadao Takaoka:
  An All Pairs Shortest Path Algorithm with Expected Running Time O(n^2 log n). 101-105
  
• Csaba P. Gabor, Wen-Lian Hsu, Kenneth J. Supowit:
  Recognizing Circle Graphs in Polynomial Time. 106-116
  
• Marshall W. Bern, Eugene L. Lawler, A. L. Wong:
  Why Certain Subgraph Computations Require Only Linear Time. 117-125
  
• Gad M. Landau, Uzi Vishkin:
  Efficient String Matching in the Presence of Errors. 126-136
  
• Daniel S. Hirschberg, Lawrence L. Larmore:
  The Least Weight Subsequence Problem (Extended Abstract). 137-143
  
• John H. Reif, Micha Sharir:
  Motion Planning in the Presence of Moving Obstacles. 144-154
  
• Takao Asano, Tetsuo Asano, Leonidas J. Guibas, John Hershberger, Hiroshi Imai:
  Visibility-Polygon Search and Euclidean Shortest Paths. 155-164
  
• Bernard Chazelle:
  Slimming Down Search Structures: A Functional Approach to Algorithm Design. 165-174
  
• Lefteris M. Kirousis, Christos H. Papadimitriou:
  The Complexity of Recognizing Polyhedral Scenes (Extended Abstract). 175-185
  

Session 3

• Alok Aggarwal, Maria M. Klawe, David Lichtenstein, Nathan Linial, Avi Wigderson:
  Multi-Layer Grid Embeddings. 186-196
  
• Paul M. B. Vitányi:
  Area Penalty for Sublinear Signal Propagation Delay on Chip (Preliminary Version). 197-207
  
• Richard Cole, Alan Siegel:
  On Information Flow and Sorting: New Upper and Lower Bounds for VLSI Circuits (Extended Abstract). 208-221
  
• Mikhail J. Atallah, Susanne E. Hambrusch:
  Solving Tree Problems on a Mesh-Connected Processor Array (Preliminary Version). 222-231
  
• Ming-Deh A. Huang:
  Solving Some Graph Problems with Optimal or Near-Optimal Speedup on Mesh-of-Trees Networks. 232-240
  
• Ronald I. Greenberg, Charles E. Leiserson:
  Randomized Routing on Fat-Trees (Preliminary Version). 241-249
  
• Baruch Awerbuch, Robert G. Gallager:
  Distributed BFS Algorithms. 250-256
  
• Francis Y. L. Chin, H. F. Ting:
  An Almost Linear Time and O(n log n + e) Messages Distributed Algorithm for Minimum-Weight Spanning Trees. 257-266
  
• Paul Feldman, Silvio Micali:
  Byzantine Agreement in Constant Expected Time (and Trusting No One). 267-276
  
• Noga Alon, Peter Frankl, Vojtech Rödl:
  Geometrical Realization of Set Systems and Probabilistic Communication Complexity. 277-280
  

Session 4

• Pedro Celis, Per-Åke Larson, J. Ian Munro:
  Robin Hood Hashing (Preliminary Report). 281-288
  
• Michael J. Fischer, Mike Paterson:
  Dynamic Monotone Priorities on Planar Sets (Extended Abstract). 289-292
  
• Jeffrey Scott Vitter:
  Design and Analysis of Dynamic Huffman Coding (Extended Abstract). 293-302
  
• Harry G. Mairson:
  Average Case Lower Bounds on the Construction and Searching of Partial Orders. 303-311
  
• Micha Sharir, Ron Livne:
  On Minima of Functions, Intersection Patterns of Curves, and Davenport-Schinzel Sequences. 312-320
  
• Steven Rudich:
  Inferring the Structure of a Markov Chain from its Output. 321-326
  
• Moshe Y. Vardi:
  Automatic Verification of Probabilistic Concurrent Finite-State Programs. 327-338
  
• Hans-Juergen Boehm:
  Partial Polymorphic Type Inference Is Undecidable. 339-345
  
• Yuri Gurevich, Saharon Shelah:
  Fixed-Point Extensions of First-Order Logic. 346-353
  
• Bruno Courcelle:
  Equivalences and Transformations of Recursive Definitions. 354-359
  

Session 5

• Zvi Galil, Stuart Haber, Moti Yung:
  A Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems (Extended Abstract). 360-371
  
• Josh D. Cohen, Michael J. Fischer:
  A Robust and Verifiable Cryptographically Secure Election Scheme (Extended Abstract). 372-382
  
• Benny Chor, Shafi Goldwasser, Silvio Micali, Baruch Awerbuch:
  Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults (Extended Abstract). 383-395
  
• Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, Roman Smolensky:
  The Bit Extraction Problem of t-Resilient Functions (Preliminary Version). 396-407
  
• Michael Ben-Or, Nathan Linial:
  Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values. 408-416
  
• Umesh V. Vazirani, Vijay V. Vazirani:
  Random Polynomial Time Is Equal to Slightly-random Polynomial Time. 417-428
  
• Benny Chor, Oded Goldreich:
  Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity (Extended Abstract). 429-442
  
• Eric Bach, Jeffrey Shallit:
  Factoring with Cyclotomic Polynomials. 443-450
  
• Erich Kaltofen:
  Computing with Polynomials Given by Straight-Line Programs II: Sparse Factorization. 451-458
  
• András Frank, Éva Tardos:
  An Application of Simultaneous Approximation in Combinatorial Optimization. 459-463
  

Session 6

• László Lovász:
  Computing ears and branchings in parallel. 464-467
  
• Alok Aggarwal, Bernard Chazelle, Leonidas J. Guibas, Colm Ó'Dúnlaing, Chee-Keng Yap:
  Parallel Computational Geometry (Extended Abstract). 468-477
  
• Gary L. Miller, John H. Reif:
  Parallel Tree Contraction and Its Application. 478-489
  
• Zvi Galil, Victor Y. Pan:
  Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC. 490-495
  
• John H. Reif:
  An Optimal Parallel Algorithm for Integer Sorting. 496-504
  
• Eugene M. Luks, Pierre McKenzie:
  Fast Parallel Computation with Permutation Groups. 505-514
  
• Dexter Kozen, Chee-Keng Yap:
  Algebraic Cell Decomposition in NC (Preliminary Version). 515-521
  
• Victor Y. Pan:
  Fast and Efficient Algorithms for Sequential and Parallel Evaluation of Polynomial Zeros and of Matrix Polynomials. 522-531
  
• Friedhelm Meyer auf der Heide, Avi Wigderson:
  The Complexity of Parallel Sorting. 532-540
  
• Richard M. Karp, Eli Upfal, Avi Wigderson:
  The Complexity of Parallel Computation on Matroids. 541-550
  

Last update Fri May 25 08:14:15 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page