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