stoc82.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>STOC 1982</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>14. <a href="index.html">STOC</a> 1982</h1> Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA. ACM 1982 <ul> <li><a name="DurisG82" href="../../indices/a-tree/d/Duris:Pavol.html">Pavol Duris</a>, <a href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>: Two Tapes are Better than One for Nondeterministic Machines. 1-7 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DurisG82">BibTeX</a></font> <li><a name="Furer82" href="../../indices/a-tree/f/F=uuml=rer:Martin.html">Martin Fürer</a>: The Tight Deterministic Time Hierarchy. 8-16 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Furer82">BibTeX</a></font> <li><a name="Pippenger82" href="../../indices/a-tree/p/Pippenger:Nicholas.html">Nicholas Pippenger</a>: Probabilistic Simulations (Preliminary Version). 17-26 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Pippenger82">BibTeX</a></font> <li><a name="Vitanyi82" href="../../indices/a-tree/v/Vit=aacute=nyi:Paul_M=_B=.html">Paul M. B. Vitányi</a>: Real-Time Simulation of Multicounters by Oblivious One-Tape Turing Machines. 27-36 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Vitanyi82">BibTeX</a></font> <li><a name="InoueTT82" href="../../indices/a-tree/i/Inoue:Katsushi.html">Katsushi Inoue</a>, <a href="../../indices/a-tree/t/Takanami:Itsuo.html">Itsuo Takanami</a>, <a href="../../indices/a-tree/t/Taniguchi:Hiroshi.html">Hiroshi Taniguchi</a>: Two-Dimensional Alternating Turing Machines. 37-46 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/InoueTT82">BibTeX</a></font> <li><a name="NivatP82" href="../../indices/a-tree/n/Nivat:Maurice.html">Maurice Nivat</a>, <a href="../../indices/a-tree/p/Perrin:Dominique.html">Dominique Perrin</a>: Ensembles Reconnaissables de Mots Biinfinis. 47-59 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/NivatP82">BibTeX</a></font> <li><a name="GurevichH82" href="../../indices/a-tree/g/Gurevich:Yuri.html">Yuri Gurevich</a>, <a href="../../indices/a-tree/h/Harrington:Leo.html">Leo Harrington</a>: Trees, Automata, and Games. 60-65 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GurevichH82">BibTeX</a></font> <li><a name="Carter82" href="../../indices/a-tree/c/Carter:J=_Lawrence.html">J. Lawrence Carter</a>: The Theory of Signature Testing for VLSI. 66-76 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Carter82">BibTeX</a></font> <li><a name="BhattL82" href="../../indices/a-tree/b/Bhatt:Sandeep_N=.html">Sandeep N. Bhatt</a>, <a href="../../indices/a-tree/l/Leiserson:Charles_E=.html">Charles E. Leiserson</a>: How to Assemble Tree Machines (Extended Abstract). 77-84 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BhattL82">BibTeX</a></font> <li><a name="Leighton82" href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>: A Layout Strategy for VLSI which Is Provably Good (Extended Abstract). 85-98 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Leighton82">BibTeX</a></font> <li><a name="Kissin82" href="../../indices/a-tree/k/Kissin:Gloria.html">Gloria Kissin</a>: Measuring Energy Consumption in VLSI Circuits: a Foundation. 99-104 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Kissin82">BibTeX</a></font> <li><a name="RivestS82" href="../../indices/a-tree/r/Rivest:Ronald_L=.html">Ronald L. Rivest</a>, <a href="../../indices/a-tree/s/Shamir:Adi.html">Adi Shamir</a>: How to Reuse a ``Write-Once'' Memory (Preliminary Version). 105-113 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/RivestS82">BibTeX</a></font> <li><a name="Willard82" href="../../indices/a-tree/w/Willard:Dan_E=.html">Dan E. Willard</a>: Maintaining Dense Sequential Files in a Dynamic Environment (Extended Abstract). 114-121 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Willard82">BibTeX</a></font> <li><a name="Dietz82" href="../../indices/a-tree/d/Dietz:Paul_F=.html">Paul F. Dietz</a>: Maintaining Order in a Linked List. 122-127 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Dietz82">BibTeX</a></font> <li><a name="Yao82" href="../../indices/a-tree/y/Yao:Andrew_Chi=Chih.html">Andrew Chi-Chih Yao</a>: Space-Time Tradeoff for Answering Range Queries (Extended Abstract). 128-136 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Yao82">BibTeX</a></font> <li><a name="Vardi82" href="../../indices/a-tree/v/Vardi:Moshe_Y=.html">Moshe Y. Vardi</a>: The Complexity of Relational Query Languages (Extended Abstract). 137-146 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Vardi82">BibTeX</a></font> <li><a name="Immerman82" href="../../indices/a-tree/i/Immerman:Neil.html">Neil Immerman</a>: Relational Queries Computable in Polynomial Time (Extended Abstract). 147-152 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Immerman82">BibTeX</a></font> <li><a name="DeBakkerZ82" href="../../indices/a-tree/b/Bakker:J=_W=_de.html">J. W. de Bakker</a>, <a href="../../indices/a-tree/z/Zucker:Jeffery_I=.html">Jeffery I. Zucker</a>: Denotational Semantics of Concurrency. 153-158 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DeBakkerZ82">BibTeX</a></font> <li><a name="SistlaC82" href="../../indices/a-tree/s/Sistla:A=_Prasad.html">A. Prasad Sistla</a>, <a href="../../indices/a-tree/c/Clarke:Edmund_M=.html">Edmund M. Clarke</a>: The Complexity of Propositional Linear Temporal Logics. 159-168 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/SistlaC82">BibTeX</a></font> <li><a name="EmersonH82" href="../../indices/a-tree/e/Emerson:E=_Allen.html">E. Allen Emerson</a>, <a href="../../indices/a-tree/h/Halpern:Joseph_Y=.html">Joseph Y. Halpern</a>: Decision Procedures and Expressiveness in the Temporal Logic of Branching Time. 169-180 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/EmersonH82">BibTeX</a></font> <li><a name="FeldmanH82" href="../../indices/a-tree/f/Feldman:Yishai_A=.html">Yishai A. Feldman</a>, <a href="../../indices/a-tree/h/Harel:David.html">David Harel</a>: A Probabilistic Dynamic Logic. 181-195 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FeldmanH82">BibTeX</a></font> <li><a name="PapadimitriouS82" href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>, <a href="../../indices/a-tree/s/Sipser:Michael.html">Michael Sipser</a>: Communication Complexity. 196-200 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/PapadimitriouS82">BibTeX</a></font> <li><a name="Reif82" href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>: Symmetric Complementation. 201-214 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Reif82">BibTeX</a></font> <li><a name="RuzzoST82" href="../../indices/a-tree/r/Ruzzo:Walter_L=.html">Walter L. Ruzzo</a>, <a href="../../indices/a-tree/s/Simon:Janos.html">Janos Simon</a>, <a href="../../indices/a-tree/t/Tompa:Martin.html">Martin Tompa</a>: Space-Bounded Hierarchies and Probabilistic Computations. 215-223 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/RuzzoST82">BibTeX</a></font> <li><a name="Kurtz82" href="../../indices/a-tree/k/Kurtz:Stuart_A=.html">Stuart A. Kurtz</a>: On the Random Oracle Hypothesis. 224-230 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Kurtz82">BibTeX</a></font> <li><a name="CookD82" href="../../indices/a-tree/c/Cook:Stephen.html">Stephen Cook</a>, <a href="../../indices/a-tree/d/Dwork:Cynthia.html">Cynthia Dwork</a>: Bounds on the Time for Parallel RAM's to Compute Simple Functions. 231-233 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CookD82">BibTeX</a></font> <li><a name="ManberT82" href="../../indices/a-tree/m/Manber:Udi.html">Udi Manber</a>, <a href="../../indices/a-tree/t/Tompa:Martin.html">Martin Tompa</a>: Probabilistic, Nondeterministic, and Alternating Decision Trees. 234-244 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ManberT82">BibTeX</a></font> <li><a name="AsanoH82" href="../../indices/a-tree/a/Asano:Takao.html">Takao Asano</a>, <a href="../../indices/a-tree/h/Hirata:Tomio.html">Tomio Hirata</a>: Edge-Deletion and Edge-Contraction Problems. 245-254 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AsanoH82">BibTeX</a></font> <li><a name="PapadimitriouY82" href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>, <a href="../../indices/a-tree/y/Yannakakis:Mihalis.html">Mihalis Yannakakis</a>: The Complexity of Facets (and Some Facets of Complexity). 255-260 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/PapadimitriouY82">BibTeX</a></font> <li><a name="Kaltofen82" href="../../indices/a-tree/k/Kaltofen:Erich.html">Erich Kaltofen</a>: A Polynomial Reduction from Multivariate to Bivariate Integral Polynomial Factorization. 261-266 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Kaltofen82">BibTeX</a></font> <li><a name="Kosaraju82" href="../../indices/a-tree/k/Kosaraju:S=_Rao.html">S. Rao Kosaraju</a>: Decidability of Reachability in Vector Addition Systems (Preliminary Version). 267-281 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Kosaraju82">BibTeX</a></font> <li><a name="BoyceDDG82" href="../../indices/a-tree/b/Boyce:James_E=.html">James E. Boyce</a>, <a href="../../indices/a-tree/d/Dobkin:David_P=.html">David P. Dobkin</a>, <a href="../../indices/a-tree/d/Drysdale_III:Robert_L=_=Scot=.html">Robert L. (Scot) Drysdale III</a>, <a href="../../indices/a-tree/g/Guibas:Leonidas_J=.html">Leonidas J. Guibas</a>: Finding Extremal Polygons. 282-289 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BoyceDDG82">BibTeX</a></font> <li><a name="Bach82" href="../../indices/a-tree/b/Bach:Eric.html">Eric Bach</a>: Fast Algorithms under the Extended Riemann Hypothesis: A Concrete Estimate. 290-295 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Bach82">BibTeX</a></font> <li><a name="HongS82" href="../../indices/a-tree/h/Hong:Zhu.html">Zhu Hong</a>, <a href="../../indices/a-tree/s/Sedgewick:Robert.html">Robert Sedgewick</a>: Notes on Merging Networks (Preliminary Version). 296-302 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HongS82">BibTeX</a></font> <li><a name="Bar-YehudaE82" href="../../indices/a-tree/b/Bar=Yehuda:Reuven.html">Reuven Bar-Yehuda</a>, <a href="../../indices/a-tree/e/Even:Shimon.html">Shimon Even</a>: On Approximating a Vertex Cover for Planar Graphs. 303-309 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Bar-YehudaE82">BibTeX</a></font> <li><a name="BabaiGM82" href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>, <a href="../../indices/a-tree/g/Grigoryev:D=_Yu=.html">D. Yu. Grigoryev</a>, <a href="../../indices/a-tree/m/Mount:David_M=.html">David M. Mount</a>: Isomorphism of Graphs with Bounded Eigenvalue Multiplicity. 310-324 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BabaiGM82">BibTeX</a></font> <li><a name="Wigderson82" href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: A New Approximate Graph Coloring Algorithm. 325-329 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Wigderson82">BibTeX</a></font> <li><a name="MehlhornS82" href="../../indices/a-tree/m/Mehlhorn:Kurt.html">Kurt Mehlhorn</a>, <a href="../../indices/a-tree/s/Schmidt:Erik_Meineche.html">Erik Meineche Schmidt</a>: Las Vegas Is better than Determinism in VLSI and Distributed Computing (Extended Abstract). 330-337 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MehlhornS82">BibTeX</a></font> <li><a name="BorodinH82" href="../../indices/a-tree/b/Borodin:Allan.html">Allan Borodin</a>, <a href="../../indices/a-tree/h/Hopcroft:John_E=.html">John E. Hopcroft</a>: Routing, Merging and Sorting on Parallel Models of Computation (Extended Abstract). 338-344 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BorodinH82">BibTeX</a></font> <li><a name="AtallahK82" href="../../indices/a-tree/a/Atallah:Mikhail_J=.html">Mikhail J. Atallah</a>, <a href="../../indices/a-tree/k/Kosaraju:S=_Rao.html">S. Rao Kosaraju</a>: Graph Problems on a Mesh-Connected Processor Array (Preliminary Version). 345-353 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AtallahK82">BibTeX</a></font> <li><a name="Greenberg82" href="../../indices/a-tree/g/Greenberg:Albert_G=.html">Albert G. Greenberg</a>: On the Time Complexity of Broadcast Communication Schemes (Preliminary Version). 354-364 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Greenberg82">BibTeX</a></font> <li><a name="GoldwasserM82" href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/m/Micali:Silvio.html">Silvio Micali</a>: Probabilistic Encryption and How to Play Mental Poker Keeping Secret All Partial Information. 365-377 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldwasserM82">BibTeX</a></font> <li><a name="PachlKR82" href="../../indices/a-tree/p/Pachl:Jan_K=.html">Jan K. Pachl</a>, <a href="../../indices/a-tree/k/Korach:Ephraim.html">Ephraim Korach</a>, <a href="../../indices/a-tree/r/Rotem:Doron.html">Doron Rotem</a>: A Technique for Proving Lower Bounds for Distributed Maximum-Finding Algorithms. 378-382 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/PachlKR82">BibTeX</a></font> <li><a name="DeMilloLM82" href="../../indices/a-tree/d/DeMillo:Richard_A=.html">Richard A. DeMillo</a>, <a href="../../indices/a-tree/l/Lynch:Nancy_A=.html">Nancy A. Lynch</a>, <a href="../../indices/a-tree/m/Merritt:Michael.html">Michael Merritt</a>: Cryptographic Protocols. 383-400 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DeMilloLM82">BibTeX</a></font> <li><a name="DolevS82" href="../../indices/a-tree/d/Dolev:Danny.html">Danny Dolev</a>, <a href="../../indices/a-tree/s/Strong:H=_Raymond.html">H. Raymond Strong</a>: Polynomial Algorithms for Multiple Processor Agreement. 401-407 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DolevS82">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
