26. FOCS 1985:
Portland,
Oregon
26th Annual Symposium on Foundations of Computer Science,
Portland, Oregon, 21-23 October 1985. IEEE Computer Society
- 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
- 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
- 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
- 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
- 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
- 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
Copyright © Thu Nov 12 00:34:09 2009
by Michael Ley (ley@uni-trier.de)
