stoc85.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>STOC 1985</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>17. <a href="index.html">STOC</a> 1985</h1> Proceedings of the 17th Annual ACM Symposium on Theory of Computing, May 6-8, 1985, Providence, Rhode Island, USA. ACM 1985 <ul> <li><a name="Luby85" href="../../indices/a-tree/l/Luby:Michael.html">Michael Luby</a>: A Simple Parallel Algorithm for the Maximal Independent Set Problem. 1-10 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Luby85">BibTeX</a></font> <li><a name="VaziraniV85" href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>, <a href="../../indices/a-tree/v/Vazirani:Vijay_V=.html">Vijay V. Vazirani</a>: The Two-Processor Scheduling Problem is in R-NC. 11-21 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/VaziraniV85">BibTeX</a></font> <li><a name="KarpUW85" href="../../indices/a-tree/k/Karp:Richard_M=.html">Richard M. Karp</a>, <a href="../../indices/a-tree/u/Upfal:Eli.html">Eli Upfal</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: Constructing a Perfect Matching is in Random NC. 22-32 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KarpUW85">BibTeX</a></font> <li><a name="Anderson85" href="../../indices/a-tree/a/Anderson:Richard.html">Richard Anderson</a>: A Parallel Algorithm for the Maximal Path Problem. 33-37 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Anderson85">BibTeX</a></font> <li><a name="FichT85" href="../../indices/a-tree/f/Fich:Faith_E=.html">Faith E. Fich</a>, <a href="../../indices/a-tree/t/Tompa:Martin.html">Martin Tompa</a>: The Parallel Complexity of Exponentiating Polynomials over Finite Fields. 38-47 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FichT85">BibTeX</a></font> <li><a name="FichHRW85" href="../../indices/a-tree/f/Fich:Faith_E=.html">Faith E. Fich</a>, <a href="../../indices/a-tree/h/Heide:Friedhelm_Meyer_auf_der.html">Friedhelm Meyer auf der Heide</a>, <a href="../../indices/a-tree/r/Ragde:Prabhakar.html">Prabhakar Ragde</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation. 48-58 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FichHRW85">BibTeX</a></font> <li><a name="Aggarwal85" href="../../indices/a-tree/a/Aggarwal:Alok.html">Alok Aggarwal</a>: Tradeoffs for VLSI Models with Subpolynomial Delay. 59-68 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Aggarwal85">BibTeX</a></font> <li><a name="LeisersonM85" href="../../indices/a-tree/l/Leiserson:Charles_E=.html">Charles E. Leiserson</a>, <a href="../../indices/a-tree/m/Maley:F=_Miller.html">F. Miller Maley</a>: Algorithms for Routing and Testing Routability of Planar VLSI Layouts. 69-78 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LeisersonM85">BibTeX</a></font> <li><a name="RaghavanT85" href="../../indices/a-tree/r/Raghavan:Prabhakar.html">Prabhakar Raghavan</a>, <a href="../../indices/a-tree/t/Thompson:Clark_D=.html">Clark D. Thompson</a>: Provably Good Routing in Graphs: Regular Arrays. 79-87 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/RaghavanT85">BibTeX</a></font> <li><a name="JimboM85" href="../../indices/a-tree/j/Jimbo:Shuji.html">Shuji Jimbo</a>, <a href="../../indices/a-tree/m/Maruoka:Akira.html">Akira Maruoka</a>: Expanders Obtained from Affine Transformations (Preliminary Version). 88-97 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/JimboM85">BibTeX</a></font> <li><a name="Alon85" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>: Expanders, Sorting in Rounds and Superconcentrators of Limited Depth. 98-102 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Alon85">BibTeX</a></font> <li><a name="Wilber85" href="../../indices/a-tree/w/Wilber:Robert_E=.html">Robert E. Wilber</a>: White Pebbles Help. 103-112 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Wilber85">BibTeX</a></font> <li><a name="BakerFG85" href="../../indices/a-tree/b/Baker:Brenda_S=.html">Brenda S. Baker</a>, <a href="../../indices/a-tree/f/Fortune:Steven.html">Steven Fortune</a>, <a href="../../indices/a-tree/g/Grosse:Eric.html">Eric Grosse</a>: Stable Prehension with Three Fingers. 114-120 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BakerFG85">BibTeX</a></font> <li><a name="Huang85" href="../../indices/a-tree/h/Huang:Ming=Deh_A=.html">Ming-Deh A. Huang</a>: Riemann Hypothesis and Finding Roots over Finite Fields. 121-130 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Huang85">BibTeX</a></font> <li><a name="Kaltofen85" href="../../indices/a-tree/k/Kaltofen:Erich.html">Erich Kaltofen</a>: Computing with Polynomials Given by Straight-Line Programs I: Greatest Common Divisors. 131-142 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Kaltofen85">BibTeX</a></font> <li><a name="PanR85" href="../../indices/a-tree/p/Pan:Victor_Y=.html">Victor Y. Pan</a>, <a href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>: Efficient Parallel Solution of Linear Systems. 143-152 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/PanR85">BibTeX</a></font> <li><a name="FriedlR85" href="../../indices/a-tree/f/Friedl:Katalin.html">Katalin Friedl</a>, <a href="../../indices/a-tree/r/R=oacute=nyai:Lajos.html">Lajos Rónyai</a>: Polynomial Time Solutions of Some Problems in Computational Algebra. 153-162 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FriedlR85">BibTeX</a></font> <li><a name="YaoY85" href="../../indices/a-tree/y/Yao:Andrew_Chi=Chih.html">Andrew Chi-Chih Yao</a>, <a href="../../indices/a-tree/y/Yao:F=_Frances.html">F. Frances Yao</a>: A General Approach to d-Dimensional Geometric Queries (Extended Abstract). 163-168 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/YaoY85">BibTeX</a></font> <li><a name="Vaidya85" href="../../indices/a-tree/v/Vaidya:Pravin_M=.html">Pravin M. Vaidya</a>: Space-Time Tradeoffs for Orthogonal Range Queries (Extended Abstract). 169-174 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Vaidya85">BibTeX</a></font> <li><a name="Clarkson85" href="../../indices/a-tree/c/Clarkson:Kenneth_L=.html">Kenneth L. Clarkson</a>: A Probabilistic Algorithm for the Post Office Problem. 175-184 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Clarkson85">BibTeX</a></font> <li><a name="Harel85" href="../../indices/a-tree/h/Harel:Dov.html">Dov Harel</a>: A Linear Time Algorithm for Finding Dominators in Flow Graphs and Related Problems. 185-194 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Harel85">BibTeX</a></font> <li><a name="SuzukiNS85" href="../../indices/a-tree/s/Suzuki:Hitoshi.html">Hitoshi Suzuki</a>, <a href="../../indices/a-tree/n/Nishizeki:Takao.html">Takao Nishizeki</a>, <a href="../../indices/a-tree/s/Saito:Nobuji.html">Nobuji Saito</a>: Multicommodity Flows in Planar Undirected Graphs and Shortest Paths. 195-204 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/SuzukiNS85">BibTeX</a></font> <li><a name="Culberson85" href="../../indices/a-tree/c/Culberson:Joseph_C=.html">Joseph C. Culberson</a>: The Effect of Updates in Binary Search Trees. 205-212 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Culberson85">BibTeX</a></font> <li><a name="BentJ85" href="../../indices/a-tree/b/Bent:Samuel_W=.html">Samuel W. Bent</a>, <a href="../../indices/a-tree/j/John:John_W=.html">John W. John</a>: Finding the Median Requires 2n Comparisons. 213-216 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BentJ85">BibTeX</a></font> <li><a name="ChungHS85" href="../../indices/a-tree/c/Chung:Fan_R=_K=.html">Fan R. K. Chung</a>, <a href="../../indices/a-tree/h/Hajela:D=_J=.html">D. J. Hajela</a>, <a href="../../indices/a-tree/s/Seymour:Paul_D=.html">Paul D. Seymour</a>: Self-Organizing Sequential Search and Hilbert's Inequalities. 217-223 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChungHS85">BibTeX</a></font> <li><a name="BollobasS85" href="../../indices/a-tree/b/Bollob=aacute=s:B=eacute=la.html">Béla Bollobás</a>, <a href="../../indices/a-tree/s/Simon:Istv=aacute=n.html">István Simon</a>: On the Expected Behaviour of Disjoint Set Union Algorithms. 224-231 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BollobasS85">BibTeX</a></font> <li><a name="Peleg85" href="../../indices/a-tree/p/Peleg:David.html">David Peleg</a>: Concurrent Dynamic Logic (Extended Abstract). 232-239 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Peleg85">BibTeX</a></font> <li><a name="VardiS85" href="../../indices/a-tree/v/Vardi:Moshe_Y=.html">Moshe Y. Vardi</a>, <a href="../../indices/a-tree/s/Stockmeyer:Larry_J=.html">Larry J. Stockmeyer</a>: Improved Upper and Lower Bounds for Modal Logics of Programs: Preliminary Report. 240-251 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/VardiS85">BibTeX</a></font> <li><a name="BakkerMOZ85" href="../../indices/a-tree/b/Bakker:J=_W=_de.html">J. W. de Bakker</a>, <a href="../../indices/a-tree/m/Meyer:John=Jules_Ch=.html">John-Jules Ch. Meyer</a>, <a href="../../indices/a-tree/o/Olderog:Ernst=R=uuml=diger.html">Ernst-Rüdiger Olderog</a>, <a href="../../indices/a-tree/z/Zucker:Jeffery_I=.html">Jeffery I. Zucker</a>: Transition Systems, Infinitary Languages and the Semantics of Uniform Concurrency. 252-262 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BakkerMOZ85">BibTeX</a></font> <li><a name="BruceL85" href="../../indices/a-tree/b/Bruce:Kim_B=.html">Kim B. Bruce</a>, <a href="../../indices/a-tree/l/Longo:Giuseppe.html">Giuseppe Longo</a>: Provable Isomorphisms and Domain Equations in Models of Typed Languages (Preliminary Version). 263-272 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BruceL85">BibTeX</a></font> <li><a name="CosmadakisK85" href="../../indices/a-tree/c/Cosmadakis:Stavros_S=.html">Stavros S. Cosmadakis</a>, <a href="../../indices/a-tree/k/Kanellakis:Paris_C=.html">Paris C. Kanellakis</a>: Equational Theories and Database Constraints. 273-284 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CosmadakisK85">BibTeX</a></font> <li><a name="Buss85" href="../../indices/a-tree/b/Buss:Samuel_R=.html">Samuel R. Buss</a>: The Polynomial Hierarchy and Fragments of Bounded Arithmetic (Extended Abstract). 285-290 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Buss85">BibTeX</a></font> <li><a name="GoldwasserMR85" 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/r/Rackoff:Charles.html">Charles Rackoff</a>: The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). 291-304 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldwasserMR85">BibTeX</a></font> <li><a name="FaginV85" href="../../indices/a-tree/f/Fagin:Ronald.html">Ronald Fagin</a>, <a href="../../indices/a-tree/v/Vardi:Moshe_Y=.html">Moshe Y. Vardi</a>: An Internal Semantics for Modal Logic: Preliminary Report. 305-315 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FaginV85">BibTeX</a></font> <li><a name="Bracha85" href="../../indices/a-tree/b/Bracha:Gabriel.html">Gabriel Bracha</a>: An O(\mathop lg n) Expected Rounds Randomized Byzantine Generals Protocol. 316-326 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Bracha85">BibTeX</a></font> <li><a name="Feldman85" href="../../indices/a-tree/f/Feldman:Paul.html">Paul Feldman</a>: Fault Tolerance of Minimal Path Routings in a Network. 327-334 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Feldman85">BibTeX</a></font> <li><a name="CoanDDS85" href="../../indices/a-tree/c/Coan:Brian_A=.html">Brian A. Coan</a>, <a 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/s/Stockmeyer:Larry_J=.html">Larry J. Stockmeyer</a>: The Distributed Firing Squad Problem (Preliminary Version). 335-345 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CoanDDS85">BibTeX</a></font> <li><a name="HalpernMM85" href="../../indices/a-tree/h/Halpern:Joseph_Y=.html">Joseph Y. Halpern</a>, <a href="../../indices/a-tree/m/Megiddo:Nimrod.html">Nimrod Megiddo</a>, <a href="../../indices/a-tree/m/Munshi:Ashfaq_A=.html">Ashfaq A. Munshi</a>: Optimal Precision in the Presence of Uncertainty (Preliminary Version). 346-355 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HalpernMM85">BibTeX</a></font> <li><a name="HastadS85" href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>, <a href="../../indices/a-tree/s/Shamir:Adi.html">Adi Shamir</a>: The Cryptographic Security of Truncated Linearly Related Variables. 356-362 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HastadS85">BibTeX</a></font> <li><a name="Levin85" href="../../indices/a-tree/l/Levin:Leonid_A=.html">Leonid A. Levin</a>: One-Way Functions and Pseudorandom Generators. 363-365 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Levin85">BibTeX</a></font> <li><a name="Vazirani85" href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>: Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (Extended Abstract). 366-378 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Vazirani85">BibTeX</a></font> <li><a name="GoodmanGMM85" href="../../indices/a-tree/g/Goodman:Jonathan.html">Jonathan Goodman</a>, <a href="../../indices/a-tree/g/Greenberg:Albert_G=.html">Albert G. Greenberg</a>, <a href="../../indices/a-tree/m/Madras:Neal.html">Neal Madras</a>, <a href="../../indices/a-tree/m/March:Peter.html">Peter March</a>: On the Stability of the Ethernet. 379-387 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoodmanGMM85">BibTeX</a></font> <li><a name="GacsR85" href="../../indices/a-tree/g/G=aacute=cs:P=eacute=ter.html">Péter Gács</a>, <a href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>: A Simple Three-Dimensional Real-Time Reliable Cellular Array. 388-395 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GacsR85">BibTeX</a></font> <li><a name="Lubiw85" href="../../indices/a-tree/l/Lubiw:Anna.html">Anna Lubiw</a>: Doubly Lexical Orderings of Matrices. 396-404 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Lubiw85">BibTeX</a></font> <li><a name="Huynh85" href="../../indices/a-tree/h/Huynh:Dung_T=.html">Dung T. Huynh</a>: The Complexity of the Equivalence Problem for Commutative Semigroups and Symmetric Vector Addition Systems. 405-412 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Huynh85">BibTeX</a></font> <li><a name="Heide85" href="../../indices/a-tree/h/Heide:Friedhelm_Meyer_auf_der.html">Friedhelm Meyer auf der Heide</a>: Fast Algorithms for N-Dimensional Restrictions of Hard Problems. 413-420 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Heide85">BibTeX</a></font> <li><a name="Babai85" href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>: Trading Group Theory for Randomness. 421-429 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Babai85">BibTeX</a></font> <li><a name="BollobasFF85" href="../../indices/a-tree/b/Bollob=aacute=s:B=eacute=la.html">Béla Bollobás</a>, <a href="../../indices/a-tree/f/Fenner:Trevor_I=.html">Trevor I. Fenner</a>, <a href="../../indices/a-tree/f/Frieze:Alan_M=.html">Alan M. Frieze</a>: An Algorithm for Finding Hamilton Cycles in a Random Graph. 430-439 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BollobasFF85">BibTeX</a></font> <li><a name="GoldbergS85" href="../../indices/a-tree/g/Goldberg:Andrew_V=.html">Andrew V. Goldberg</a>, <a href="../../indices/a-tree/s/Sipser:Michael.html">Michael Sipser</a>: Compression and Ranking. 440-448 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldbergS85">BibTeX</a></font> <li><a name="CarterSW85" href="../../indices/a-tree/c/Carter:Larry.html">Larry Carter</a>, <a href="../../indices/a-tree/s/Stockmeyer:Larry_J=.html">Larry J. Stockmeyer</a>, <a href="../../indices/a-tree/w/Wegman:Mark_N=.html">Mark N. Wegman</a>: The Complexity of Backtrack Searches (Preliminary Version). 449-457 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CarterSW85">BibTeX</a></font> <li><a name="ValiantV85" href="../../indices/a-tree/v/Valiant:Leslie_G=.html">Leslie G. Valiant</a>, <a href="../../indices/a-tree/v/Vazirani:Vijay_V=.html">Vijay V. Vazirani</a>: NP Is as Easy as Detecting Unique Solutions. 458-463 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ValiantV85">BibTeX</a></font> <li><a name="AharoniEL85" href="../../indices/a-tree/a/Aharoni:Ron.html">Ron Aharoni</a>, <a href="../../indices/a-tree/e/Erd=ouml=s:Paul.html">Paul Erdös</a>, <a href="../../indices/a-tree/l/Linial:Nathan.html">Nathan Linial</a>: Dual Integer Linear Programs and the Relationship between their Optima. 476-483 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AharoniEL85">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
