15. STOC 1983
Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA. ACM 1972
- 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
- 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
- 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
- Patrick W. Dymond, Martin Tompa:
Speedups of Deterministic Machines by Synchronous Parallel Machines.
336-343
- 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
Copyright © Tue Nov 10 00:17:37 2009
by Michael Ley (ley@uni-trier.de)
