19. STOC 1987: New York, New York, USA

• Don Coppersmith, Shmuel Winograd:
  Matrix Multiplication via Arithmetic Progressions. 1-6
  
• Andrew V. Goldberg, Robert Endre Tarjan:
  Solving Minimum-Cost Flow Problems by Successive Approximation. 7-18
  
• Greg N. Frederickson:
  A New Approach to All Pairs Shortest Paths in Planar Graphs (Extended Abstract). 19-28
  
• Pravin M. Vaidya:
  An Algorithm for Linear Programming which Requires O(((m+n)n^2 + (m+n)^1.5 n)L) Arithmetic Operations. 29-38
  
• Alok Aggarwal, Leonidas J. Guibas, James B. Saxe, Peter W. Shor:
  A Linear Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon. 39-45
  
• Kazuo Iwano, Kenneth Steiglitz:
  Testing for Cycles in Infinite Graphs with Periodic Structure (Extended Abstract). 46-55
  
• Kenneth L. Clarkson:
  Approximation Algorithms for Shortest Path Motion Planning (Extended Abstract). 56-65
  
• Bernard Chazelle, Herbert Edelsbrunner, Leonidas J. Guibas:
  The Complexity of Cutting Convex Polytopes. 66-76
  
• Roman Smolensky:
  Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. 77-82
  
• Paul Beame, Johan Håstad:
  Optimal Bounds for Decision Problems on the CRCW PRAM. 83-93
  
• Wolfgang Maass, Georg Schnitger, Endre Szemerédi:
  Two Tapes Are Better than One for Off-Line Turing Machines. 94-100
  
• David A. Mix Barrington, Denis Thérien:
  Finite Monoids and the Fine Structure of NC¹. 101-109
  
• Lane A. Hemachandra:
  The Strong Exponential Hierarchy Collapses. 110-122
  
• Samuel R. Buss:
  The Boolean Formula Value Problem Is in ALOGTIME. 123-131
  
• Miklós Ajtai, János Komlós, Endre Szemerédi:
  Deterministic Simulation in LOGSPACE. 132-140
  
• H. Venkateswaran:
  Properties that Characterize LOGCFL. 141-150
  
• Eric Allender:
  Some Consequences of the Existence of Pseudorandom Generators. 151-159
  
• Umesh V. Vazirani:
  Efficiency Considerations in Using Semi-random Sources (Extended Abstract). 160-168
  
• David Lichtenstein, Nathan Linial, Michael E. Saks:
  Imperfect Random Sources and Discrete Controlled Processes. 169-177
  
• Martin Fürer:
  The Power of Randomness for Communication Complexity (Preliminary Version). 178-181
  
• Oded Goldreich:
  Towards a Theory of Software Protection and Simulation by Oblivious RAMs. 182-194
  
• Martín Abadi, Joan Feigenbaum, Joe Kilian:
  On Hiding Information from an Oracle (Extended Abstract). 195-203
  
• Lance Fortnow:
  The Complexity of Perfect Zero-Knowledge (Extended Abstract). 204-209
  
• Uriel Feige, Amos Fiat, Adi Shamir:
  Zero Knowledge Proofs of Identity. 210-217
  
• Oded Goldreich, Silvio Micali, Avi Wigderson:
  How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. 218-229
  
• Baruch Awerbuch:
  Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election and Related Problems (Detailed Summary). 230-240
  
• Johan Håstad, Frank Thomson Leighton, Brian Rogoff:
  Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract). 241-253
  
• Gary L. Miller, Shang-Hua Teng:
  Dynamic Parallel Complexity of Computational Circuits. 254-263
  
• David Peleg, Eli Upfal:
  Constructing Disjoint Paths on Expander Graphs (Extended Abstract). 264-273
  
• Johan Håstad, Frank Thomson Leighton, Mark Newman:
  Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract). 274-284
  
• Michael J. Kearns, Ming Li, Leonard Pitt, Leslie G. Valiant:
  On the Learnability of Boolean Formulae. 285-295
  
• B. K. Natarajan:
  On Learning Boolean Functions. 296-304
  
• Alok Aggarwal, Bowen Alpern, Ashok K. Chandra, Marc Snir:
  A Model for Hierarchical Memory. 305-314
  
• Andrew V. Goldberg, Serge A. Plotkin, Gregory E. Shannon:
  Parallel Symmetry-Breaking in Sparse Graphs. 315-324
  
• Alok Aggarwal, Richard J. Anderson:
  A Random NC Algorithm for Depth First Search. 325-334
  
• Gary L. Miller, Vijaya Ramachandran:
  A New Graph Triconnectivity Algorithm and Its Parallelization. 335-344
  
• Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani:
  Matching Is as Easy as Matrix Inversion. 345-354
  
• Joseph Naor, Moni Naor, Alejandro A. Schäffer:
  Fast Parallel Algorithms for Chordal Graphs (Extended Abstract). 355-364
  
• Paul F. Dietz, Daniel Dominic Sleator:
  Two Algorithms for Maintaining Order in a List. 365-372
  
• Allan Borodin, Nathan Linial, Michael E. Saks:
  An Optimal Online Algorithm for Metrical Task Systems. 373-382
  
• J. Ian Munro:
  Searching a Two Key Table Under a Single Key. 383-387
  
• Lenwood S. Heath, Sorin Istrail:
  The Pagenumber of Genus g Graphs is O(g). 388-397
  
• Lajos Rónyai:
  Simple Algebras Are Difficult. 398-408
  
• László Babai, Eugene M. Luks, Ákos Seress:
  Permutation Groups in NC. 409-420
  
• Saharon Shelah, Joel Spencer:
  Threshold Spectra for Random Graphs. 421-424
  
• Phokion G. Kolaitis, Moshe Y. Vardi:
  The Decision Problem for the Probabilities of Higher-Order Properties. 425-435
  
• Gianfranco Bilardi, Franco P. Preparata:
  Size-Time Complexity of Boolean Networks for Prefix Computations. 436-442
  
• Erich Kaltofen:
  Single-Factor Hensel Lifting and its Application to the Straight-Line Complexity of Certain Polynomials. 443-452
  
• Eric Bach:
  Realistic Analysis of Some Randomized Algorithms. 453-461
  
• Leonard M. Adleman, Ming-Deh A. Huang:
  Recognizing Primes in Random Polynomial Time. 462-469
  

Last update Tue May 21 18:06:22 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page