stoc87.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>STOC 1987</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>19. <a href="index.html">STOC</a> 1987</h1> Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA. ACM 1987 <ul> <li><a name="CoppersmithW87" href="../../indices/a-tree/c/Coppersmith:Don.html">Don Coppersmith</a>, <a href="../../indices/a-tree/w/Winograd:Shmuel.html">Shmuel Winograd</a>: Matrix Multiplication via Arithmetic Progressions. 1-6 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CoppersmithW87">BibTeX</a></font> <li><a name="GoldbergT87" href="../../indices/a-tree/g/Goldberg:Andrew_V=.html">Andrew V. Goldberg</a>, <a href="../../indices/a-tree/t/Tarjan:Robert_Endre.html">Robert Endre Tarjan</a>: Solving Minimum-Cost Flow Problems by Successive Approximation. 7-18 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldbergT87">BibTeX</a></font> <li><a name="Frederickson87" href="../../indices/a-tree/f/Frederickson:Greg_N=.html">Greg N. Frederickson</a>: A New Approach to All Pairs Shortest Paths in Planar Graphs (Extended Abstract). 19-28 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Frederickson87">BibTeX</a></font> <li><a name="Vaidya87" href="../../indices/a-tree/v/Vaidya:Pravin_M=.html">Pravin M. Vaidya</a>: An Algorithm for Linear Programming which Requires O(((m+n)n^2 + (m+n)^1.5 n)L) Arithmetic Operations. 29-38 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Vaidya87">BibTeX</a></font> <li><a name="AggarwalGSS87" href="../../indices/a-tree/a/Aggarwal:Alok.html">Alok Aggarwal</a>, <a href="../../indices/a-tree/g/Guibas:Leonidas_J=.html">Leonidas J. Guibas</a>, <a href="../../indices/a-tree/s/Saxe:James_B=.html">James B. Saxe</a>, <a href="../../indices/a-tree/s/Shor:Peter_W=.html">Peter W. Shor</a>: A Linear Time Algorithm for Computing the Voronoi Diagram of a Convex Polygon. 39-45 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AggarwalGSS87">BibTeX</a></font> <li><a name="IwanoS87" href="../../indices/a-tree/i/Iwano:Kazuo.html">Kazuo Iwano</a>, <a href="../../indices/a-tree/s/Steiglitz:Kenneth.html">Kenneth Steiglitz</a>: Testing for Cycles in Infinite Graphs with Periodic Structure (Extended Abstract). 46-55 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/IwanoS87">BibTeX</a></font> <li><a name="Clarkson87" href="../../indices/a-tree/c/Clarkson:Kenneth_L=.html">Kenneth L. Clarkson</a>: Approximation Algorithms for Shortest Path Motion Planning (Extended Abstract). 56-65 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Clarkson87">BibTeX</a></font> <li><a name="ChazelleEG87" href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>, <a href="../../indices/a-tree/e/Edelsbrunner:Herbert.html">Herbert Edelsbrunner</a>, <a href="../../indices/a-tree/g/Guibas:Leonidas_J=.html">Leonidas J. Guibas</a>: The Complexity of Cutting Convex Polytopes. 66-76 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChazelleEG87">BibTeX</a></font> <li><a name="Smolensky87" href="../../indices/a-tree/s/Smolensky:Roman.html">Roman Smolensky</a>: Algebraic Methods in the Theory of Lower Bounds for Boolean Circuit Complexity. 77-82 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Smolensky87">BibTeX</a></font> <li><a name="BeameH87" href="../../indices/a-tree/b/Beame:Paul.html">Paul Beame</a>, <a href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>: Optimal Bounds for Decision Problems on the CRCW PRAM. 83-93 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BeameH87">BibTeX</a></font> <li><a name="MaassSS87" href="../../indices/a-tree/m/Maass:Wolfgang.html">Wolfgang Maass</a>, <a href="../../indices/a-tree/s/Schnitger:Georg.html">Georg Schnitger</a>, <a href="../../indices/a-tree/s/Szemer=eacute=di:Endre.html">Endre Szemerédi</a>: Two Tapes Are Better than One for Off-Line Turing Machines. 94-100 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MaassSS87">BibTeX</a></font> <li><a name="BarringtonT87" href="../../indices/a-tree/b/Barrington:David_A=_Mix.html">David A. Mix Barrington</a>, <a href="../../indices/a-tree/t/Th=eacute=rien:Denis.html">Denis Thérien</a>: Finite Monoids and the Fine Structure of NC¹. 101-109 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BarringtonT87">BibTeX</a></font> <li><a name="Hemachandra87" href="../../indices/a-tree/h/Hemachandra:Lane_A=.html">Lane A. Hemachandra</a>: The Strong Exponential Hierarchy Collapses. 110-122 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Hemachandra87">BibTeX</a></font> <li><a name="Buss87" href="../../indices/a-tree/b/Buss:Samuel_R=.html">Samuel R. Buss</a>: The Boolean Formula Value Problem Is in ALOGTIME. 123-131 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Buss87">BibTeX</a></font> <li><a name="AjtaiKS87" 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>: Deterministic Simulation in LOGSPACE. 132-140 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AjtaiKS87">BibTeX</a></font> <li><a name="Venkateswaran87" href="../../indices/a-tree/v/Venkateswaran:H=.html">H. Venkateswaran</a>: Properties that Characterize LOGCFL. 141-150 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Venkateswaran87">BibTeX</a></font> <li><a name="Allender87" href="../../indices/a-tree/a/Allender:Eric.html">Eric Allender</a>: Some Consequences of the Existence of Pseudorandom Generators. 151-159 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Allender87">BibTeX</a></font> <li><a name="Vazirani87" href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>: Efficiency Considerations in Using Semi-random Sources (Extended Abstract). 160-168 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Vazirani87">BibTeX</a></font> <li><a name="LichtensteinLS87" href="../../indices/a-tree/l/Lichtenstein:David.html">David Lichtenstein</a>, <a href="../../indices/a-tree/l/Linial:Nathan.html">Nathan Linial</a>, <a href="../../indices/a-tree/s/Saks:Michael_E=.html">Michael E. Saks</a>: Imperfect Random Sources and Discrete Controlled Processes. 169-177 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LichtensteinLS87">BibTeX</a></font> <li><a name="Furer87" href="../../indices/a-tree/f/F=uuml=rer:Martin.html">Martin Fürer</a>: The Power of Randomness for Communication Complexity (Preliminary Version). 178-181 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Furer87">BibTeX</a></font> <li><a name="Goldreich87" href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>: Towards a Theory of Software Protection and Simulation by Oblivious RAMs. 182-194 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Goldreich87">BibTeX</a></font> <li><a name="AbadiFK87" href="../../indices/a-tree/a/Abadi:Mart=iacute=n.html">Martín Abadi</a>, <a href="../../indices/a-tree/f/Feigenbaum:Joan.html">Joan Feigenbaum</a>, <a href="../../indices/a-tree/k/Kilian:Joe.html">Joe Kilian</a>: On Hiding Information from an Oracle (Extended Abstract). 195-203 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AbadiFK87">BibTeX</a></font> <li><a name="Fortnow87" href="../../indices/a-tree/f/Fortnow:Lance.html">Lance Fortnow</a>: The Complexity of Perfect Zero-Knowledge (Extended Abstract). 204-209 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Fortnow87">BibTeX</a></font> <li><a name="FeigeFS87" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>, <a href="../../indices/a-tree/f/Fiat:Amos.html">Amos Fiat</a>, <a href="../../indices/a-tree/s/Shamir:Adi.html">Adi Shamir</a>: Zero Knowledge Proofs of Identity. 210-217 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FeigeFS87">BibTeX</a></font> <li><a name="GoldreichMW87" href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/m/Micali:Silvio.html">Silvio Micali</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority. 218-229 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldreichMW87">BibTeX</a></font> <li><a name="Awerbuch87" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>: Optimal Distributed Algorithms for Minimum Weight Spanning Tree, Counting, Leader Election and Related Problems (Detailed Summary). 230-240 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Awerbuch87">BibTeX</a></font> <li><a name="HastadLR87" href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>, <a href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/r/Rogoff:Brian.html">Brian Rogoff</a>: Analysis of Backoff Protocols for Multiple Access Channels (Extended Abstract). 241-253 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HastadLR87">BibTeX</a></font> <li><a name="MillerT87" href="../../indices/a-tree/m/Miller:Gary_L=.html">Gary L. Miller</a>, <a href="../../indices/a-tree/t/Teng:Shang=Hua.html">Shang-Hua Teng</a>: Dynamic Parallel Complexity of Computational Circuits. 254-263 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MillerT87">BibTeX</a></font> <li><a name="PelegU87" href="../../indices/a-tree/p/Peleg:David.html">David Peleg</a>, <a href="../../indices/a-tree/u/Upfal:Eli.html">Eli Upfal</a>: Constructing Disjoint Paths on Expander Graphs (Extended Abstract). 264-273 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/PelegU87">BibTeX</a></font> <li><a name="HastadLN87" href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>, <a href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/n/Newman:Mark.html">Mark Newman</a>: Reconfiguring a Hypercube in the Presence of Faults (Extended Abstract). 274-284 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HastadLN87">BibTeX</a></font> <li><a name="KearnsLPV87" href="../../indices/a-tree/k/Kearns:Michael_J=.html">Michael J. Kearns</a>, <a href="../../indices/a-tree/l/Li:Ming.html">Ming Li</a>, <a href="../../indices/a-tree/p/Pitt:Leonard.html">Leonard Pitt</a>, <a href="../../indices/a-tree/v/Valiant:Leslie_G=.html">Leslie G. Valiant</a>: On the Learnability of Boolean Formulae. 285-295 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KearnsLPV87">BibTeX</a></font> <li><a name="Natarajan87" href="../../indices/a-tree/n/Natarajan:B=_K=.html">B. K. Natarajan</a>: On Learning Boolean Functions. 296-304 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Natarajan87">BibTeX</a></font> <li><a name="AggarwalACS87" href="../../indices/a-tree/a/Aggarwal:Alok.html">Alok Aggarwal</a>, <a href="../../indices/a-tree/a/Alpern:Bowen.html">Bowen Alpern</a>, <a href="../../indices/a-tree/c/Chandra:Ashok_K=.html">Ashok K. Chandra</a>, <a href="../../indices/a-tree/s/Snir:Marc.html">Marc Snir</a>: A Model for Hierarchical Memory. 305-314 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AggarwalACS87">BibTeX</a></font> <li><a name="GoldbergPS87" href="../../indices/a-tree/g/Goldberg:Andrew_V=.html">Andrew V. Goldberg</a>, <a href="../../indices/a-tree/p/Plotkin:Serge_A=.html">Serge A. Plotkin</a>, <a href="../../indices/a-tree/s/Shannon:Gregory_E=.html">Gregory E. Shannon</a>: Parallel Symmetry-Breaking in Sparse Graphs. 315-324 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldbergPS87">BibTeX</a></font> <li><a name="AggarwalA87" href="../../indices/a-tree/a/Aggarwal:Alok.html">Alok Aggarwal</a>, <a href="../../indices/a-tree/a/Anderson:Richard_J=.html">Richard J. Anderson</a>: A Random NC Algorithm for Depth First Search. 325-334 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AggarwalA87">BibTeX</a></font> <li><a name="MillerR87" href="../../indices/a-tree/m/Miller:Gary_L=.html">Gary L. Miller</a>, <a href="../../indices/a-tree/r/Ramachandran:Vijaya.html">Vijaya Ramachandran</a>: A New Graph Triconnectivity Algorithm and Its Parallelization. 335-344 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MillerR87">BibTeX</a></font> <li><a name="MulmuleyVV87" href="../../indices/a-tree/m/Mulmuley:Ketan.html">Ketan Mulmuley</a>, <a 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>: Matching Is as Easy as Matrix Inversion. 345-354 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MulmuleyVV87">BibTeX</a></font> <li><a name="NaorNS87" href="../../indices/a-tree/n/Naor:Joseph.html">Joseph Naor</a>, <a href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>, <a href="../../indices/a-tree/s/Sch=auml=ffer:Alejandro_A=.html">Alejandro A. Schäffer</a>: Fast Parallel Algorithms for Chordal Graphs (Extended Abstract). 355-364 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/NaorNS87">BibTeX</a></font> <li><a name="DietzS87" href="../../indices/a-tree/d/Dietz:Paul_F=.html">Paul F. Dietz</a>, <a href="../../indices/a-tree/s/Sleator:Daniel_Dominic.html">Daniel Dominic Sleator</a>: Two Algorithms for Maintaining Order in a List. 365-372 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DietzS87">BibTeX</a></font> <li><a name="BorodinLS87" href="../../indices/a-tree/b/Borodin:Allan.html">Allan Borodin</a>, <a href="../../indices/a-tree/l/Linial:Nathan.html">Nathan Linial</a>, <a href="../../indices/a-tree/s/Saks:Michael_E=.html">Michael E. Saks</a>: An Optimal Online Algorithm for Metrical Task Systems. 373-382 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BorodinLS87">BibTeX</a></font> <li><a name="Munro87" href="../../indices/a-tree/m/Munro:J=_Ian.html">J. Ian Munro</a>: Searching a Two Key Table Under a Single Key. 383-387 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Munro87">BibTeX</a></font> <li><a name="HeathI87" href="../../indices/a-tree/h/Heath:Lenwood_S=.html">Lenwood S. Heath</a>, <a href="../../indices/a-tree/i/Istrail:Sorin.html">Sorin Istrail</a>: The Pagenumber of Genus g Graphs is O(g). 388-397 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HeathI87">BibTeX</a></font> <li><a name="Ronyai87" href="../../indices/a-tree/r/R=oacute=nyai:Lajos.html">Lajos Rónyai</a>: Simple Algebras Are Difficult. 398-408 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Ronyai87">BibTeX</a></font> <li><a name="BabaiLS87" 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>, <a href="../../indices/a-tree/s/Seress:=Aacute=kos.html">Ákos Seress</a>: Permutation Groups in NC. 409-420 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BabaiLS87">BibTeX</a></font> <li><a name="ShelahS87" href="../../indices/a-tree/s/Shelah:Saharon.html">Saharon Shelah</a>, <a href="../../indices/a-tree/s/Spencer:Joel.html">Joel Spencer</a>: Threshold Spectra for Random Graphs. 421-424 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ShelahS87">BibTeX</a></font> <li><a name="KolaitisV87" href="../../indices/a-tree/k/Kolaitis:Phokion_G=.html">Phokion G. Kolaitis</a>, <a href="../../indices/a-tree/v/Vardi:Moshe_Y=.html">Moshe Y. Vardi</a>: The Decision Problem for the Probabilities of Higher-Order Properties. 425-435 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KolaitisV87">BibTeX</a></font> <li><a name="BilardiP87" href="../../indices/a-tree/b/Bilardi:Gianfranco.html">Gianfranco Bilardi</a>, <a href="../../indices/a-tree/p/Preparata:Franco_P=.html">Franco P. Preparata</a>: Size-Time Complexity of Boolean Networks for Prefix Computations. 436-442 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BilardiP87">BibTeX</a></font> <li><a name="Kaltofen87" href="../../indices/a-tree/k/Kaltofen:Erich.html">Erich Kaltofen</a>: Single-Factor Hensel Lifting and its Application to the Straight-Line Complexity of Certain Polynomials. 443-452 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Kaltofen87">BibTeX</a></font> <li><a name="Bach87" href="../../indices/a-tree/b/Bach:Eric.html">Eric Bach</a>: Realistic Analysis of Some Randomized Algorithms. 453-461 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Bach87">BibTeX</a></font> <li><a name="AdlemanH87" href="../../indices/a-tree/a/Adleman:Leonard_M=.html">Leonard M. Adleman</a>, <a href="../../indices/a-tree/h/Huang:Ming=Deh_A=.html">Ming-Deh A. Huang</a>: Recognizing Primes in Random Polynomial Time. 462-469 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AdlemanH87">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
