HALPERN@IBM.COM (Joe Halpern) (01/22/91)
Factoring numbers using singular integers
L. Adleman
Randomization vs Computability in Online Problems
Xiaotie Deng, Sanjeev Mahajan
Hamiltonian Paths in Infinite Graphs
David Harel
A Lower Bound for Parallel String Matching
Dany Breslauer and Zvi Galil
Hidden Surface Removal With Respect to a Moving View Point
Ketan Mulmuley
Approximations and Optimal Geometric Divide-and-Conquer
Jiri Matousek
Integral Equations, System of Quadratic Equations, and Exponential
Time Completeness
Ker-I Ko
Fully Dynamic Algorithms for Edge-Connectivity Problems
Zvi Galil and Giuseppe F. Italiano
Local Expansion of Vertex-Transitive Graphs and Random Generation in
Finite Groups
Laszlo Babai
Lower Bounds for Non-Commutative Computation
Noam Nisan
Bounds on the Time to Reach Agreement in the Presence of Timing Uncer-
tainty
Hagit Attiya, Cynthia Dwork, Nancy Lynch, Larry Stockmeyer
Reducing Elliptic Curve Logarithms to Logarithms in a Finite Field
Alfred Menezes, Scott Vanstone, Tatsuaki Okamoto
Generic Computation and Its Complexity
Serge Abiteboul and Victor Vianu
Counting Linear Extensions Is #P-Complete
Graham Brightwell and Peter Winkler
Combining Tentative and Definite Executions for Very Fast Dependable
Parallel Computing
Z.M. Kedem, K.V. Palem, A. Raghunathan, P.G. Spirakis
A Model for Data in Motion
Simon Kahan
Rounds in Communication Complexity Revisited
Noam Nisan and Avi Wigderson
Average-Case Performance of Bin Packing Algorithms Under Discrete Uni-
form Distributions
Coffman, Courcoubetis, Garey, Johnson, McGeoch, Shor, Weber and
Yannakakis
Constructing Nonresidues in Finite Fields and the Extended Riemann Hy-
pothesis
Johannes Buchmann and Victor Shoup
Proof of the 4/3 Conjecture for Preemptive vs. Nonpreemptive Two-
Processor Scheduling
E.G. Coffman, Jr. and M.R. Garey
The Harmonic Online K-Server Algorithm is Competitive
Eddie Grove
Clique Partitions, Graph Compression and Speeding-up Algorithms
Tomas Feder and Rajeev Motwani
Counting Networks and Muli-Processor Coordination
James Aspnes, Maurice Herlihy and Nir Shavit
PP is Closed Under Intersection
Richard Beigel, Nick Reingold, and Daniel Spielman
Constant-Time Parallel Integer Sorting
Torben Hagerup
Rigorous Time/Space Tradeoffs for Inverting Functions
Amos Fiat and Moni Naor
Navigating in Unfamiliar Geometric Terrain
Avrim Blum, Prabhakar Raghavan and Baruch Schieber
General Completeness Theorems for 2-Party Games
Joe Kilian
Searching in the Presence of Linearly Bounded Errors
Javed A. Aslam and Aditi Dhagat
Polylogarithmic Checking of all Polynomial Time Programs
Leonid A. Levin, Laszlo Babai, Lance Fortnow, and Mario Szegedy
Fast Approximation Algorithms for Multicommodity Flow Problems
T. Leighton, F. Makedon, S. Plotkin, C. Stein, E. Tardos, S.
Tragoudas
Learning Decision Trees Using the Fourier Sprectrum
Eyal Kushilevitz and Yishay Mansour
Effective Noether Irreducibility Forms and Applications
Erich Kaltofen
When Trees Collide: An Approximation Algorithm for the Generalized
Steiner Tree Problem on Networks
Ajit Agrawal, Philip Klein and R. Ravi
Non-Malleable Cryptography
Danny Dolev, Cynthia Dwork and Moni Naor
A Matroid Approach to Finding Edge Connectivity and Packing
Arborescences
Harold N. Gabow
The Expressive Power of Voting Polynomials
J. Aspnes, R. Beigel, M. Furst, and S. Rudich
Algorithms for Parallel k-Vertex Connectivity and Sparse Certificates
Joseph Cheriyan and Ramakrishna Thurimella
Dynamic Trees and Dynamic Point Location
Michael T. Goodrich and Roberto Tamassia
Finding Hidden Hamiltonian Cycles
Andrei Z. Broder, Alan M. Frieze and Eli Shamir
An Efficient Algorithm for the Genus Problem with Explicit Con-
struction of Forbidden Subgraphs
Hristo Djidjev and John Reif
Improved Algorithms for Linear Inequalities with Two Variables per In-
equality
Edith Cohen and Nimrod Megiddo
When Won't Membership Queries Help
Dana Angluin and Michael Kharitonov
Self-Testing/Correcting for Polynomials and for Approximate Functions
P.Gemmell, R.Lipton, R.Rubinfeld, M.Sudan, A.Wigderson
Competitive Paging with Locality of Reference
A. Borodin, S. Irani, P. Raghavan, B. Schieber
Probabilistic Recurrence Relations
Richard M. Karp
Converting High Probability into Nearly-Constant Time- with Applica-
tions to Parallel Hashing
Yossi Matias and Uzi Vishkin
On-Line Learning of Linear Functiongs and Iterative Solution of Linear
Systems
N. Littlestone, P. M. Long and M.K. Warmuth
On Deterministic Approximation of DNF
Michael Luby and Boban Velickovic
Deterministic Algorithms for Undirected s-t Connectivity Using
Polynomial Time and Sublinear Space
Greg Barnes and Walter L. Ruzzo
Wait-free Parallel Algorithms for the Union-Find Problem
Richard J. Anderson and Heather S. Woll
Testing Finite State Machines
Mihalis Yannakakis and David Lee
Linear Approximation of Shortest Superstrings
A. Blum, T. Jiang, M. Li, J. Tromp, M. Yannakakis
Lower Bounds for Randomized k-Server and Motion Planning Algorithms
Howard Karloff, Yuval Rabani and Yiftach Ravid
Sampling and Integration of Near Log-Concave Functions
David Applegate and Ravi Kannan
Fast Monte Carlo Algorithms for Permutation Groups
L. Babai, G. Cooperman, L. Finkelstein, E. Luks, A. Seress
Perfect Cryptographic Security from Partially Independent Channels
Ueli M. Maurer
An Algebraic Hierarchy of Concurrent Programming Languages
E. Shapiro