28. FOCS 1987: Los Angeles, California, USA

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

Last update Fri May 25 08:14:15 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page