28. FOCS 1987:
Los Angeles,
California
28th Annual Symposium on Foundations of Computer Science,
Los Angeles, California, 27-29 October 1987. IEEE Computer Society
- Bernard Chazelle:
Polytope Range Searching and Integral Geometry (Extended Abstract).
1-10 BibTeX
- Subir Kumar Ghosh, David M. Mount:
An Output Sensitive Algorithm for Computing Visibility Graphs.
11-19 BibTeX
- David P. Dobkin, Steven J. Friedman, Kenneth J. Supowit:
Delaunay Graphs are Almost as Good as Complete Graphs.
20-26 BibTeX
- Herbert Edelsbrunner, János Pach, Jacob T. Schwartz, Micha Sharir:
On the Lower Envelope of Bivariate Functions and its Applications.
27-37 BibTeX
- John F. Canny:
A New Algebraic Method for Robot Motion Planning and Real Geometry.
39-48 BibTeX
- John F. Canny, John H. Reif:
New Lower Bound Techniques for Robot Motion Planning Problems.
49-60 BibTeX
- Piotr Berman, Robert Roos:
Learning One-Counter Languages in Polynomial Time (Extended Abstract).
61-67 BibTeX
- Nick Littlestone:
Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm (Extended Abstract).
68-77 BibTeX
- Ronald L. Rivest, Robert E. Schapire:
Diversity-Based Inference of Finite Automata (Extended Abstract).
78-87 BibTeX
- Vince Grolmusz, Prabhakar Ragde:
Incomparability in Parallel Computation.
89-98 BibTeX
- András Hajnal, Wolfgang Maass, Pavel Pudlák, Mario Szegedy, György Turán:
Threshold circuits of bounded depth.
99-110 BibTeX
- Yuri Gurevich:
Complete and Incomplete Randomized NP Problems.
111-117 BibTeX
- Manuel Blum, Russell Impagliazzo:
Generic Oracles and Oracle Classes (Extended Abstract).
118-126 BibTeX
- Joachim von zur Gathen, Dexter Kozen, Susan Landau:
Functional Decomposition of Polynomials.
127-131 BibTeX
- Lajos Rónyai:
Factoring Polynomials over Finite Fields.
132-137 BibTeX
- Michael Kaminski, Nader H. Bshouty:
Multiplicative complexity of polynomial multiplication over finite fields (Extended abstract).
138-140 BibTeX
- Roland Mirwald, Claus-Peter Schnorr:
The Multiplicative Complexity of Quadratic Boolean Forms.
141-150 BibTeX
- Mikhail J. Atallah, Richard Cole, Michael T. Goodrich:
Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms.
151-160 BibTeX
- Mark K. Goldberg, Thomas H. Spencer:
A New Parallel Algorithm for the Maximal Independent Set Problem.
161-165 BibTeX
- Dima Grigoriev, Marek Karpinski:
The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract).
166-172 BibTeX
- Victor Y. Pan, John H. Reif:
Some Polynomial and Toeplitz Matrix Computations.
173-184 BibTeX
- Abhiram G. Ranade:
How to emulate shared memory (Preliminary Version).
185-194 BibTeX
- Mihály Geréb-Graus, Danny Krizanc:
The Complexity of Parallel Comparison Merging.
195-201 BibTeX
- Alok Aggarwal, Ashok K. Chandra, Marc Snir:
Hierarchical Memory with Block Transfer.
204-216 BibTeX
- Jan Karel Lenstra, David B. Shmoys, Éva Tardos:
Approximation Algorithms for Scheduling Unrelated Parallel Machines.
217-224 BibTeX
- Satish Rao:
Finding Near Optimal Separators in Planar Graphs.
225-237 BibTeX
- Hillel Gazit, Gary L. Miller:
A Parallel Algorithm for Finding a Separator in Planar Graphs.
238-248 BibTeX
- David W. Matula:
Determining Edge Connectivity in O(nm).
249-251 BibTeX
- Arkady Kanevsky, Vijaya Ramachandran:
Improved Algorithms for Graph Four-Connectivity.
252-259 BibTeX
- Don Coppersmith, Prabhakar Raghavan, Martin Tompa:
Parallel Graph Algorithms that Are Efficient on Average.
260-269 BibTeX
- Ludek Kucera:
Canonical Labeling of Regular Graphs in Linear Average Time.
271-279 BibTeX
- Ravi B. Boppana:
Eigenvalues and Graph Bisection: An Average-Case Analysis (Extended Abstract).
280-285 BibTeX
- Andrei Z. Broder, Eli Shamir:
On the Second Eigenvalue of Random Regular Graphs (Preliminary Version).
286-294 BibTeX
- Miklós Ajtai:
Recursive Construction for 3-Regular Expanders.
295-304 BibTeX
- Joe Kilian, Shlomo Kipnis, Charles E. Leiserson:
The Organization of Permutation Architectures with Bussed Interconnections (Extended Abstract).
305-315 BibTeX
- Shaodi Gao, Michael Kaufmann:
Channel Routing of Multiterminal Nets.
316-325 BibTeX
- Pavol Duris, Zvi Galil:
Two Lower Bounds in Asynchronous Distributed Computation (Preliminary Version).
326-330 BibTeX
- Nathan Linial:
Distributive Graph Algorithms-Global Solutions from Local Data.
331-335 BibTeX
- Hagit Attiya, Amotz Bar-Noy, Danny Dolev, Daphne Koller, David Peleg, Rüdiger Reischuk:
Achievable Cases in an Asynchronous Environment (Extended Abstract).
337-346 BibTeX
- Yehuda Afek, Baruch Awerbuch, Serge A. Plotkin, Michael E. Saks:
Local Management of a Global Resource in a Communication Network.
347-357 BibTeX
- Yehuda Afek, Baruch Awerbuch, Eli Gafni:
Applying Static Network Protocols to Dynamic Networks.
358-370 BibTeX
- Amos Israeli, Ming Li:
Bounded Time-Stamps (Extended Abstract).
371-382 BibTeX
- Gary L. Peterson, James E. Burns:
Concurrent Reading While Writing II: The Multi-writer Case.
383-392 BibTeX
- Andrew Chi-Chih Yao:
Lower Bounds to Randomized Algorithms for Graph Properties (Extended Abstract).
393-400 BibTeX
- Michael D. Hirsch, Stephen A. Vavasis:
Exponential Lower Bounds for Finding Brouwer Fixed Points (Extended Abstract).
401-410 BibTeX
- Stavros S. Cosmadakis:
Database Theory and Cylindric Lattices (Extended Abstract).
411-420 BibTeX
- Jacques Stern:
Secret Linear Congruential Generators Are Not Cryptographically Secure.
421-426 BibTeX
- Paul Feldman:
A Practical Scheme for Non-interactive Verifiable Secret Sharing.
427-437 BibTeX
- William Aiello, Johan Håstad:
Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds.
439-448 BibTeX
- Oded Goldreich, Yishay Mansour, Michael Sipser:
Interactive Proof Systems: Provers that never Fail and Random Selection (Extended Abstract).
449-461 BibTeX
- Yair Oren:
On the Cunning Power of Cheating Verifiers: Some Observations about Zero Knowledge Proofs (Extended Abstract).
462-471 BibTeX
- Martin Tompa, Heather Woll:
Random Self-Reducibility and Zero Knowledge Interactive Proofs of Possession of Information.
472-482 BibTeX
- Robert Endre Tarjan, Christopher J. Van Wyk:
Correction to ``A Linear-Time Algorithm for Triangulating Simple Polygons''.
486 BibTeX
- Paul M. B. Vitányi, Baruch Awerbuch:
Errata to ``Atomic Shared Register Access by Asynchronous Hardware''.
487 BibTeX
- Noga Alon, Yossi Azar:
The Average Complexity of Deterministic and Randomized Parallel Comparison Sorting Algorithms.
489-498 BibTeX
Copyright © Sat May 16 23:12:25 2009
by Michael Ley (ley@uni-trier.de)
