25th Annual Symposium on Foundations of Computer Science, West Palm Beach, Florida, USA, 24-26 October 1984.
IEEE Computer Society 1984
25. FOCS 1984:
West Palm Beach, Florida, USA
: Very Fast Parallel Matrix and Polynomial Arithmetic.
: A Comparative Study of X-Tree, Pyramid and Related Machines.
: Lower Bounds on Communication Complexity in Distributed Computer Networks (Preliminary Version).
: Parallel Communication with Limited Buffers (Preliminary Version).
Peter W. Shor
: The Average-Case Analysis of Some On-Line Algorithms for Bin Packing.
: Linear Verification for Spanning Trees.
: An Efficient Algorithm to Find all `Bidirectional' Edges of an Undirected Graph.
: Mulltiplication of Polynomials over the Ring of Integers.
: Slowing Down Sorting Networks to Obtain Faster Sorting Algorithms.
, Mike Shub
: Evaluating Rational Functions: Infinite Precision is Finite Cost and Tractable on Average (Extended Abstract).
: A Semantic Characterization of Full Abstraction for Typed Lambda Calculi.
: Minimal Degrees for Honest Polynomial Reducibilities.
, Micha Sharir
: Nonlinearity of Davenport-Schinzel Sequences and of a Generalized Path Compression Scheme.
: Computing on a Free Tree via Complexity-Preserving Mappings.
J. Ian Munro
: An Implicit Data Structure for the Dictionary Problem that Runs in Polylog Time.
Pravin M. Vaidya
: A fast approximation for minimum spanning trees in k-dimensional space.
: Independent Unbiased Coin Flips From a Correlated Biased Source: a Finite State Markov Chain.
: A Characterization of Probabilistic Inference.
: Constructing O(n log n) Size Monotone Formulae for the k-th Elementary Symmetric Polynomial of n Boolean Variables.