15. STOC 1983: Boston, Massachusetts, USA

• Miklós Ajtai, János Komlós, Endre Szemerédi:
  An O(n log n) Sorting Network. 1-9
  
• John H. Reif, Leslie G. Valiant:
  A Logarithmic Time Sort for Linear Size Networks. 10-16
  
• Joachim von zur Gathen:
  Parallel algorithms for algebraic problems. 17-23
  
• Quentin F. Stout:
  Topological Matching. 24-31
  
• Péter Gács:
  Reliable Computation with Cellular Automata. 32-41
  
• Danny Dolev, Cynthia Dwork, Nicholas Pippenger, Avi Wigderson:
  Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version). 42-51
  
• Ashok K. Chandra, Steven Fortune, Richard J. Lipton:
  Unbounded Fan-in Circuits and Associative Functions. 52-60
  
• Michael Sipser:
  Borel Sets and Circuit Complexity. 61-69
  
• Friedhelm Meyer auf der Heide:
  A Polynomial Linear Search Algorithm for the N-Dimensional Knapsack Problem. 70-79
  
• Michael Ben-Or:
  Lower Bounds for Algebraic Computation Trees (Preliminary Report). 80-86
  
• Allan Borodin, Danny Dolev, Faith E. Fich, Wolfgang J. Paul:
  Bounds for Width Two Branching Programs. 87-93
  
• Ashok K. Chandra, Merrick L. Furst, Richard J. Lipton:
  Multi-Party Protocols. 94-99
  
• Faith E. Fich:
  New Bounds for Parallel Prefix Circuits. 100-109
  
• Leslie G. Valiant:
  Exponential Lower Bounds for Restricted Monotone Circuits. 110-117
  
• Larry J. Stockmeyer:
  The Complexity of Approximate Counting (Preliminary Version). 118-126
  
• Pavol Duris, Zvi Galil, Wolfgang J. Paul, Rüdiger Reischuk:
  Two Nonlinear Lower Bounds. 127-132
  
• Alfred V. Aho, Jeffrey D. Ullman, Mihalis Yannakakis:
  On Notions of Information Transfer in VLSI Circuits. 133-139
  
• Susan Landau, Gary L. Miller:
  Solvability by Radicals is in Polynomial Time. 140-151
  
• James R. Driscoll, Merrick L. Furst:
  On the Diameter of Permutation Groups. 152-160
  
• Martin Fürer, Walter Schnyder, Ernst Specker:
  Normal Forms for Trivalent Graphs and Graphs of Bounded Valence. 161-170
  
• László Babai, Eugene M. Luks:
  Canonical Labeling of Graphs. 171-183
  
• Eric Bach:
  How to Generate Random Integers with Known Factorization. 184-188
  
• Arjen K. Lenstra:
  Factoring Multivariate Polynomials over Finite Fields (Extended Abstract). 189-192
  
• Ravi Kannan:
  Improved Algorithms for Integer Programming and Related Lattice Problems. 193-206
  
• Colm Ó'Dúnlaing, Micha Sharir, Chee-Keng Yap:
  Retraction: A New Approach to Motion-Planning (Extended Abstract). 207-220
  
• Leonidas J. Guibas, Jorge Stolfi:
  Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. 221-234
  
• Daniel Dominic Sleator, Robert Endre Tarjan:
  Self-Adjusting Binary Trees. 235-245
  
• Harold N. Gabow, Robert Endre Tarjan:
  A Linear-Time Algorithm for a Special Case of Disjoint Set Union. 246-251
  
• Greg N. Frederickson:
  Data Structures for On-Line Updating of Minimum Spanning Trees (Preliminary Version). 252-257
  
• F. Frances Yao:
  A 3-Space Partition and Its Applications (Extended Abstract). 258-263
  
• Paris C. Kanellakis, Stavros S. Cosmadakis, Moshe Y. Vardi:
  Unary Inclusion Dependencies have Polynomial Time Inference Problems (Extended Abstract). 264-277
  
• Amir Pnueli:
  On the Extremely Fair Treatment of Probabilistic Algorithms. 278-290
  
• Dexter Kozen:
  A Probabilistic PDL. 291-297
  
• Yishai A. Feldman:
  A Decidable Propositional Probabilistic Dynamic Logic. 298-309
  
• Joseph Y. Halpern, Michael O. Rabin:
  A Logic to Reason about Likelihood. 310-319
  
• Ernst-Rüdiger Olderog:
  A Characterization of Hoare's Logic for Programs with Pascal-like Procedures. 320-329
  
• Michael Sipser:
  A Complexity Theoretic Approach to Randomness. 330-335
  
• Patrick W. Dymond, Martin Tompa:
  Speedups of Deterministic Machines by Synchronous Parallel Machines. 336-343
  
• Ravi Kannan:
  Alternation and the Power of Nondeterminism. 344-346
  
• Neil Immerman:
  Languages Which Capture Complexity Classes (Preliminary Report). 347-354
  
• Dale Myers:
  The Random Access Hierarchy (Preliminary Report). 355-364
  
• Joost Engelfriet:
  Iterated Pushdown Automata and Complexity Classes. 365-373
  
• Kazuo Iwama:
  Unique Decomposability of Shuffled Strings: A Formal Treatment of Asynchronous Time-Multiplexed Communication. 374-381
  
• Juris Hartmanis, Vivian Sewelson, Neil Immerman:
  Sparse Sets in NP-P: EXPTIME versus NEXPTIME. 382-391
  
• Paul Young:
  Some Structural Properties of Polynomial Reducibilities and Sets in NP. 392-401
  
• Leonard M. Adleman:
  On Breaking Generalized Knapsack Public Key Cryptosystems (Abstract). 402-412
  
• Douglas L. Long, Avi Wigderson:
  How Discreet is the Discrete Log? 413-420
  
• Michael Ben-Or, Benny Chor, Adi Shamir:
  On the Cryptographic Security of Single RSA Bits. 421-430
  
• Shafi Goldwasser, Silvio Micali, Andrew Chi-Chih Yao:
  Strong Signature Schemes. 431-439
  
• Manuel Blum:
  How to Exchange (Secret) Keys (Extended Abstract). 440-447
  
• Harold N. Gabow:
  An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems. 448-456
  
• Jeremy Spinrad:
  Transitive Orientation in O(n²) Time. 457-466
  
• Jonathan S. Turner:
  Probabilistic Analysis of Bandwidth Minimization Algorithms. 467-476
  
• Brenda S. Baker, Sandeep N. Bhatt, Frank Thomson Leighton:
  An Approximation Algorithm for Manhattan Routing (Extended Abstract). 477-486
  

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