stoc83.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>STOC 1983</title><link href="../../../dblp.css" rel="stylesheet" type="text/css" /></head> <body> <table width="100%"><tr><td align="left"><a href="../../index.html"><img alt="dblp.uni-trier.de" src="../../Logo.gif" border=0 height=60 width=170></a></td> <td align="right"><a href="http://www.uni-trier.de"><img alt="www.uni-trier.de" src="../../logo_universitaet-trier.gif" border=0 height=48 width=215></a></td></tr></table> <h1>15. <a href="index.html">STOC</a> 1983</h1> Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA. ACM 1972 <ul> <li><a name="AjtaiKS83" href="../../indices/a-tree/a/Ajtai:Mikl=oacute=s.html">Miklós Ajtai</a>, <a href="../../indices/a-tree/k/Koml=oacute=s:J=aacute=nos.html">János Komlós</a>, <a href="../../indices/a-tree/s/Szemer=eacute=di:Endre.html">Endre Szemerédi</a>: An O(n log n) Sorting Network. 1-9 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AjtaiKS83">BibTeX</a></font> <li><a name="ReifV83" href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>, <a href="../../indices/a-tree/v/Valiant:Leslie_G=.html">Leslie G. Valiant</a>: A Logarithmic Time Sort for Linear Size Networks. 10-16 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ReifV83">BibTeX</a></font> <li><a name="Gathen83" href="../../indices/a-tree/g/Gathen:Joachim_von_zur.html">Joachim von zur Gathen</a>: Parallel algorithms for algebraic problems. 17-23 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Gathen83">BibTeX</a></font> <li><a name="Stout83" href="../../indices/a-tree/s/Stout:Quentin_F=.html">Quentin F. Stout</a>: Topological Matching. 24-31 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Stout83">BibTeX</a></font> <li><a name="Gacs83" href="../../indices/a-tree/g/G=aacute=cs:P=eacute=ter.html">Péter Gács</a>: Reliable Computation with Cellular Automata. 32-41 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Gacs83">BibTeX</a></font> <li><a name="DolevDPW83" href="../../indices/a-tree/d/Dolev:Danny.html">Danny Dolev</a>, <a href="../../indices/a-tree/d/Dwork:Cynthia.html">Cynthia Dwork</a>, <a href="../../indices/a-tree/p/Pippenger:Nicholas.html">Nicholas Pippenger</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: Superconcentrators, Generalizers and Generalized Connectors with Limited Depth (Preliminary Version). 42-51 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DolevDPW83">BibTeX</a></font> <li><a name="Sipser83" href="../../indices/a-tree/s/Sipser:Michael.html">Michael Sipser</a>: Borel Sets and Circuit Complexity. 61-69 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Sipser83">BibTeX</a></font> <li><a name="Heide83" href="../../indices/a-tree/h/Heide:Friedhelm_Meyer_auf_der.html">Friedhelm Meyer auf der Heide</a>: A Polynomial Linear Search Algorithm for the N-Dimensional Knapsack Problem. 70-79 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Heide83">BibTeX</a></font> <li><a name="Ben-Or83" href="../../indices/a-tree/b/Ben=Or:Michael.html">Michael Ben-Or</a>: Lower Bounds for Algebraic Computation Trees (Preliminary Report). 80-86 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Ben-Or83">BibTeX</a></font> <li><a name="BorodinDFP83" href="../../indices/a-tree/b/Borodin:Allan.html">Allan Borodin</a>, <a href="../../indices/a-tree/d/Dolev:Danny.html">Danny Dolev</a>, <a href="../../indices/a-tree/f/Fich:Faith_E=.html">Faith E. Fich</a>, <a href="../../indices/a-tree/p/Paul:Wolfgang_J=.html">Wolfgang J. Paul</a>: Bounds for Width Two Branching Programs. 87-93 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BorodinDFP83">BibTeX</a></font> <li><a name="Fich83" href="../../indices/a-tree/f/Fich:Faith_E=.html">Faith E. Fich</a>: New Bounds for Parallel Prefix Circuits. 100-109 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Fich83">BibTeX</a></font> <li><a name="Valiant83" href="../../indices/a-tree/v/Valiant:Leslie_G=.html">Leslie G. Valiant</a>: Exponential Lower Bounds for Restricted Monotone Circuits. 110-117 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Valiant83">BibTeX</a></font> <li><a name="Stockmeyer83" href="../../indices/a-tree/s/Stockmeyer:Larry_J=.html">Larry J. Stockmeyer</a>: The Complexity of Approximate Counting (Preliminary Version). 118-126 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Stockmeyer83">BibTeX</a></font> <li><a name="DurisGPR83" href="../../indices/a-tree/d/Duris:Pavol.html">Pavol Duris</a>, <a href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/p/Paul:Wolfgang_J=.html">Wolfgang J. Paul</a>, <a href="../../indices/a-tree/r/Reischuk:R=uuml=diger.html">Rüdiger Reischuk</a>: Two Nonlinear Lower Bounds. 127-132 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DurisGPR83">BibTeX</a></font> <li><a name="AhoUY83" href="../../indices/a-tree/a/Aho:Alfred_V=.html">Alfred V. Aho</a>, <a href="../../indices/a-tree/u/Ullman:Jeffrey_D=.html">Jeffrey D. Ullman</a>, <a href="../../indices/a-tree/y/Yannakakis:Mihalis.html">Mihalis Yannakakis</a>: On Notions of Information Transfer in VLSI Circuits. 133-139 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AhoUY83">BibTeX</a></font> <li><a name="LandauM83" href="../../indices/a-tree/l/Landau:Susan.html">Susan Landau</a>, <a href="../../indices/a-tree/m/Miller:Gary_L=.html">Gary L. Miller</a>: Solvability by Radicals is in Polynomial Time. 140-151 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LandauM83">BibTeX</a></font> <li><a name="DriscollF83" href="../../indices/a-tree/d/Driscoll:James_R=.html">James R. Driscoll</a>, <a href="../../indices/a-tree/f/Furst:Merrick_L=.html">Merrick L. Furst</a>: On the Diameter of Permutation Groups. 152-160 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DriscollF83">BibTeX</a></font> <li><a name="FurerSS83" href="../../indices/a-tree/f/F=uuml=rer:Martin.html">Martin Fürer</a>, <a href="../../indices/a-tree/s/Schnyder:Walter.html">Walter Schnyder</a>, <a href="../../indices/a-tree/s/Specker:Ernst.html">Ernst Specker</a>: Normal Forms for Trivalent Graphs and Graphs of Bounded Valence. 161-170 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FurerSS83">BibTeX</a></font> <li><a name="BabaiL83" href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>, <a href="../../indices/a-tree/l/Luks:Eugene_M=.html">Eugene M. Luks</a>: Canonical Labeling of Graphs. 171-183 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BabaiL83">BibTeX</a></font> <li><a name="Bach83" href="../../indices/a-tree/b/Bach:Eric.html">Eric Bach</a>: How to Generate Random Integers with Known Factorization. 184-188 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Bach83">BibTeX</a></font> <li><a name="Lenstra83" href="../../indices/a-tree/l/Lenstra:Arjen_K=.html">Arjen K. Lenstra</a>: Factoring Multivariate Polynomials over Finite Fields (Extended Abstract). 189-192 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Lenstra83">BibTeX</a></font> <li><a name="Kannan83" href="../../indices/a-tree/k/Kannan:Ravi.html">Ravi Kannan</a>: Improved Algorithms for Integer Programming and Related Lattice Problems. 193-206 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Kannan83">BibTeX</a></font> <li><a name="ODunlaingSY83" href="../../indices/a-tree/=/=Oacute==D=uacute=nlaing:Colm.html">Colm Ó'Dúnlaing</a>, <a href="../../indices/a-tree/s/Sharir:Micha.html">Micha Sharir</a>, <a href="../../indices/a-tree/y/Yap:Chee=Keng.html">Chee-Keng Yap</a>: Retraction: A New Approach to Motion-Planning (Extended Abstract). 207-220 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ODunlaingSY83">BibTeX</a></font> <li><a name="GuibasS83" href="../../indices/a-tree/g/Guibas:Leonidas_J=.html">Leonidas J. Guibas</a>, <a href="../../indices/a-tree/s/Stolfi:Jorge.html">Jorge Stolfi</a>: Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. 221-234 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GuibasS83">BibTeX</a></font> <li><a name="SleatorT83" href="../../indices/a-tree/s/Sleator:Daniel_Dominic.html">Daniel Dominic Sleator</a>, <a href="../../indices/a-tree/t/Tarjan:Robert_Endre.html">Robert Endre Tarjan</a>: Self-Adjusting Binary Trees. 235-245 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/SleatorT83">BibTeX</a></font> <li><a name="GabowT83" href="../../indices/a-tree/g/Gabow:Harold_N=.html">Harold N. Gabow</a>, <a href="../../indices/a-tree/t/Tarjan:Robert_Endre.html">Robert Endre Tarjan</a>: A Linear-Time Algorithm for a Special Case of Disjoint Set Union. 246-251 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GabowT83">BibTeX</a></font> <li><a name="Frederickson83" href="../../indices/a-tree/f/Frederickson:Greg_N=.html">Greg N. Frederickson</a>: Data Structures for On-Line Updating of Minimum Spanning Trees (Preliminary Version). 252-257 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Frederickson83">BibTeX</a></font> <li><a name="Yao83" href="../../indices/a-tree/y/Yao:F=_Frances.html">F. Frances Yao</a>: A 3-Space Partition and Its Applications (Extended Abstract). 258-263 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Yao83">BibTeX</a></font> <li><a name="KanellakisCV83" href="../../indices/a-tree/k/Kanellakis:Paris_C=.html">Paris C. Kanellakis</a>, <a href="../../indices/a-tree/c/Cosmadakis:Stavros_S=.html">Stavros S. Cosmadakis</a>, <a href="../../indices/a-tree/v/Vardi:Moshe_Y=.html">Moshe Y. Vardi</a>: Unary Inclusion Dependencies have Polynomial Time Inference Problems (Extended Abstract). 264-277 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KanellakisCV83">BibTeX</a></font> <li><a name="Pnueli83" href="../../indices/a-tree/p/Pnueli:Amir.html">Amir Pnueli</a>: On the Extremely Fair Treatment of Probabilistic Algorithms. 278-290 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Pnueli83">BibTeX</a></font> <li><a name="Kozen83" href="../../indices/a-tree/k/Kozen:Dexter.html">Dexter Kozen</a>: A Probabilistic PDL. 291-297 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Kozen83">BibTeX</a></font> <li><a name="Feldman83" href="../../indices/a-tree/f/Feldman:Yishai_A=.html">Yishai A. Feldman</a>: A Decidable Propositional Probabilistic Dynamic Logic. 298-309 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Feldman83">BibTeX</a></font> <li><a name="HalpernR83" href="../../indices/a-tree/h/Halpern:Joseph_Y=.html">Joseph Y. Halpern</a>, <a href="../../indices/a-tree/r/Rabin:Michael_O=.html">Michael O. Rabin</a>: A Logic to Reason about Likelihood. 310-319 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HalpernR83">BibTeX</a></font> <li><a name="Olderog83" href="../../indices/a-tree/o/Olderog:Ernst=R=uuml=diger.html">Ernst-Rüdiger Olderog</a>: A Characterization of Hoare's Logic for Programs with Pascal-like Procedures. 320-329 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Olderog83">BibTeX</a></font> <li><a name="DymondT83" href="../../indices/a-tree/d/Dymond:Patrick_W=.html">Patrick W. Dymond</a>, <a href="../../indices/a-tree/t/Tompa:Martin.html">Martin Tompa</a>: Speedups of Deterministic Machines by Synchronous Parallel Machines. 336-343 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DymondT83">BibTeX</a></font> <li><a name="Immerman83" href="../../indices/a-tree/i/Immerman:Neil.html">Neil Immerman</a>: Languages Which Capture Complexity Classes (Preliminary Report). 347-354 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Immerman83">BibTeX</a></font> <li><a name="Myers83" href="../../indices/a-tree/m/Myers:Dale.html">Dale Myers</a>: The Random Access Hierarchy (Preliminary Report). 355-364 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Myers83">BibTeX</a></font> <li><a name="Engelfriet83" href="../../indices/a-tree/e/Engelfriet:Joost.html">Joost Engelfriet</a>: Iterated Pushdown Automata and Complexity Classes. 365-373 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Engelfriet83">BibTeX</a></font> <li><a name="Iwama83" href="../../indices/a-tree/i/Iwama:Kazuo.html">Kazuo Iwama</a>: Unique Decomposability of Shuffled Strings: A Formal Treatment of Asynchronous Time-Multiplexed Communication. 374-381 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Iwama83">BibTeX</a></font> <li><a name="HartmanisSI83" href="../../indices/a-tree/h/Hartmanis:Juris.html">Juris Hartmanis</a>, <a href="../../indices/a-tree/s/Sewelson:Vivian.html">Vivian Sewelson</a>, <a href="../../indices/a-tree/i/Immerman:Neil.html">Neil Immerman</a>: Sparse Sets in NP-P: EXPTIME versus NEXPTIME. 382-391 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HartmanisSI83">BibTeX</a></font> <li><a name="Young83" href="../../indices/a-tree/y/Young:Paul.html">Paul Young</a>: Some Structural Properties of Polynomial Reducibilities and Sets in NP. 392-401 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Young83">BibTeX</a></font> <li><a name="Adleman83" href="../../indices/a-tree/a/Adleman:Leonard_M=.html">Leonard M. Adleman</a>: On Breaking Generalized Knapsack Public Key Cryptosystems (Abstract). 402-412 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Adleman83">BibTeX</a></font> <li><a name="LongW83" href="../../indices/a-tree/l/Long:Douglas_L=.html">Douglas L. Long</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: How Discreet is the Discrete Log? 413-420 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LongW83">BibTeX</a></font> <li><a name="Ben-OrCS83" href="../../indices/a-tree/b/Ben=Or:Michael.html">Michael Ben-Or</a>, <a href="../../indices/a-tree/c/Chor:Benny.html">Benny Chor</a>, <a href="../../indices/a-tree/s/Shamir:Adi.html">Adi Shamir</a>: On the Cryptographic Security of Single RSA Bits. 421-430 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Ben-OrCS83">BibTeX</a></font> <li><a name="GoldwasserMY83" href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/m/Micali:Silvio.html">Silvio Micali</a>, <a href="../../indices/a-tree/y/Yao:Andrew_Chi=Chih.html">Andrew Chi-Chih Yao</a>: Strong Signature Schemes. 431-439 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldwasserMY83">BibTeX</a></font> <li><a name="Blum83" href="../../indices/a-tree/b/Blum:Manuel.html">Manuel Blum</a>: How to Exchange (Secret) Keys (Extended Abstract). 440-447 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Blum83">BibTeX</a></font> <li><a name="Gabow83" href="../../indices/a-tree/g/Gabow:Harold_N=.html">Harold N. Gabow</a>: An Efficient Reduction Technique for Degree-Constrained Subgraph and Bidirected Network Flow Problems. 448-456 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Gabow83">BibTeX</a></font> <li><a name="Spinrad83" href="../../indices/a-tree/s/Spinrad:Jeremy.html">Jeremy Spinrad</a>: Transitive Orientation in O(n²) Time. 457-466 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Spinrad83">BibTeX</a></font> <li><a name="Turner83" href="../../indices/a-tree/t/Turner:Jonathan_S=.html">Jonathan S. Turner</a>: Probabilistic Analysis of Bandwidth Minimization Algorithms. 467-476 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Turner83">BibTeX</a></font> <li><a name="BakerBL83" href="../../indices/a-tree/b/Baker:Brenda_S=.html">Brenda S. Baker</a>, <a href="../../indices/a-tree/b/Bhatt:Sandeep_N=.html">Sandeep N. Bhatt</a>, <a href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>: An Approximation Algorithm for Manhattan Routing (Extended Abstract). 477-486 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BakerBL83">BibTeX</a></font> </ul><p><div class="footer"> <a href="../../index.html">Home</a> | <a href="../indexa.html">Conferences</a> | <a href="../../journals/index.html">Journals</a> | <a href="../../series/index.html">Series</a> | <a href="../../about/faq.html">FAQ</a> — Search: <a href="http://dblp.l3s.de">Faceted</a> | <a href="http://dblp.mpi-inf.mpg.de/dblp-mirror/index.php">Complete</a> | <a href="../../indices/a-tree/index.html">Author</a></div> <small><a href="../../copyright.html">Copyright ©</a> Sat May 16 23:43:10 2009 by <a href="http://www.informatik.uni-trier.de/~ley/addr.html">Michael Ley</a> (<a href="mailto:ley@uni-trier.de">ley@uni-trier.de</a>)</small></p></body></html>
SIGMOD News
