stoc86.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>STOC 1986</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>18. <a href="index.html">STOC</a> 1986</h1> Proceedings of the 18th Annual ACM Symposium on Theory of Computing, May 28-30, 1986, Berkeley, California, USA. ACM 1986 <ul> <li><a name="Barrington86" href="../../indices/a-tree/b/Barrington:David_A=_Mix.html">David A. Mix Barrington</a>: Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC¹. 1-5 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Barrington86">BibTeX</a></font> <li><a name="Hastad86" href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>: Almost Optimal Lower Bounds for Small Depth Circuits. 6-20 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Hastad86">BibTeX</a></font> <li><a name="Cai86" href="../../indices/a-tree/c/Cai:Jin=yi.html">Jin-yi Cai</a>: With Probability One, A Random Oracle Separates PSPACE from the Polynomial-Time Hierarchy. 21-29 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Cai86">BibTeX</a></font> <li><a name="AjtaiBHKPRST86" href="../../indices/a-tree/a/Ajtai:Mikl=oacute=s.html">Miklós Ajtai</a>, <a href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>, <a href="../../indices/a-tree/h/Hajnal:P=eacute=ter.html">Péter Hajnal</a>, <a href="../../indices/a-tree/k/Koml=oacute=s:J=aacute=nos.html">János Komlós</a>, <a href="../../indices/a-tree/p/Pudl=aacute=k:Pavel.html">Pavel Pudlák</a>, <a href="../../indices/a-tree/r/R=ouml=dl:Vojtech.html">Vojtech Rödl</a>, <a href="../../indices/a-tree/s/Szemer=eacute=di:Endre.html">Endre Szemerédi</a>, <a href="../../indices/a-tree/t/Tur=aacute=n:Gy=ouml=rgy.html">György Turán</a>: Two lower bounds for branching programs. 30-38 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AjtaiBHKPRST86">BibTeX</a></font> <li><a name="GalilKS86" href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/k/Kannan:Ravi.html">Ravi Kannan</a>, <a href="../../indices/a-tree/s/Szemer=eacute=di:Endre.html">Endre Szemerédi</a>: On Nontrivial Separators for k-Page Graphs and Simulations by Nondeterministic One-Tape Turing Machines. 39-49 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GalilKS86">BibTeX</a></font> <li><a name="Broder86" href="../../indices/a-tree/b/Broder:Andrei_Z=.html">Andrei Z. Broder</a>: How hard is to marry at random? (On the approximation of the permanent). 50-58 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Broder86">BibTeX</a></font> <li><a name="GoldwasserS86" href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/s/Sipser:Michael.html">Michael Sipser</a>: Private Coins versus Public Coins in Interactive Proof Systems. 59-68 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldwasserS86">BibTeX</a></font> <li><a name="Krentel86" href="../../indices/a-tree/k/Krentel:Mark_W=.html">Mark W. Krentel</a>: The Complexity of Optimization Problems. 69-76 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Krentel86">BibTeX</a></font> <li><a name="CoffmanL86" href="../../indices/a-tree/c/Coffman_Jr=:Edward_G=.html">Edward G. Coffman Jr.</a>, <a href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>: A Provably Efficient Algorithm for Dynamic Storage Allocation. 77-90 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CoffmanL86">BibTeX</a></font> <li><a name="LeightonS86" href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/s/Shor:Peter_W=.html">Peter W. Shor</a>: Tight Bounds for Minimax Grid Matching, With Applications to the Average Case Analysis of Algorithms. 91-103 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LeightonS86">BibTeX</a></font> <li><a name="Yannakakis86" href="../../indices/a-tree/y/Yannakakis:Mihalis.html">Mihalis Yannakakis</a>: Four Pages are Necessary and Sufficient for Planar Graphs (Extended Abstract). 104-108 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Yannakakis86">BibTeX</a></font> <li><a name="DriscollSST86" href="../../indices/a-tree/d/Driscoll:James_R=.html">James R. Driscoll</a>, <a href="../../indices/a-tree/s/Sarnak:Neil.html">Neil Sarnak</a>, <a 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>: Making Data Structures Persistent. 109-121 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DriscollSST86">BibTeX</a></font> <li><a name="SleatorTT86" 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>, <a href="../../indices/a-tree/t/Thurston:William_P=.html">William P. Thurston</a>: Rotation Distance, Triangulations, and Hyperbolic Geometry. 122-135 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/SleatorTT86">BibTeX</a></font> <li><a name="GoldbergT86" 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>: A New Approach to the Maximum Flow Problem. 136-146 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldbergT86">BibTeX</a></font> <li><a name="KapoorV86" href="../../indices/a-tree/k/Kapoor:Sanjiv.html">Sanjiv Kapoor</a>, <a href="../../indices/a-tree/v/Vaidya:Pravin_M=.html">Pravin M. Vaidya</a>: Fast Algorithms for Convex Quadratic Programming and Multicommodity Flows. 147-159 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KapoorV86">BibTeX</a></font> <li><a name="KarlinU86" href="../../indices/a-tree/k/Karlin:Anna_R=.html">Anna R. Karlin</a>, <a href="../../indices/a-tree/u/Upfal:Eli.html">Eli Upfal</a>: Parallel Hashing-An Efficient Implementation of Shared Memory (Preliminary Version). 160-168 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KarlinU86">BibTeX</a></font> <li><a name="Beame86" href="../../indices/a-tree/b/Beame:Paul.html">Paul Beame</a>: Limits on the Power of Concurrent-Write Parallel Machines. 169-176 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Beame86">BibTeX</a></font> <li><a name="LiY86" href="../../indices/a-tree/l/Li:Ming.html">Ming Li</a>, <a href="../../indices/a-tree/y/Yesha:Yaacov.html">Yaacov Yesha</a>: New Lower Bounds for Parallel Computation. 177-187 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LiY86">BibTeX</a></font> <li><a name="AjtaiKSS86" 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/Steiger:William_L=.html">William L. Steiger</a>, <a href="../../indices/a-tree/s/Szemer=eacute=di:Endre.html">Endre Szemerédi</a>: Deterministic Selection in O(log log N) Parallel Time. 188-195 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AjtaiKSS86">BibTeX</a></font> <li><a name="LuekerMR86" href="../../indices/a-tree/l/Lueker:George_S=.html">George S. Lueker</a>, <a href="../../indices/a-tree/m/Megiddo:Nimrod.html">Nimrod Megiddo</a>, <a href="../../indices/a-tree/r/Ramachandran:Vijaya.html">Vijaya Ramachandran</a>: Linear Programming with Two Variables per Inequality in Poly-Log Time (Preliminary Version). 196-205 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LuekerMR86">BibTeX</a></font> <li><a name="ColeV86" href="../../indices/a-tree/c/Cole:Richard.html">Richard Cole</a>, <a href="../../indices/a-tree/v/Vishkin:Uzi.html">Uzi Vishkin</a>: Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms. 206-219 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ColeV86">BibTeX</a></font> <li><a name="LandauV86" href="../../indices/a-tree/l/Landau:Gad_M=.html">Gad M. Landau</a>, <a href="../../indices/a-tree/v/Vishkin:Uzi.html">Uzi Vishkin</a>: Introducing Efficient Parallelism into Approximate String Matching and a New Serial Algorithm. 220-230 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LandauV86">BibTeX</a></font> <li><a name="Kosaraju86" href="../../indices/a-tree/k/Kosaraju:S=_Rao.html">S. Rao Kosaraju</a>: Parallel Evaluation of Division-Free Arithmetic Expressions. 231-239 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Kosaraju86">BibTeX</a></font> <li><a name="LubotzkyPS86" href="../../indices/a-tree/l/Lubotzky:Alexander.html">Alexander Lubotzky</a>, <a href="../../indices/a-tree/p/Phillips:R=.html">R. Phillips</a>, <a href="../../indices/a-tree/s/Sarnak:P=.html">P. Sarnak</a>: Explicit Expanders and the Ramanujan Conjectures. 240-246 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LubotzkyPS86">BibTeX</a></font> <li><a name="FeldmanFP86" href="../../indices/a-tree/f/Feldman:Paul.html">Paul Feldman</a>, <a href="../../indices/a-tree/f/Friedman:Joel.html">Joel Friedman</a>, <a href="../../indices/a-tree/p/Pippenger:Nicholas.html">Nicholas Pippenger</a>: Non-Blocking Networks (Preliminary Version). 247-254 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FeldmanFP86">BibTeX</a></font> <li><a name="SchnorrS86" href="../../indices/a-tree/s/Schnorr:Claus=Peter.html">Claus-Peter Schnorr</a>, <a href="../../indices/a-tree/s/Shamir:Adi.html">Adi Shamir</a>: An Optimal Sorting Algorithm for Mesh Connected Computers. 255-263 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/SchnorrS86">BibTeX</a></font> <li><a name="KosarajuA86" href="../../indices/a-tree/k/Kosaraju:S=_Rao.html">S. Rao Kosaraju</a>, <a href="../../indices/a-tree/a/Atallah:Mikhail_J=.html">Mikhail J. Atallah</a>: Optimal Simulations between Mesh-Connected Arrays of Processors (Preliminary Version). 264-272 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KosarajuA86">BibTeX</a></font> <li><a name="BlumerEHW86" href="../../indices/a-tree/b/Blumer:Anselm.html">Anselm Blumer</a>, <a href="../../indices/a-tree/e/Ehrenfeucht:Andrzej.html">Andrzej Ehrenfeucht</a>, <a href="../../indices/a-tree/h/Haussler:David.html">David Haussler</a>, <a href="../../indices/a-tree/w/Warmuth:Manfred_K=.html">Manfred K. Warmuth</a>: Classifying Learnable Geometric Concepts with the Vapnik-Chervonenkis Dimension (Extended Abstract). 273-282 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BlumerEHW86">BibTeX</a></font> <li><a name="CourcoubetisVW86" href="../../indices/a-tree/c/Courcoubetis:Costas.html">Costas Courcoubetis</a>, <a href="../../indices/a-tree/v/Vardi:Moshe_Y=.html">Moshe Y. Vardi</a>, <a href="../../indices/a-tree/w/Wolper:Pierre.html">Pierre Wolper</a>: Reasoning about Fair Concurrent Programs. 283-294 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CourcoubetisVW86">BibTeX</a></font> <li><a name="KoLD86" href="../../indices/a-tree/k/Ko:Ker=I.html">Ker-I Ko</a>, <a href="../../indices/a-tree/l/Long:Timothy_J=.html">Timothy J. Long</a>, <a href="../../indices/a-tree/d/Du:Ding=Zhu.html">Ding-Zhu Du</a>: A Note on One-Way Functions and Polynomial-Time Isomorphisms (Extended Abstract). 295-303 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KoLD86">BibTeX</a></font> <li><a name="HalpernV86" href="../../indices/a-tree/h/Halpern:Joseph_Y=.html">Joseph Y. Halpern</a>, <a href="../../indices/a-tree/v/Vardi:Moshe_Y=.html">Moshe Y. Vardi</a>: The Complexity of Reasoning about Knowledge and Time: Extended Abstract. 304-315 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HalpernV86">BibTeX</a></font> <li><a name="GoldwasserK86" href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/k/Kilian:Joe.html">Joe Kilian</a>: Almost All Primes Can Be Quickly Certified. 316-329 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldwasserK86">BibTeX</a></font> <li><a name="Kaltofen86" href="../../indices/a-tree/k/Kaltofen:Erich.html">Erich Kaltofen</a>: Uniform Closure Properties of P-Computable Functions. 330-337 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Kaltofen86">BibTeX</a></font> <li><a name="Mulmuley86" href="../../indices/a-tree/m/Mulmuley:Ketan.html">Ketan Mulmuley</a>: A Fast Parallel Algorithm to Compute the Rank of a Matrix over an Arbitrary Field. 338-339 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Mulmuley86">BibTeX</a></font> <li><a name="Ben-OrFKT86" href="../../indices/a-tree/b/Ben=Or:Michael.html">Michael Ben-Or</a>, <a href="../../indices/a-tree/f/Feig:Ephraim.html">Ephraim Feig</a>, <a href="../../indices/a-tree/k/Kozen:Dexter.html">Dexter Kozen</a>, <a href="../../indices/a-tree/t/Tiwari:Prasoon.html">Prasoon Tiwari</a>: A Fast Parallel Algorithm for Determining All Roots of a Polynomial with Real Roots. 340-349 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Ben-OrFKT86">BibTeX</a></font> <li><a name="AdlemanL86" href="../../indices/a-tree/a/Adleman:Leonard_M=.html">Leonard M. Adleman</a>, <a href="../../indices/a-tree/l/Lenstra_Jr=:Hendrik_W=.html">Hendrik W. Lenstra Jr.</a>: Finding Irreducible Polynomials over Finite Fields. 350-355 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AdlemanL86">BibTeX</a></font> <li><a name="LubyR86" href="../../indices/a-tree/l/Luby:Michael.html">Michael Luby</a>, <a href="../../indices/a-tree/r/Rackoff:Charles.html">Charles Rackoff</a>: Pseudo-random Permutation Generators and Cryptographic Composition. 356-363 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LubyR86">BibTeX</a></font> <li><a name="Cleve86" href="../../indices/a-tree/c/Cleve:Richard.html">Richard Cleve</a>: Limits on the Security of Coin Flips when Half the Processors Are Faulty (Extended Abstract). 364-369 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Cleve86">BibTeX</a></font> <li><a name="DworkPPU86" href="../../indices/a-tree/d/Dwork:Cynthia.html">Cynthia Dwork</a>, <a href="../../indices/a-tree/p/Peleg:David.html">David Peleg</a>, <a href="../../indices/a-tree/p/Pippenger:Nicholas.html">Nicholas Pippenger</a>, <a href="../../indices/a-tree/u/Upfal:Eli.html">Eli Upfal</a>: Fault Tolerance in Networks of Bounded Degree (Preliminary Version). 370-379 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DworkPPU86">BibTeX</a></font> <li><a name="TarjanW86" href="../../indices/a-tree/t/Tarjan:Robert_Endre.html">Robert Endre Tarjan</a>, <a href="../../indices/a-tree/w/Wyk:Christopher_J=_Van.html">Christopher J. Van Wyk</a>: A Linear-Time Algorithm for Triangulating Simple Polygons. 380-388 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/TarjanW86">BibTeX</a></font> <li><a name="EdelsbrunnerG86" 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>: Topologically Sweeping an Arrangement. 389-403 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/EdelsbrunnerG86">BibTeX</a></font> <li><a name="Seidel86" href="../../indices/a-tree/s/Seidel:Raimund.html">Raimund Seidel</a>: Constructing Higher-Dimensional Convex Hulls at Logarithmic Cost per Face. 404-413 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Seidel86">BibTeX</a></font> <li><a name="Clarkson86" href="../../indices/a-tree/c/Clarkson:Kenneth_L=.html">Kenneth L. Clarkson</a>: Further Applications of Random Sampling to Computational Geometry. 414-423 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Clarkson86">BibTeX</a></font> <li><a name="DobkinEY86" href="../../indices/a-tree/d/Dobkin:David_P=.html">David P. Dobkin</a>, <a href="../../indices/a-tree/e/Edelsbrunner:Herbert.html">Herbert Edelsbrunner</a>, <a href="../../indices/a-tree/y/Yap:Chee=Keng.html">Chee-Keng Yap</a>: Probing Convex Polytopes. 424-432 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DobkinEY86">BibTeX</a></font> <li><a name="Bern86" href="../../indices/a-tree/b/Bern:Marshall_W=.html">Marshall W. Bern</a>: Two Probabilistic Results on Rectilinear Steiner Trees. 433-441 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Bern86">BibTeX</a></font> <li><a name="BaranyF86" href="../../indices/a-tree/b/B=aacute=r=aacute=ny:Imre.html">Imre Bárány</a>, <a href="../../indices/a-tree/f/F=uuml=redi:Zolt=aacute=n.html">Zoltán Füredi</a>: Computing the Volume Is Difficult. 442-447 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BaranyF86">BibTeX</a></font> <li><a name="Siegel86" href="../../indices/a-tree/s/Siegel:Alan.html">Alan Siegel</a>: Aspects of Information Flow in VLSI Circuits (Extended Abstract). 448-459 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Siegel86">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
