default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID26th FOCS 1985: Portland, Oregon, USA
- 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985. IEEE Computer Society 1985, ISBN 0-8186-0644-4
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 F. 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 O. Shallit:
Factoring with Cyclotomic Polynomials. 443-450 - Erich L. 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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-11-02 20:54 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
