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 BibTeX
- Miklós Ajtai, Avi Wigderson:
Deterministic Simulation of Probabilistic Constant Depth Circuits (Preliminary Version).
11-19 BibTeX
- Ravi B. Boppana:
Amplification of Probabilistic Boolean Formulas.
20-29 BibTeX
- Nicholas Pippenger:
On Networks of Noisy Gates.
30-38 BibTeX
- David S. Johnson, Christos H. Papadimitriou, Mihalis Yannakakis:
How Easy Is Local Search? (Extended Abstract).
39-42 BibTeX
- Joseph JáJá:
Identification Is Easier Than Decoding.
43-50 BibTeX
- Klaus Ambos-Spies:
Three Theorems on Polynomial Degrees of NP-Sets.
51-55 BibTeX
- Ming Li:
Simulating Two Pushdown Stores by One Tape in O(n^1.5 sqrt(log n)) Time.
56-64 BibTeX
- Friedhelm Meyer auf der Heide:
Nondeterministic versus Probabilistic Linear Search Algorithms.
65-73 BibTeX
- Christos H. Papadimitriou, David Wolfe:
The Complexity of Facets Resolved.
74-78 BibTeX
- Dorit S. Hochbaum, David B. Shmoys:
Using Dual Approximation Algorithms for Scheduling Problems: Theoretical and Practical Results.
79-89 BibTeX
- Harold N. Gabow:
A Scaling Algorithm for Weighted Matching on General Graphs.
90-100 BibTeX
- Alistair Moffat, Tadao Takaoka:
An All Pairs Shortest Path Algorithm with Expected Running Time O(n^2 log n).
101-105 BibTeX
- Csaba P. Gabor, Wen-Lian Hsu, Kenneth J. Supowit:
Recognizing Circle Graphs in Polynomial Time.
106-116 BibTeX
- Marshall W. Bern, Eugene L. Lawler, A. L. Wong:
Why Certain Subgraph Computations Require Only Linear Time.
117-125 BibTeX
- Gad M. Landau, Uzi Vishkin:
Efficient String Matching in the Presence of Errors.
126-136 BibTeX
- Daniel S. Hirschberg, Lawrence L. Larmore:
The Least Weight Subsequence Problem (Extended Abstract).
137-143 BibTeX
- John H. Reif, Micha Sharir:
Motion Planning in the Presence of Moving Obstacles.
144-154 BibTeX
- Takao Asano, Tetsuo Asano, Leonidas J. Guibas, John Hershberger, Hiroshi Imai:
Visibility-Polygon Search and Euclidean Shortest Paths.
155-164 BibTeX
- Bernard Chazelle:
Slimming Down Search Structures: A Functional Approach to Algorithm Design.
165-174 BibTeX
- Lefteris M. Kirousis, Christos H. Papadimitriou:
The Complexity of Recognizing Polyhedral Scenes (Extended Abstract).
175-185 BibTeX
- Alok Aggarwal, Maria M. Klawe, David Lichtenstein, Nathan Linial, Avi Wigderson:
Multi-Layer Grid Embeddings.
186-196 BibTeX
- Paul M. B. Vitányi:
Area Penalty for Sublinear Signal Propagation Delay on Chip (Preliminary Version).
197-207 BibTeX
- Richard Cole, Alan Siegel:
On Information Flow and Sorting: New Upper and Lower Bounds for VLSI Circuits (Extended Abstract).
208-221 BibTeX
- Mikhail J. Atallah, Susanne E. Hambrusch:
Solving Tree Problems on a Mesh-Connected Processor Array (Preliminary Version).
222-231 BibTeX
- Ming-Deh A. Huang:
Solving Some Graph Problems with Optimal or Near-Optimal Speedup on Mesh-of-Trees Networks.
232-240 BibTeX
- Ronald I. Greenberg, Charles E. Leiserson:
Randomized Routing on Fat-Trees (Preliminary Version).
241-249 BibTeX
- Baruch Awerbuch, Robert G. Gallager:
Distributed BFS Algorithms.
250-256 BibTeX
- 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 BibTeX
- Paul Feldman, Silvio Micali:
Byzantine Agreement in Constant Expected Time (and Trusting No One).
267-276 BibTeX
- Noga Alon, Peter Frankl, Vojtech Rödl:
Geometrical Realization of Set Systems and Probabilistic Communication Complexity.
277-280 BibTeX
- Pedro Celis, Per-Åke Larson, J. Ian Munro:
Robin Hood Hashing (Preliminary Report).
281-288 BibTeX
- Michael J. Fischer, Mike Paterson:
Dynamic Monotone Priorities on Planar Sets (Extended Abstract).
289-292 BibTeX
- Jeffrey Scott Vitter:
Design and Analysis of Dynamic Huffman Coding (Extended Abstract).
293-302 BibTeX
- Harry G. Mairson:
Average Case Lower Bounds on the Construction and Searching of Partial Orders.
303-311 BibTeX
- Micha Sharir, Ron Livne:
On Minima of Functions, Intersection Patterns of Curves, and Davenport-Schinzel Sequences.
312-320 BibTeX
- Steven Rudich:
Inferring the Structure of a Markov Chain from its Output.
321-326 BibTeX
- Moshe Y. Vardi:
Automatic Verification of Probabilistic Concurrent Finite-State Programs.
327-338 BibTeX
- Hans-Juergen Boehm:
Partial Polymorphic Type Inference Is Undecidable.
339-345 BibTeX
- Yuri Gurevich, Saharon Shelah:
Fixed-Point Extensions of First-Order Logic.
346-353 BibTeX
- Bruno Courcelle:
Equivalences and Transformations of Recursive Definitions.
354-359 BibTeX
- Zvi Galil, Stuart Haber, Moti Yung:
A Private Interactive Test of a Boolean Predicate and Minimum-Knowledge Public-Key Cryptosystems (Extended Abstract).
360-371 BibTeX
- Josh D. Cohen, Michael J. Fischer:
A Robust and Verifiable Cryptographically Secure Election Scheme (Extended Abstract).
372-382 BibTeX
- Benny Chor, Shafi Goldwasser, Silvio Micali, Baruch Awerbuch:
Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults (Extended Abstract).
383-395 BibTeX
- 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 BibTeX
- Michael Ben-Or, Nathan Linial:
Collective Coin Flipping, Robust Voting Schemes and Minima of Banzhaf Values.
408-416 BibTeX
- Umesh V. Vazirani, Vijay V. Vazirani:
Random Polynomial Time Is Equal to Slightly-random Polynomial Time.
417-428 BibTeX
- Benny Chor, Oded Goldreich:
Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity (Extended Abstract).
429-442 BibTeX
- Eric Bach, Jeffrey Shallit:
Factoring with Cyclotomic Polynomials.
443-450 BibTeX
- Erich Kaltofen:
Computing with Polynomials Given by Straight-Line Programs II: Sparse Factorization.
451-458 BibTeX
- András Frank, Éva Tardos:
An Application of Simultaneous Approximation in Combinatorial Optimization.
459-463 BibTeX
- László Lovász:
Computing ears and branchings in parallel.
464-467 BibTeX
- Alok Aggarwal, Bernard Chazelle, Leonidas J. Guibas, Colm Ó'Dúnlaing, Chee-Keng Yap:
Parallel Computational Geometry (Extended Abstract).
468-477 BibTeX
- Gary L. Miller, John H. Reif:
Parallel Tree Contraction and Its Application.
478-489 BibTeX
- Zvi Galil, Victor Y. Pan:
Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC.
490-495 BibTeX
- John H. Reif:
An Optimal Parallel Algorithm for Integer Sorting.
496-504 BibTeX
- Eugene M. Luks, Pierre McKenzie:
Fast Parallel Computation with Permutation Groups.
505-514 BibTeX
- Dexter Kozen, Chee-Keng Yap:
Algebraic Cell Decomposition in NC (Preliminary Version).
515-521 BibTeX
- Victor Y. Pan:
Fast and Efficient Algorithms for Sequential and Parallel Evaluation of Polynomial Zeros and of Matrix Polynomials.
522-531 BibTeX
- Friedhelm Meyer auf der Heide, Avi Wigderson:
The Complexity of Parallel Sorting.
532-540 BibTeX
- Richard M. Karp, Eli Upfal, Avi Wigderson:
The Complexity of Parallel Computation on Matroids.
541-550 BibTeX
Copyright © Sat May 16 23:12:25 2009
by Michael Ley (ley@uni-trier.de)
