15. STOC 1983: Boston, Massachusetts, USA
David S. Johnson, Ronald Fagin, Michael L. Fredman, David Harel, Richard M. Karp, Nancy A. Lynch, Christos H. Papadimitriou, Ronald L. Rivest, Walter L. Ruzzo, Joel I. Seiferas (Eds.): Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA. ACM 1983- 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
- 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
- Alfred V. Aho, Jeffrey D. Ullman, Mihalis Yannakakis: On Notions of Information Transfer in VLSI Circuits. 133-139
- Martin Fürer, Walter Schnyder, Ernst Specker: Normal Forms for Trivalent Graphs and Graphs of Bounded Valence. 161-170
- 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
- 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
- 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
- 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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T214307 by the dblp team