%A B. Chazelle
%T Polytope range searching and integral geometry
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A S. Ghosh
%A D. Mount
%T An output sensitive algorithm for computing visibility graphs
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A D. Dobkin
%A S. Friedman
%A K. Supowit
%T Delaunay graphs are almost as good as complete graphs
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A H. Edelsbrunner
%A J. Pach
%A J. Schwartz
%A M. Sharir
%T On the lower envelope of bivariate functions and its applications
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A J. Canny
%T A new algebraic method for robot motion planning and real geometry
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A J. Canny
%A J. Reif
%T New lower bound techniques for robot motion planning problems
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A P. Berman
%A R. Roos
%T Learning one-counter languages in polynomial time
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A N. Littlestone
%T Learning quickly when irrelevant attributes abound:
a new linear-threshold algorithm
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A R. Rivest
%A R. Schapire
%T Diversity-based inference of finite automata
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A V. Grolmusz
%A P. Ragde
%T Incomparability in parallel computation
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A A. Hajnal
%A W. Maass
%A P. Pudlak
%A M. Szegedy
%A G. Turan
%T Threshold circuits of bounded depth
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A Y. Gurevich
%T Complete and incomplete randomized NP problems
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A M. Blum
%A R. Impagliazzo
%T Generic oracles and oracle classes
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A D. Kozen
%A S. Landau
%A J. von zur Gathen
%T Polynomial decomposition algorithms
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A L. Ronyai
%T Factoring polynomials over finite fields
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A M. Kaminski
%A N. Bshouty
%T Multiplicative complexity of polynomial multiplication over finite fields
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A R. Mirwald
%A C. Schnorr
%T The multiplicative complexity of Boolean quadratic forms
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A M. Atallah
%A R. Cole
%A M. Goodrich
%T Cascading divide-and-conquer: a technique for designing parallel algorithms
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A M. Goldberg
%A T. Spencer
%T A new parallel algorithm for the maximal independent set problem
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A D. Grigoriev
%A M. Karpinski
%T The matching problem for bipartite graphs
with polynomially bounded permanents is in NC
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A V. Pan
%A J. Reif
%T On the complexity of some computations with polynomials and Toeplitz matrices
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A A. Ranade
%T How to emulate shared memory
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A M. Gereb-Graus
%A D. Krizanc
%T A lower bound of Omega(log log n) for randomized parallel merging
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A N. Alon
%A Y. Azar
%T The average complexity of deterministic and randomized
parallel comparison sorting algorithms
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A A. Aggarwal
%A A. Chandra
%A M. Snir
%T Hierarchical memory with block transfer
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A J. Lenstra
%A D. Shmoys
%A E. Tardos
%T Approximation algorithms for scheduling unrelated parallel machines
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A S. Rao
%T Finding near optimal separators in planar graphs
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A H. Gazit
%A G. Miller
%T A parallel algorithm for finding a separator in planar graphs
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A D. Matula
%T Determining edge connectivity in O(nm) steps
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A A. Kanevsky
%A V. Ramachandran
%T Improved algorithms for graph four-connectivity
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A D. Coppersmith
%A P. Raghavan
%A M. Tompa
%T Parallel graph algorithms that are efficient on average
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A L. Kucera
%T Canonical labeling of regular graphs in linear average time
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A R. Boppana
%T Eigenvalues and graph bisection: an average-case analysis
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A A. Broder
%A E. Shamir
%T On the second eigenvalue of random regular graphs
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A M. Ajtai
%T Recursive construction for 3-regular expanders
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A J. Kilian
%A S. Kipnis
%A C. Leiserson
%T The organization of permutation architectures with bussed interconnections
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A S. Gao
%A M. Kaufmann
%T Channel routing of multiterminal nets
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A P. Duris
%A Z. Galil
%T Two lower bounds in asynchronous distributed computation
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A N. Linial
%T Locality as an obstacle to distributed computing
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A H. Attiya
%A A. Bar-Noy
%A D. Dolev
%A D. Koller
%A D. Peleg
%A R. Reischuk
%T Achievable cases in an asynchronous environment
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A Y. Afek
%A B. Awerbuch
%A S. Plotkin
%A M. Saks
%T Local management of a global resource in a communication network
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A Y. Afek
%A B. Awerbuch
%A E. Gafni
%T Applying static network protocols to dynamic networks
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A A. Israeli
%A M. Li
%T Bounded time-stamps
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A G. Peterson
%A J. Burns
%T Concurrent reading while writing II: the multi-writer case
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A A. Yao
%T Lower bounds to randomized algorithms for graph properties
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A M. Hirsch
%A S. Vavasis
%T Exponential lower bounds for finding Brouwer fixed points
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A S. Cosmadakis
%T Database theory and cylindric lattices
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A J. Stern
%T Secret linear congruential generators are not cryptographically secure
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A P. Feldman
%T A practical scheme for verifiable secret sharing
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A W. Aiello
%A J. Hastad
%T Perfect zero-knowledge languages can be recognized in two rounds
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A O. Goldreich
%A Y. Mansour
%T Interactive proof systems: provers that never fail and random selection
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A Y. Oren
%T On the cunning power of cheating verifiers: some observations about zero knowledge proofs
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28

%A M. Tompa
%A H. Woll
%T Random self-reducibility
and zero knowledge interactive proofs of possession of information
%J Proceedings of the 28th Annual Symposium on Foundations of Computer Science
%C Los Angeles, California
%D October 1987
%K focs focs87 focs28