focs89.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>30. FOCS 1989: Research Triangle Park, North Carolina</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>30. <a href="index.html">FOCS</a> 1989: Research Triangle Park, North Carolina</h1> 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, 30 October - 1 November 1989. IEEE Computer Society <ul> <li><a name="BergerR89" href="../../indices/a-tree/b/Berger:Bonnie.html">Bonnie Berger</a>, <a href="../../indices/a-tree/r/Rompel:John.html">John Rompel</a>: Simulating (log ^c n)-wise Independence in NC. 2-7 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BergerR89">BibTeX</a></font> <li><a name="MotwaniNN89" href="../../indices/a-tree/m/Motwani:Rajeev.html">Rajeev Motwani</a>, <a href="../../indices/a-tree/n/Naor:Joseph.html">Joseph Naor</a>, <a href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>: The Probabilistic Method Yields Deterministic Parallel Algorithms. 8-13 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MotwaniNN89">BibTeX</a></font> <li><a name="CohenW89" href="../../indices/a-tree/c/Cohen:Aviad.html">Aviad Cohen</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: Dispersers, Deterministic Amplification, and Weak Random Sources (Extended Abstract). 14-19 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CohenW89">BibTeX</a></font> <li><a name="Siegel89" href="../../indices/a-tree/s/Siegel:Alan.html">Alan Siegel</a>: On Universal Classes of Fast High Performance Hash Functions, Their Time-Space Tradeoff, and Their Applications (Extended Abstract). 20-25 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Siegel89">BibTeX</a></font> <li><a name="Schapire89" href="../../indices/a-tree/s/Schapire:Robert_E=.html">Robert E. Schapire</a>: The Strength of Weak Learnability (Extended Abstract). 28-33 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Schapire89">BibTeX</a></font> <li><a name="LiV89" href="../../indices/a-tree/l/Li:Ming.html">Ming Li</a>, <a href="../../indices/a-tree/v/Vit=aacute=nyi:Paul_M=_B=.html">Paul M. B. Vitányi</a>: A Theory of Learning Simple Concepts Under Simple Distributions and Average Case Complexity for the Universal Distribution (Extended Abstract). 34-39 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LiV89">BibTeX</a></font> <li><a name="Haussler89" href="../../indices/a-tree/h/Haussler:David.html">David Haussler</a>: Generalizing the PAC Model: Sample Size Bounds From Metric Dimension-based Uniform Convergence Results. 40-45 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Haussler89">BibTeX</a></font> <li><a name="GoldmanRS89" href="../../indices/a-tree/g/Goldman:Sally_A=.html">Sally A. Goldman</a>, <a href="../../indices/a-tree/r/Rivest:Ronald_L=.html">Ronald L. Rivest</a>, <a href="../../indices/a-tree/s/Schapire:Robert_E=.html">Robert E. Schapire</a>: Learning Binary Relations and Total Orders (Extended Abstract). 46-51 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldmanRS89">BibTeX</a></font> <li><a name="BergerRS89" href="../../indices/a-tree/b/Berger:Bonnie.html">Bonnie Berger</a>, <a href="../../indices/a-tree/r/Rompel:John.html">John Rompel</a>, <a href="../../indices/a-tree/s/Shor:Peter_W=.html">Peter W. Shor</a>: Efficient NC Algorithms for Set Cover with Applications to Learning and Geometry. 54-59 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BergerRS89">BibTeX</a></font> <li><a name="MarcotteS89" href="../../indices/a-tree/m/Marcotte:Odile.html">Odile Marcotte</a>, <a href="../../indices/a-tree/s/Suri:Subhash.html">Subhash Suri</a>: Fast Matching Algorithms for Points on a Polygon (Extended Abstract). 60-65 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MarcotteS89">BibTeX</a></font> <li><a name="FredericksonG89" href="../../indices/a-tree/f/Frederickson:Greg_N=.html">Greg N. Frederickson</a>, <a href="../../indices/a-tree/g/Guan:D=_J=.html">D. J. Guan</a>: Ensemble Motion Planning in Trees. 66-71 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FredericksonG89">BibTeX</a></font> <li><a name="PachSS89" href="../../indices/a-tree/p/Pach:J=aacute=nos.html">János Pach</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>: An Upper Bound on the Number of Planar k-Sets. 72-79 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PachSS89">BibTeX</a></font> <li><a name="Dickerson89" href="../../indices/a-tree/d/Dickerson:Matthew.html">Matthew Dickerson</a>: The Inverse of an Automorphism in Polynomial Time. 82-87 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Dickerson89">BibTeX</a></font> <li><a name="Gathen89" href="../../indices/a-tree/g/Gathen:Joachim_von_zur.html">Joachim von zur Gathen</a>: Testing Permutation Polynomials (Extended Abstract). 88-92 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Gathen89">BibTeX</a></font> <li><a name="BabaiR89" href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>, <a href="../../indices/a-tree/r/R=oacute=nyai:Lajos.html">Lajos Rónyai</a>: Computing Irreducible Representations of Finite Groups. 93-98 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BabaiR89">BibTeX</a></font> <li><a name="Ronyai89" href="../../indices/a-tree/r/R=oacute=nyai:Lajos.html">Lajos Rónyai</a>: Galois Groups and Factoring Polynomials over Finite Fields. 99-104 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ronyai89">BibTeX</a></font> <li><a name="GabowX89" href="../../indices/a-tree/g/Gabow:Harold_N=.html">Harold N. Gabow</a>, <a href="../../indices/a-tree/x/Xu:Ying.html">Ying Xu</a>: Efficient Algorithms for Independent Assignments on Graphic and Linear Matroids. 106-111 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GabowX89">BibTeX</a></font> <li><a name="MillerN89" href="../../indices/a-tree/m/Miller:Gary_L=.html">Gary L. Miller</a>, <a href="../../indices/a-tree/n/Naor:Joseph.html">Joseph Naor</a>: Flow in Planar Graphs with Multiple Sources and Sinks (Extended Abstract). 112-117 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MillerN89">BibTeX</a></font> <li><a name="CheriyanH89" href="../../indices/a-tree/c/Cheriyan:Joseph.html">Joseph Cheriyan</a>, <a href="../../indices/a-tree/h/Hagerup:Torben.html">Torben Hagerup</a>: A Randomized Maximum-Flow Algorithm. 118-123 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CheriyanH89">BibTeX</a></font> <li><a name="LinialV89" href="../../indices/a-tree/l/Linial:Nathan.html">Nathan Linial</a>, <a href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>: Graph Products and Chromatic Numbers. 124-128 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LinialV89">BibTeX</a></font> <li><a name="Ng89" href="../../indices/a-tree/n/Ng:Cheng.html">Cheng Ng</a>: Lower Bounds for the Stable Marriage Problem and its Variants. 129-133 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ng89">BibTeX</a></font> <li><a name="HallS89" href="../../indices/a-tree/h/Hall:Leslie_A=.html">Leslie A. Hall</a>, <a href="../../indices/a-tree/s/Shmoys:David_B=.html">David B. Shmoys</a>: Approximation Schemes for Constrained Scheduling Problems. 134-139 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HallS89">BibTeX</a></font> <li><a name="AjtaiG89" href="../../indices/a-tree/a/Ajtai:Mikl=oacute=s.html">Miklós Ajtai</a>, <a href="../../indices/a-tree/g/Gurevich:Yuri.html">Yuri Gurevich</a>: Datalog vs. First-Order Logic. 142-147 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AjtaiG89">BibTeX</a></font> <li><a name="AbadiH89" href="../../indices/a-tree/a/Abadi:Mart=iacute=n.html">Martín Abadi</a>, <a href="../../indices/a-tree/h/Halpern:Joseph_Y=.html">Joseph Y. Halpern</a>: Decidability and Expressiveness for First-Order Logics of Probability (Extended Abstract). 148-153 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AbadiH89">BibTeX</a></font> <li><a name="CookK89" href="../../indices/a-tree/c/Cook:Stephen_A=.html">Stephen A. Cook</a>, <a href="../../indices/a-tree/k/Kapron:Bruce_M=.html">Bruce M. Kapron</a>: Characterizations of the Basic Feasible Functionals of Finite Type (Extended Abstract). 154-159 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CookK89">BibTeX</a></font> <li><a name="PacholskiS89" href="../../indices/a-tree/p/Pacholski:Leszek.html">Leszek Pacholski</a>, <a href="../../indices/a-tree/s/Szwast:Wieslaw.html">Wieslaw Szwast</a>: The 0-1 Law Fails for the Class of Existential Second Order Gödel Sentences with Equality. 160-163 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PacholskiS89">BibTeX</a></font> <li><a name="AlurH89" href="../../indices/a-tree/a/Alur:Rajeev.html">Rajeev Alur</a>, <a href="../../indices/a-tree/h/Henzinger:Thomas_A=.html">Thomas A. Henzinger</a>: A Really Temporal Logic. 164-169 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlurH89">BibTeX</a></font> <li><a name="Russell89" href="../../indices/a-tree/r/Russell:James_R=.html">James R. Russell</a>: Full Abstraction for Nondeterministic Dataflow Networks. 170-175 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Russell89">BibTeX</a></font> <li><a name="GoodrichK89" href="../../indices/a-tree/g/Goodrich:Michael_T=.html">Michael T. Goodrich</a>, <a href="../../indices/a-tree/k/Kosaraju:S=_Rao.html">S. Rao Kosaraju</a>: Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation (Preliminary Version). 190-195 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoodrichK89">BibTeX</a></font> <li><a name="BerkmanV89" href="../../indices/a-tree/b/Berkman:Omer.html">Omer Berkman</a>, <a href="../../indices/a-tree/v/Vishkin:Uzi.html">Uzi Vishkin</a>: Recursive *-Tree Parallel Data-Structure (Extended Abstract). 196-202 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BerkmanV89">BibTeX</a></font> <li><a name="Ko89" href="../../indices/a-tree/k/Ko:Ker=I.html">Ker-I Ko</a>: Computational Complexity of Roots of Real Functions (Extended Abstract). 204-209 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ko89">BibTeX</a></font> <li><a name="AbrahamsonEFM89" href="../../indices/a-tree/a/Abrahamson:Karl_R=.html">Karl R. Abrahamson</a>, <a href="../../indices/a-tree/e/Ellis:John_A=.html">John A. Ellis</a>, <a href="../../indices/a-tree/f/Fellows:Michael_R=.html">Michael R. Fellows</a>, <a href="../../indices/a-tree/m/Mata:Manuel_E=.html">Manuel E. Mata</a>: On the Complexity of Fixed Parameter Problems (Extended Abstract). 210-215 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AbrahamsonEFM89">BibTeX</a></font> <li><a name="Krentel89" href="../../indices/a-tree/k/Krentel:Mark_W=.html">Mark W. Krentel</a>: Structure in Locally Optimal Solutions (Extended Abstract). 216-221 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Krentel89">BibTeX</a></font> <li><a name="ImpagliazzoT89" href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/t/Tardos:G=aacute=bor.html">Gábor Tardos</a>: Decision Versus Search Problems in Super-Polynomial Time. 222-227 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ImpagliazzoT89">BibTeX</a></font> <li><a name="ImpagliazzoL89" href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/l/Luby:Michael.html">Michael Luby</a>: One-way Functions are Essential for Complexity Based Cryptography (Extended Abstract). 230-235 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ImpagliazzoL89">BibTeX</a></font> <li><a name="ImpagliazzoN89" href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>: Efficient Cryptographic Schemes Provably as Secure as Subset Sum. 236-241 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ImpagliazzoN89">BibTeX</a></font> <li><a name="KharitonovGY89" href="../../indices/a-tree/k/Kharitonov:Michael.html">Michael Kharitonov</a>, <a href="../../indices/a-tree/g/Goldberg:Andrew_V=.html">Andrew V. Goldberg</a>, <a href="../../indices/a-tree/y/Yung:Moti.html">Moti Yung</a>: Lower Bounds for Pseudorandom Number Generators. 242-247 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KharitonovGY89">BibTeX</a></font> <li><a name="ImpagliazzoZ89" href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/z/Zuckerman:David.html">David Zuckerman</a>: How to Recycle Random Bits. 248-253 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ImpagliazzoZ89">BibTeX</a></font> <li><a name="LittlestoneW89" href="../../indices/a-tree/l/Littlestone:Nick.html">Nick Littlestone</a>, <a href="../../indices/a-tree/w/Warmuth:Manfred_K=.html">Manfred K. Warmuth</a>: The Weighted Majority Algorithm. 256-261 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LittlestoneW89">BibTeX</a></font> <li><a name="MaassT89" href="../../indices/a-tree/m/Maass:Wolfgang.html">Wolfgang Maass</a>, <a href="../../indices/a-tree/t/Tur=aacute=n:Gy=ouml=rgy.html">György Turán</a>: On the Complexity of Learning From Counterexamples (Extended Abstract). 262-267 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MaassT89">BibTeX</a></font> <li><a name="Tzeng89" href="../../indices/a-tree/t/Tzeng:Wen=Guey.html">Wen-Guey Tzeng</a>: The Equivalence and Learning of Probabilistic Automata (Extended Abstract). 268-273 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Tzeng89">BibTeX</a></font> <li><a name="FiatMSST89" href="../../indices/a-tree/f/Fiat:Amos.html">Amos Fiat</a>, <a href="../../indices/a-tree/m/Moses:Shahar.html">Shahar Moses</a>, <a href="../../indices/a-tree/s/Shamir:Adi.html">Adi Shamir</a>, <a href="../../indices/a-tree/s/Shimshoni:Ilan.html">Ilan Shimshoni</a>, <a href="../../indices/a-tree/t/Tardos:G=aacute=bor.html">Gábor Tardos</a>: Planning and Learning in Permutation Groups. 274-279 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FiatMSST89">BibTeX</a></font> <li><a name="RamachandranR89" href="../../indices/a-tree/r/Ramachandran:Vijaya.html">Vijaya Ramachandran</a>, <a href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>: An Optimal Parallel Algorithm for Graph Planarity (Extended Abstract). 282-287 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RamachandranR89">BibTeX</a></font> <li><a name="KhullerS89" href="../../indices/a-tree/k/Khuller:Samir.html">Samir Khuller</a>, <a href="../../indices/a-tree/s/Schieber:Baruch.html">Baruch Schieber</a>: Efficient Parallel Algorithms for Testing Connectivity and Finding Disjoint s-t Paths in Graphs (Extended Summary). 288-293 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KhullerS89">BibTeX</a></font> <li><a name="KirousisSS89" href="../../indices/a-tree/k/Kirousis:Lefteris_M=.html">Lefteris M. Kirousis</a>, <a href="../../indices/a-tree/s/Serna:Maria_J=.html">Maria J. Serna</a>, <a href="../../indices/a-tree/s/Spirakis:Paul_G=.html">Paul G. Spirakis</a>: The Parallel Complexity of the Subgraph Connectivity Problem. 294-299 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KirousisSS89">BibTeX</a></font> <li><a name="KhullerMV89" href="../../indices/a-tree/k/Khuller:Samir.html">Samir Khuller</a>, <a href="../../indices/a-tree/m/Mitchell:Stephen_G=.html">Stephen G. Mitchell</a>, <a href="../../indices/a-tree/v/Vazirani:Vijay_V=.html">Vijay V. Vazirani</a>: Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem, and for Finding a Kuratowski Homeomorph. 300-305 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KhullerMV89">BibTeX</a></font> <li><a name="Yao89" href="../../indices/a-tree/y/Yao:Andrew_Chi=Chih.html">Andrew Chi-Chih Yao</a>: Lower Bounds for Algebraic Computation Trees with Integer Inputs. 308-313 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Yao89">BibTeX</a></font> <li><a name="Landau89" href="../../indices/a-tree/l/Landau:Susan.html">Susan Landau</a>: Simplification of Nested Radicals. 314-319 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Landau89">BibTeX</a></font> <li><a name="Just89" href="../../indices/a-tree/j/Just:Bettina.html">Bettina Just</a>: Generalizing the Continued Fraction Algorithm to Arbitrary Dimensions. 320-324 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Just89">BibTeX</a></font> <li><a name="MansourST89" href="../../indices/a-tree/m/Mansour:Yishay.html">Yishay Mansour</a>, <a href="../../indices/a-tree/s/Schieber:Baruch.html">Baruch Schieber</a>, <a href="../../indices/a-tree/t/Tiwari:Prasoon.html">Prasoon Tiwari</a>: The Complexity of Approximating the Square Root (Extended Summary). 325-330 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MansourST89">BibTeX</a></font> <li><a name="DriscollH89" href="../../indices/a-tree/d/Driscoll:James_R=.html">James R. Driscoll</a>, <a href="../../indices/a-tree/h/Healy_Jr=:Dennis_M=.html">Dennis M. Healy Jr.</a>: Asymptotically Fast Algorithms for Spherical and Related Transforms. 344-349 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DriscollH89">BibTeX</a></font> <li><a name="GoldbergPST89" 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/Shmoys:David_B=.html">David B. Shmoys</a>, <a href="../../indices/a-tree/t/Tardos:=Eacute=va.html">Éva Tardos</a>: Interior-Point Methods in Parallel Computation. 350-355 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldbergPST89">BibTeX</a></font> <li><a name="AwerbuchMS89" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/m/Mansour:Yishay.html">Yishay Mansour</a>, <a href="../../indices/a-tree/s/Shavit:Nir.html">Nir Shavit</a>: Polynomial End-To-End Communication (Extended Abstract). 358-363 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchMS89">BibTeX</a></font> <li><a name="AwerbuchGLP89" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/g/Goldberg:Andrew_V=.html">Andrew V. Goldberg</a>, <a href="../../indices/a-tree/l/Luby:Michael.html">Michael Luby</a>, <a href="../../indices/a-tree/p/Plotkin:Serge_A=.html">Serge A. Plotkin</a>: Network Decomposition and Locality in Distributed Computation. 364-369 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchGLP89">BibTeX</a></font> <li><a name="AfekGR89" href="../../indices/a-tree/a/Afek:Yehuda.html">Yehuda Afek</a>, <a href="../../indices/a-tree/g/Gafni:Eli.html">Eli Gafni</a>, <a href="../../indices/a-tree/r/Ricklin:Moty.html">Moty Ricklin</a>: Upper and Lower Bounds for Routing Schemes in Dynamic Networks (Abstract). 370-375 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AfekGR89">BibTeX</a></font> <li><a name="Jiang89" href="../../indices/a-tree/j/Jiang:Tao.html">Tao Jiang</a>: The Synchronization of Nonuniform Networks of Finite Automata (Extended Abstract). 376-381 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Jiang89">BibTeX</a></font> <li><a name="LeightonM89" href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/m/Maggs:Bruce_M=.html">Bruce M. Maggs</a>: Expanders Might Be Practical: Fast Algorithms for Routing Around Faults on Multibutterflies. 384-389 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LeightonM89">BibTeX</a></font> <li><a name="Herley89" href="../../indices/a-tree/h/Herley:Kieran_T=.html">Kieran T. Herley</a>: Efficient Simulations of Small Shared Memories on Bounded Degree Networks (Preliminary Version). 390-395 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Herley89">BibTeX</a></font> <li><a name="Plaxton89" href="../../indices/a-tree/p/Plaxton:C=_Greg.html">C. Greg Plaxton</a>: On the Network Complexity of Selection. 396-401 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Plaxton89">BibTeX</a></font> <li><a name="ItkisL89" href="../../indices/a-tree/i/Itkis:Gene.html">Gene Itkis</a>, <a href="../../indices/a-tree/l/Levin:Leonid_A=.html">Leonid A. Levin</a>: Power of Fast VLSI Models Is Insensitive to Wires' Thinness. 402-407 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ItkisL89">BibTeX</a></font> <li><a name="BermanGP89" href="../../indices/a-tree/b/Berman:Piotr.html">Piotr Berman</a>, <a href="../../indices/a-tree/g/Garay:Juan_A=.html">Juan A. Garay</a>, <a href="../../indices/a-tree/p/Perry:Kenneth_J=.html">Kenneth J. Perry</a>: Towards Optimal Distributed Consensus (Extended Abstract). 410-415 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BermanGP89">BibTeX</a></font> <li><a name="Kushilevitz89" href="../../indices/a-tree/k/Kushilevitz:Eyal.html">Eyal Kushilevitz</a>: Privacy and Communication Complexity. 416-421 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Kushilevitz89">BibTeX</a></font> <li><a name="ChorM89" href="../../indices/a-tree/c/Chor:Benny.html">Benny Chor</a>, <a href="../../indices/a-tree/m/Moscovici:Lior.html">Lior Moscovici</a>: Solvability in Asynchronous Environments (Extended Abstract). 422-427 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChorM89">BibTeX</a></font> <li><a name="DolevF89" href="../../indices/a-tree/d/Dolev:Danny.html">Danny Dolev</a>, <a href="../../indices/a-tree/f/Feder:Tom=aacute=s.html">Tomás Feder</a>: Multiparty Communication Complexity. 428-433 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DolevF89">BibTeX</a></font> <li><a name="BattistaT89" href="../../indices/a-tree/b/Battista:Giuseppe_Di.html">Giuseppe Di Battista</a>, <a href="../../indices/a-tree/t/Tamassia:Roberto.html">Roberto Tamassia</a>: Incremental Planarity Testing (Extended Abstract). 436-441 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BattistaT89">BibTeX</a></font> <li><a name="Broder89" href="../../indices/a-tree/b/Broder:Andrei_Z=.html">Andrei Z. Broder</a>: Generating Random Spanning Trees. 442-447 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Broder89">BibTeX</a></font> <li><a name="Frederickson89" href="../../indices/a-tree/f/Frederickson:Greg_N=.html">Greg N. Frederickson</a>: Using Cellular Graph Embeddings in Solving All Pairs Shortest Paths Problems (Preliminary Version). 448-453 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Frederickson89">BibTeX</a></font> <li><a name="DahlhausK89" href="../../indices/a-tree/d/Dahlhaus:Elias.html">Elias Dahlhaus</a>, <a href="../../indices/a-tree/k/Karpinski:Marek.html">Marek Karpinski</a>: An Efficient Parallel Algorithm for the Minimal Elimination Ordering (MEO) of an Arbitrary Graph (Extended Abstract). 454-459 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DahlhausK89">BibTeX</a></font> <li><a name="CondonL89" href="../../indices/a-tree/c/Condon:Anne.html">Anne Condon</a>, <a href="../../indices/a-tree/l/Lipton:Richard_J=.html">Richard J. Lipton</a>: On the Complexity of Space Bounded Interactive Proofs (Extended Abstract). 462-467 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CondonL89">BibTeX</a></font> <li><a name="BeaverG89" href="../../indices/a-tree/b/Beaver:Donald.html">Donald Beaver</a>, <a href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>: Multiparty Computation with Faulty Majority (Extended Announcement). 468-473 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BeaverG89">BibTeX</a></font> <li><a name="KilianMO89" href="../../indices/a-tree/k/Kilian:Joe.html">Joe Kilian</a>, <a href="../../indices/a-tree/m/Micali:Silvio.html">Silvio Micali</a>, <a href="../../indices/a-tree/o/Ostrovsky:Rafail.html">Rafail Ostrovsky</a>: Minimum Resource Zero-Knowledge Proofs (Extended Abstract). 474-479 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KilianMO89">BibTeX</a></font> <li><a name="DworkS89" 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>: On the Power of 2-Way Probabilistic Finite State Automata (Extended Abstract). 480-485 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DworkS89">BibTeX</a></font> <li><a name="DobkinS89" href="../../indices/a-tree/d/Dobkin:David_P=.html">David P. Dobkin</a>, <a href="../../indices/a-tree/s/Suri:Subhash.html">Subhash Suri</a>: Dynamically Computing the Maxima of Decomposable Functions, with Applications. 488-493 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DobkinS89">BibTeX</a></font> <li><a name="Fortune89" href="../../indices/a-tree/f/Fortune:Steven.html">Steven Fortune</a>: Stable Maintenance of Point Set Triangulations in Two Dimensions. 494-499 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Fortune89">BibTeX</a></font> <li><a name="Milenkovic89" href="../../indices/a-tree/m/Milenkovic:Victor.html">Victor Milenkovic</a>: Double Precision Geometry: A General Technique for Calculating Line and Segment Intersections Using Rounded Arithmetic. 500-505 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Milenkovic89">BibTeX</a></font> <li><a name="KuchemWW89" href="../../indices/a-tree/k/Kuchem:Ruth.html">Ruth Kuchem</a>, <a href="../../indices/a-tree/w/Wagner:Dorothea.html">Dorothea Wagner</a>, <a href="../../indices/a-tree/w/Wagner:Frank.html">Frank Wagner</a>: Area-Optimal Three-Layer Channel Routing. 506-511 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KuchemWW89">BibTeX</a></font> <li><a name="Toda89" href="../../indices/a-tree/t/Toda:Seinosuke.html">Seinosuke Toda</a>: On the Computational Power of PP and +P. 514-519 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Toda89">BibTeX</a></font> <li><a name="FellowsL89" href="../../indices/a-tree/f/Fellows:Michael_R=.html">Michael R. Fellows</a>, <a href="../../indices/a-tree/l/Langston:Michael_A=.html">Michael A. Langston</a>: An Analogue of the Myhill-Nerode Theorem and Its Use in Computing Finite-Basis Characterizations (Extended Abstract). 520-525 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FellowsL89">BibTeX</a></font> <li><a name="Mihail89" href="../../indices/a-tree/m/Mihail:Milena.html">Milena Mihail</a>: Conductance and Convergence of Markov Chains-A Combinatorial Treatment of Expanders. 526-531 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Mihail89">BibTeX</a></font> <li><a name="Cai89" href="../../indices/a-tree/c/Cai:Jin=yi.html">Jin-yi Cai</a>: Lower Bounds for Constant Depth Circuits in the Presence of Help Bits. 532-537 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Cai89">BibTeX</a></font> <li><a name="AragonS89" href="../../indices/a-tree/a/Aragon:Cecilia_R=.html">Cecilia R. Aragon</a>, <a href="../../indices/a-tree/s/Seidel:Raimund.html">Raimund Seidel</a>: Randomized Search Trees. 540-545 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AragonS89">BibTeX</a></font> <li><a name="MehlhornNR89" href="../../indices/a-tree/m/Mehlhorn:Kurt.html">Kurt Mehlhorn</a>, <a href="../../indices/a-tree/n/N=auml=her:Stefan.html">Stefan Näher</a>, <a href="../../indices/a-tree/r/Rauch:Monika.html">Monika Rauch</a>: On the Complexity of a Game Related to the Dictionary Problem. 546-548 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MehlhornNR89">BibTeX</a></font> <li><a name="Jacobson89" href="../../indices/a-tree/j/Jacobson:Guy.html">Guy Jacobson</a>: Space-efficient Static Trees and Graphs. 549-554 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Jacobson89">BibTeX</a></font> <li><a name="Sundar89" href="../../indices/a-tree/s/Sundar:Rajamani.html">Rajamani Sundar</a>: Twists, Turns, Cascades, Deque Conjecture, and Scanning Theorem. 555-559 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Sundar89">BibTeX</a></font> <li><a name="RazW89" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: Probabilistic Communication Complexity of Boolean Relations (Extended Abstract). 562-567 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RazW89">BibTeX</a></font> <li><a name="CaiL89" href="../../indices/a-tree/c/Cai:Jin=yi.html">Jin-yi Cai</a>, <a href="../../indices/a-tree/l/Lipton:Richard_J=.html">Richard J. Lipton</a>: Subquadratic Simulations of Circuits by Branching Programs. 568-573 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CaiL89">BibTeX</a></font> <li><a name="LinialMN89" href="../../indices/a-tree/l/Linial:Nathan.html">Nathan Linial</a>, <a href="../../indices/a-tree/m/Mansour:Yishay.html">Yishay Mansour</a>, <a href="../../indices/a-tree/n/Nisan:Noam.html">Noam Nisan</a>: Constant Depth Circuits, Fourier Transform, and Learnability. 574-579 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LinialMN89">BibTeX</a></font> <li><a name="Allender89" href="../../indices/a-tree/a/Allender:Eric.html">Eric Allender</a>: A Note on the Power of Threshold Circuits. 580-584 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Allender89">BibTeX</a></font> <li><a name="Chazelle89" href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>: An Optimal Algorithm for Intersecting Three-Dimensional Convex Polyhedra (Detailed Abstract). 586-591 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Chazelle89">BibTeX</a></font> <li><a name="Mulmuley89" href="../../indices/a-tree/m/Mulmuley:Ketan.html">Ketan Mulmuley</a>: On Obstructions in Relation to a Fixed Viewpoint. 592-597 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Mulmuley89">BibTeX</a></font> <li><a name="OvermarsS89" href="../../indices/a-tree/o/Overmars:Mark_H=.html">Mark H. Overmars</a>, <a href="../../indices/a-tree/s/Sharir:Micha.html">Micha Sharir</a>: Output-Sensitive Hidden Surface Removal. 598-603 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/OvermarsS89">BibTeX</a></font> <li><a name="Hansen89" href="../../indices/a-tree/h/Hansen:Mark_D=.html">Mark D. Hansen</a>: Approximation Algorithms for Geometric Embeddings in the Plane with Applications to Parallel Processing Problems (Extended Abstract). 604-609 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Hansen89">BibTeX</a></font> <li><a name="CaiFI89" href="../../indices/a-tree/c/Cai:Jin=yi.html">Jin-yi Cai</a>, <a href="../../indices/a-tree/f/F=uuml=rer:Martin.html">Martin Fürer</a>, <a href="../../indices/a-tree/i/Immerman:Neil.html">Neil Immerman</a>: An Optimal Lower Bound on the Number of Variables for Graph Identification. 612-617 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CaiFI89">BibTeX</a></font> <li><a name="LiskiewiczL89" href="../../indices/a-tree/l/Liskiewicz:Maciej.html">Maciej Liskiewicz</a>, <a href="../../indices/a-tree/l/Lorys:Krzysztof.html">Krzysztof Lorys</a>: On Reversal Complexity for Alternating Turing Machines (Extended Abstract). 618-623 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LiskiewiczL89">BibTeX</a></font> <li><a name="FennerKR89" href="../../indices/a-tree/f/Fenner:Stephen_A=.html">Stephen A. Fenner</a>, <a href="../../indices/a-tree/k/Kurtz:Stuart_A=.html">Stuart A. Kurtz</a>, <a href="../../indices/a-tree/r/Royer:James_S=.html">James S. Royer</a>: Every Polynomial-Time 1-Degree Collapses iff P=PSPACE. 624-629 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FennerKR89">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:12:25 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
