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