focs90.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>31. FOCS 1990: St. Louis, Missouri</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>31. <a href="index.html">FOCS</a> 1990: St. Louis, Missouri</h1> 31st Annual Symposium on Foundations of Computer Science, St. Louis, Missouri, 22-24 October 1990. IEEE Computer Society <ul> <li><a name="LundFKN90" href="../../indices/a-tree/l/Lund:Carsten.html">Carsten Lund</a>, <a href="../../indices/a-tree/f/Fortnow:Lance.html">Lance Fortnow</a>, <a href="../../indices/a-tree/k/Karloff:Howard_J=.html">Howard J. Karloff</a>, <a href="../../indices/a-tree/n/Nisan:Noam.html">Noam Nisan</a>: Algebraic Methods for Interactive Proof Systems. 2-10 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LundFKN90">BibTeX</a></font> <li><a name="Shamir90" href="../../indices/a-tree/s/Shamir:Adi.html">Adi Shamir</a>: IP=PSPACE. 11-15 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Shamir90">BibTeX</a></font> <li><a name="BabaiFL90" href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>, <a href="../../indices/a-tree/f/Fortnow:Lance.html">Lance Fortnow</a>, <a href="../../indices/a-tree/l/Lund:Carsten.html">Carsten Lund</a>: Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols. 16-25 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BabaiFL90">BibTeX</a></font> <li><a name="BabaiF90" href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>, <a href="../../indices/a-tree/f/Fortnow:Lance.html">Lance Fortnow</a>: A Characterization of \sharp P Arithmetic Straight Line Programs. 26-34 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BabaiF90">BibTeX</a></font> <li><a name="DolevDWY90" 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/w/Waarts:Orli.html">Orli Waarts</a>, <a href="../../indices/a-tree/y/Yung:Moti.html">Moti Yung</a>: Perfectly Secure Message Transmission. 36-45 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DolevDWY90">BibTeX</a></font> <li><a name="AlonN90" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>: Coin-Flipping Games Immune against Linear-Sized Coalitions (Extended Abstract). 46-54 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonN90">BibTeX</a></font> <li><a name="AttiyaLS90" href="../../indices/a-tree/a/Attiya:Hagit.html">Hagit Attiya</a>, <a href="../../indices/a-tree/l/Lynch:Nancy_A=.html">Nancy A. Lynch</a>, <a href="../../indices/a-tree/s/Shavit:Nir.html">Nir Shavit</a>: Are Wait-Free Algorithms Fast? (Extended Abstract). 55-64 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AttiyaLS90">BibTeX</a></font> <li><a name="AwerbuchS90" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/s/Saks:Michael_E=.html">Michael E. Saks</a>: A Dining Philosophers Algorithm with Polynomial Response Time. 65-74 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchS90">BibTeX</a></font> <li><a name="DuH90" href="../../indices/a-tree/d/Du:Ding=Zhu.html">Ding-Zhu Du</a>, <a href="../../indices/a-tree/h/Hwang:Frank_K=.html">Frank K. Hwang</a>: An Approach for Proving Lower Bounds: Solution of Gilbert-Pollak's Conjecture on Steiner Ratio. 76-85 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DuH90">BibTeX</a></font> <li><a name="FormannHHKLSWW90" href="../../indices/a-tree/f/Formann:Michael.html">Michael Formann</a>, <a href="../../indices/a-tree/h/Hagerup:Torben.html">Torben Hagerup</a>, <a href="../../indices/a-tree/h/Haralambides:James.html">James Haralambides</a>, <a href="../../indices/a-tree/k/Kaufmann:Michael.html">Michael Kaufmann</a>, <a href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/s/Symvonis:Antonios.html">Antonios Symvonis</a>, <a href="../../indices/a-tree/w/Welzl:Emo.html">Emo Welzl</a>, <a href="../../indices/a-tree/w/Woeginger:Gerhard_J=.html">Gerhard J. Woeginger</a>: Drawing Graphs in the Plane with High Resolution. 86-95 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FormannHHKLSWW90">BibTeX</a></font> <li><a name="ChengJ90" href="../../indices/a-tree/c/Cheng:Siu=Wing.html">Siu-Wing Cheng</a>, <a href="../../indices/a-tree/j/Janardan:Ravi.html">Ravi Janardan</a>: New Results on Dynamic Planar Point Location. 96-105 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChengJ90">BibTeX</a></font> <li><a name="ReifTY90" href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>, <a href="../../indices/a-tree/t/Tygar:J=_D=.html">J. D. Tygar</a>, <a href="../../indices/a-tree/y/Yoshida:Akitoshi.html">Akitoshi Yoshida</a>: The Computability and Complexity of Optical Beam Tracing. 106-114 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ReifTY90">BibTeX</a></font> <li><a name="ChangL90" href="../../indices/a-tree/c/Chang:William_I=.html">William I. Chang</a>, <a href="../../indices/a-tree/l/Lawler:Eugene_L=.html">Eugene L. Lawler</a>: Approximate String Matching in Sublinear Expected Time. 116-124 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChangL90">BibTeX</a></font> <li><a name="Li90" href="../../indices/a-tree/l/Li:Ming.html">Ming Li</a>: Towards a DNA Sequencing Theory (Learning a String) (Preliminary Version). 125-134 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Li90">BibTeX</a></font> <li><a name="ColussiGG90" href="../../indices/a-tree/c/Colussi:Livio.html">Livio Colussi</a>, <a href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/g/Giancarlo:Raffaele.html">Raffaele Giancarlo</a>: On the Exact Complexity of String Matching (Extended Abstract). 135-144 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ColussiGG90">BibTeX</a></font> <li><a name="DubinerGM90" href="../../indices/a-tree/d/Dubiner:Moshe.html">Moshe Dubiner</a>, <a href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/m/Magen:Edith.html">Edith Magen</a>: Faster Tree Pattern Matching. 145-150 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DubinerGM90">BibTeX</a></font> <li><a name="Neff90" href="../../indices/a-tree/n/Neff:C=_Andrew.html">C. Andrew Neff</a>: Specified Precision Polynomial Root Isolation is in NC. 152-162 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Neff90">BibTeX</a></font> <li><a name="KosarajuD90" href="../../indices/a-tree/k/Kosaraju:S=_Rao.html">S. Rao Kosaraju</a>, <a href="../../indices/a-tree/d/Delcher:Arthur_L=.html">Arthur L. Delcher</a>: A Tree-Partitioning Technique with Applications to Expression Evaluation and Term Matching (Extended Abstract). 163-172 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KosarajuD90">BibTeX</a></font> <li><a name="Lagergren90" href="../../indices/a-tree/l/Lagergren:Jens.html">Jens Lagergren</a>: Efficient Parallel Algorithms for Tree-Decomposition and Related Problems. 173-182 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Lagergren90">BibTeX</a></font> <li><a name="AngluinFP90" href="../../indices/a-tree/a/Angluin:Dana.html">Dana Angluin</a>, <a href="../../indices/a-tree/f/Frazier:Michael.html">Michael Frazier</a>, <a href="../../indices/a-tree/p/Pitt:Leonard.html">Leonard Pitt</a>: Learning Conjunctions of Horn Clauses (Extended Abstract). 186-192 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AngluinFP90">BibTeX</a></font> <li><a name="GoldmanKS90" href="../../indices/a-tree/g/Goldman:Sally_A=.html">Sally A. Goldman</a>, <a href="../../indices/a-tree/k/Kearns:Michael_J=.html">Michael J. Kearns</a>, <a href="../../indices/a-tree/s/Schapire:Robert_E=.html">Robert E. Schapire</a>: Exact Identification of Circuits Using Fixed Points of Amplification Functions (Extended Abstract). 193-202 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldmanKS90">BibTeX</a></font> <li><a name="MaassT90" 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 and Membership Queries. 203-210 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MaassT90">BibTeX</a></font> <li><a name="Chazelle90" href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>: Triangulating a Simple Polygon in Linear Time. 220-230 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Chazelle90">BibTeX</a></font> <li><a name="BernEG90" href="../../indices/a-tree/b/Bern:Marshall_W=.html">Marshall W. Bern</a>, <a href="../../indices/a-tree/e/Eppstein:David.html">David Eppstein</a>, <a href="../../indices/a-tree/g/Gilbert:John_R=.html">John R. Gilbert</a>: Provably Good Mesh Generation. 231-241 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BernEG90">BibTeX</a></font> <li><a name="ChazelleEGPSSS90" 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>, <a href="../../indices/a-tree/p/Pollack:Richard.html">Richard Pollack</a>, <a href="../../indices/a-tree/s/Seidel:Raimund.html">Raimund Seidel</a>, <a href="../../indices/a-tree/s/Sharir:Micha.html">Micha Sharir</a>, <a href="../../indices/a-tree/s/Snoeyink:Jack.html">Jack Snoeyink</a>: Counting and Cutting Cycles of Lines and Rods in Space. 242-251 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChazelleEGPSSS90">BibTeX</a></font> <li><a name="BergO90" href="../../indices/a-tree/b/Berg:Mark_de.html">Mark de Berg</a>, <a href="../../indices/a-tree/o/Overmars:Mark_H=.html">Mark H. Overmars</a>: Hidden Surface Removal for Axis-Parallel Polyhedra (Extended Abstract). 252-261 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BergO90">BibTeX</a></font> <li><a name="LeightonP90" href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/p/Plaxton:C=_Greg.html">C. Greg Plaxton</a>: A (fairly) Simple Circuit that (usually) Sorts. 264-274 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LeightonP90">BibTeX</a></font> <li><a name="AssafU90" href="../../indices/a-tree/a/Assaf:Shay.html">Shay Assaf</a>, <a href="../../indices/a-tree/u/Upfal:Eli.html">Eli Upfal</a>: Fault Tolerant Sorting Network. 275-284 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AssafU90">BibTeX</a></font> <li><a name="KaklamanisKLMRRTT90" href="../../indices/a-tree/k/Kaklamanis:Christos.html">Christos Kaklamanis</a>, <a href="../../indices/a-tree/k/Karlin:Anna_R=.html">Anna R. Karlin</a>, <a href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/m/Milenkovic:Victor.html">Victor Milenkovic</a>, <a href="../../indices/a-tree/r/Raghavan:Prabhakar.html">Prabhakar Raghavan</a>, <a href="../../indices/a-tree/r/Rao:Satish.html">Satish Rao</a>, <a href="../../indices/a-tree/t/Thomborson:Clark_D=.html">Clark D. Thomborson</a>, <a href="../../indices/a-tree/t/Tsantilas:A=.html">A. Tsantilas</a>: Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract). 285-296 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KaklamanisKLMRRTT90">BibTeX</a></font> <li><a name="BayB90" href="../../indices/a-tree/b/Bay:Paul.html">Paul Bay</a>, <a href="../../indices/a-tree/b/Bilardi:Gianfranco.html">Gianfranco Bilardi</a>: Deterministic On-Line Routing on Area-Universal Networks (Extended Abstract). 297-306 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BayB90">BibTeX</a></font> <li><a name="FeigeLS90" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>, <a href="../../indices/a-tree/l/Lapidot:Dror.html">Dror Lapidot</a>, <a href="../../indices/a-tree/s/Shamir:Adi.html">Adi Shamir</a>: Multiple Non-Interactive Zero Knowledge Proofs Based on a Single Random String (Extended Abstract). 308-317 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FeigeLS90">BibTeX</a></font> <li><a name="GoldreichILVZ90" href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/l/Levin:Leonid_A=.html">Leonid A. Levin</a>, <a href="../../indices/a-tree/v/Venkatesan:Ramarathnam.html">Ramarathnam Venkatesan</a>, <a href="../../indices/a-tree/z/Zuckerman:David.html">David Zuckerman</a>: Security Preserving Amplification of Hardness. 318-326 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldreichILVZ90">BibTeX</a></font> <li><a name="SturtivantZ90" href="../../indices/a-tree/s/Sturtivant:Carl.html">Carl Sturtivant</a>, <a href="../../indices/a-tree/z/Zhang:Zhi=Li.html">Zhi-Li Zhang</a>: Efficiently Inverting Bijections Given by Straight Line Programs. 327-334 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SturtivantZ90">BibTeX</a></font> <li><a name="ChorGK90" href="../../indices/a-tree/c/Chor:Benny.html">Benny Chor</a>, <a href="../../indices/a-tree/g/Ger=eacute=b=Graus:Mih=aacute=ly.html">Mihály Geréb-Graus</a>, <a href="../../indices/a-tree/k/Kushilevitz:Eyal.html">Eyal Kushilevitz</a>: Private Computations Over the Integers (Extended Abstract). 335-344 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChorGK90">BibTeX</a></font> <li><a name="LovaszS90" href="../../indices/a-tree/l/Lov=aacute=sz:L=aacute=szl=oacute=.html">László Lovász</a>, <a href="../../indices/a-tree/s/Simonovits:Mikl=oacute=s.html">Miklós Simonovits</a>: The Mixing Rate of Markov Chains, an Isoperimetric Inequality, and Computing the Volume. 346-354 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LovaszS90">BibTeX</a></font> <li><a name="DengP90" href="../../indices/a-tree/d/Deng:Xiaotie.html">Xiaotie Deng</a>, <a href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: Exploring an Unknown Graph (Extended Abstract). 355-361 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DengP90">BibTeX</a></font> <li><a name="KannanW90" href="../../indices/a-tree/k/Kannan:Sampath.html">Sampath Kannan</a>, <a href="../../indices/a-tree/w/Warnow:Tandy.html">Tandy Warnow</a>: Inferring Evolutionary History from DNA Sequences (Extended Abstract). 362-371 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KannanW90">BibTeX</a></font> <li><a name="FichMP90" href="../../indices/a-tree/f/Fich:Faith_E=.html">Faith E. Fich</a>, <a href="../../indices/a-tree/m/Munro:J=_Ian.html">J. Ian Munro</a>, <a href="../../indices/a-tree/p/Poblete:Patricio_V=.html">Patricio V. Poblete</a>: Permuting. 372-379 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FichMP90">BibTeX</a></font> <li><a name="KearnsS90" href="../../indices/a-tree/k/Kearns:Michael_J=.html">Michael J. Kearns</a>, <a href="../../indices/a-tree/s/Schapire:Robert_E=.html">Robert E. Schapire</a>: Efficient Distribution-free Learning of Probabilistic Concepts (Extended Abstract). 382-391 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KearnsS90">BibTeX</a></font> <li><a name="AldousV90" href="../../indices/a-tree/a/Aldous:David.html">David Aldous</a>, <a href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>: A Markovian Extension of Valiant's Learning Model (Extended Abstract). 392-396 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AldousV90">BibTeX</a></font> <li><a name="PaturiS90" href="../../indices/a-tree/p/Paturi:Ramamohan.html">Ramamohan Paturi</a>, <a href="../../indices/a-tree/s/Saks:Michael_E=.html">Michael E. Saks</a>: On Threshold Circuits for Parity. 397-404 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PaturiS90">BibTeX</a></font> <li><a name="Fulk90" href="../../indices/a-tree/f/Fulk:Mark_A=.html">Mark A. Fulk</a>: Robust Separations in Inductive Inference. 405-410 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Fulk90">BibTeX</a></font> <li><a name="Abrahamson90" href="../../indices/a-tree/a/Abrahamson:Karl_R=.html">Karl R. Abrahamson</a>: A Time-Space Tradeoff for Boolean Matrix Multiplication. 412-419 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Abrahamson90">BibTeX</a></font> <li><a name="BeameTY90" href="../../indices/a-tree/b/Beame:Paul.html">Paul Beame</a>, <a href="../../indices/a-tree/t/Tompa:Martin.html">Martin Tompa</a>, <a href="../../indices/a-tree/y/Yan:Peiyuan.html">Peiyuan Yan</a>: Communication-Space Tradeoffs for Unrestricted Protocols. 420-428 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BeameTY90">BibTeX</a></font> <li><a name="BeameBRRT90" href="../../indices/a-tree/b/Beame:Paul.html">Paul Beame</a>, <a href="../../indices/a-tree/b/Borodin:Allan.html">Allan Borodin</a>, <a href="../../indices/a-tree/r/Raghavan:Prabhakar.html">Prabhakar Raghavan</a>, <a href="../../indices/a-tree/r/Ruzzo:Walter_L=.html">Walter L. Ruzzo</a>, <a href="../../indices/a-tree/t/Tompa:Martin.html">Martin Tompa</a>: Time-Space Tradeoffs for Undirected Graph Traversal. 429-438 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BeameBRRT90">BibTeX</a></font> <li><a name="Istrail90" href="../../indices/a-tree/i/Istrail:Sorin.html">Sorin Istrail</a>: Constructing Generalized Universal Traversing Sequences of Polynomial Size for Graphs with Small Diameter (Extended Abstract). 439-448 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Istrail90">BibTeX</a></font> <li><a name="FiatRR90" href="../../indices/a-tree/f/Fiat:Amos.html">Amos Fiat</a>, <a href="../../indices/a-tree/r/Rabani:Yuval.html">Yuval Rabani</a>, <a href="../../indices/a-tree/r/Ravid:Yiftach.html">Yiftach Ravid</a>: Competitive k-Server Algorithms (Extended Abstract). 454-463 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FiatRR90">BibTeX</a></font> <li><a name="Vishwanathan90" href="../../indices/a-tree/v/Vishwanathan:Sundar.html">Sundar Vishwanathan</a>: Randomized Online Graph Coloring (Preliminary Version). 464-469 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Vishwanathan90">BibTeX</a></font> <li><a name="Irani90" href="../../indices/a-tree/i/Irani:Sandy.html">Sandy Irani</a>: Coloring Inductive Graphs On-Line. 470-479 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Irani90">BibTeX</a></font> <li><a name="ColeR90" href="../../indices/a-tree/c/Cole:Richard.html">Richard Cole</a>, <a href="../../indices/a-tree/r/Raghunathan:Arvind.html">Arvind Raghunathan</a>: Online Algorithms for Finger Searching (Extended Abstract). 480-489 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ColeR90">BibTeX</a></font> <li><a name="AwerbuchCK90" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/c/Cidon:Israel.html">Israel Cidon</a>, <a href="../../indices/a-tree/k/Kutten:Shay.html">Shay Kutten</a>: Communication-Optimal Maintenance of Replicated Information. 492-502 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchCK90">BibTeX</a></font> <li><a name="Zuckerman90" href="../../indices/a-tree/z/Zuckerman:David.html">David Zuckerman</a>: General Weak Random Sources. 534-543 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Zuckerman90">BibTeX</a></font> <li><a name="AlonGHP90" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>, <a href="../../indices/a-tree/p/Peralta:Ren=eacute=.html">René Peralta</a>: Simple Constructions of Almost k-Wise Independent Random Variables. 544-553 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonGHP90">BibTeX</a></font> <li><a name="BellareGG90" href="../../indices/a-tree/b/Bellare:Mihir.html">Mihir Bellare</a>, <a href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>: Randomness in Interactive Proofs. 563-572 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BellareGG90">BibTeX</a></font> <li><a name="AlonM90" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/m/Megiddo:Nimrod.html">Nimrod Megiddo</a>: Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time. 574-582 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonM90">BibTeX</a></font> <li><a name="Vaidya90" href="../../indices/a-tree/v/Vaidya:Pravin_M=.html">Pravin M. Vaidya</a>: Reducing the Parallel Complexity of Certain Linear Programming Problems (Extended Abstract). 583-589 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Vaidya90">BibTeX</a></font> <li><a name="MartelSP90" href="../../indices/a-tree/m/Martel:Charles_U=.html">Charles U. Martel</a>, <a href="../../indices/a-tree/s/Subramonian:Ramesh.html">Ramesh Subramonian</a>, <a href="../../indices/a-tree/p/Park:Arvin.html">Arvin Park</a>: Asynchronous PRAMs Are (Almost) as Good as Synchronous PRAMs. 590-599 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MartelSP90">BibTeX</a></font> <li><a name="AlpernCF90" href="../../indices/a-tree/a/Alpern:Bowen.html">Bowen Alpern</a>, <a href="../../indices/a-tree/c/Carter:Larry.html">Larry Carter</a>, <a href="../../indices/a-tree/f/Feig:Ephraim.html">Ephraim Feig</a>: Uniform Memory Hierarchies. 600-608 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlpernCF90">BibTeX</a></font> <li><a name="HastadG90" href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>, <a href="../../indices/a-tree/g/Goldmann:Mikael.html">Mikael Goldmann</a>: On the Power of Small-Depth Threshold Circuits. 610-618 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HastadG90">BibTeX</a></font> <li><a name="Yao90" href="../../indices/a-tree/y/Yao:Andrew_Chi=Chih.html">Andrew Chi-Chih Yao</a>: On ACC and Threshold Circuits. 619-627 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Yao90">BibTeX</a></font> <li><a name="Smolensky90" href="../../indices/a-tree/s/Smolensky:Roman.html">Roman Smolensky</a>: On Interpolation by Analytic Functions with Special Properties and Some Weak Lower Bounds on the Size of Circuits with Symmetric Gates. 628-631 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Smolensky90">BibTeX</a></font> <li><a name="BruckS90" href="../../indices/a-tree/b/Bruck:Jehoshua.html">Jehoshua Bruck</a>, <a href="../../indices/a-tree/s/Smolensky:Roman.html">Roman Smolensky</a>: Polynomial Threshold Functions, AC^0 Functions and Spectral Norms (Extended Abstract). 632-641 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BruckS90">BibTeX</a></font> <li><a name="PatersonPZ90" href="../../indices/a-tree/p/Paterson:Mike.html">Mike Paterson</a>, <a href="../../indices/a-tree/p/Pippenger:Nicholas.html">Nicholas Pippenger</a>, <a href="../../indices/a-tree/z/Zwick:Uri.html">Uri Zwick</a>: Faster Circuits and Shorter Formulae for Multiple Addition, Multiplication and Symmetric Boolean Functions. 642-650 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PatersonPZ90">BibTeX</a></font> <li><a name="HarelR90" href="../../indices/a-tree/h/Harel:David.html">David Harel</a>, <a href="../../indices/a-tree/r/Raz:Danny.html">Danny Raz</a>: Deciding Properties of Nonregular Programs (Preliminary Version). 652-661 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HarelR90">BibTeX</a></font> <li><a name="LincolnMSS90" href="../../indices/a-tree/l/Lincoln:Patrick.html">Patrick Lincoln</a>, <a href="../../indices/a-tree/m/Mitchell:John_C=.html">John C. Mitchell</a>, <a href="../../indices/a-tree/s/Scedrov:Andre.html">Andre Scedrov</a>, <a href="../../indices/a-tree/s/Shankar:Natarajan.html">Natarajan Shankar</a>: Decision Problems for Propositional Linear Logic. 662-671 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LincolnMSS90">BibTeX</a></font> <li><a name="MalerP90" href="../../indices/a-tree/m/Maler:Oded.html">Oded Maler</a>, <a href="../../indices/a-tree/p/Pnueli:Amir.html">Amir Pnueli</a>: Tight Bounds on the Complexity of Cascaded Decomposition of Automata. 672-682 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MalerP90">BibTeX</a></font> <li><a name="KaminskiF90" href="../../indices/a-tree/k/Kaminski:Michael.html">Michael Kaminski</a>, <a href="../../indices/a-tree/f/Francez:Nissim.html">Nissim Francez</a>: Finite-Memory Automata (Extended Abstract). 683-688 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KaminskiF90">BibTeX</a></font> <li><a name="Lynch90" href="../../indices/a-tree/l/Lynch:James_F=.html">James F. Lynch</a>: Probabilities of Sentences about Very Sparse Random Graphs. 689-696 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Lynch90">BibTeX</a></font> <li><a name="NaorGM90" href="../../indices/a-tree/n/Naor:Dalit.html">Dalit Naor</a>, <a href="../../indices/a-tree/g/Gusfield:Dan.html">Dan Gusfield</a>, <a href="../../indices/a-tree/m/Martel:Charles_U=.html">Charles U. Martel</a>: A Fast Algorithm for Optimally Increasing the Edge-Connectivity. 698-707 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NaorGM90">BibTeX</a></font> <li><a name="Frank90" href="../../indices/a-tree/f/Frank:Andr=aacute=s.html">András Frank</a>: Augmenting Graphs to Meet Edge-Connectivity Requirements. 708-718 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Frank90">BibTeX</a></font> <li><a name="FredmanW90" href="../../indices/a-tree/f/Fredman:Michael_L=.html">Michael L. Fredman</a>, <a href="../../indices/a-tree/w/Willard:Dan_E=.html">Dan E. Willard</a>: Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest Paths. 719-725 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FredmanW90">BibTeX</a></font> <li><a name="KleinARR90" href="../../indices/a-tree/k/Klein:Philip_N=.html">Philip N. Klein</a>, <a href="../../indices/a-tree/a/Agrawal:Ajit.html">Ajit Agrawal</a>, <a href="../../indices/a-tree/r/Ravi:R=.html">R. Ravi</a>, <a href="../../indices/a-tree/r/Rao:Satish.html">Satish Rao</a>: Approximation through Multicommodity Flow. 726-737 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KleinARR90">BibTeX</a></font> <li><a name="EvenLW90" href="../../indices/a-tree/e/Even:Shimon.html">Shimon Even</a>, <a href="../../indices/a-tree/l/Litman:Ami.html">Ami Litman</a>, <a href="../../indices/a-tree/w/Winkler:Peter.html">Peter Winkler</a>: Computing with Snakes in Directed Networks of Automata (Extended Abstract). 740-745 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/EvenLW90">BibTeX</a></font> <li><a name="PnueliR90" href="../../indices/a-tree/p/Pnueli:Amir.html">Amir Pnueli</a>, <a href="../../indices/a-tree/r/Rosner:Roni.html">Roni Rosner</a>: Distributed Reactive Systems Are Hard to Synthesize. 746-757 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PnueliR90">BibTeX</a></font> <li><a name="LuoT90" href="../../indices/a-tree/l/Luo:Zhi=Quan.html">Zhi-Quan Luo</a>, <a href="../../indices/a-tree/t/Tsitsiklis:John_N=.html">John N. Tsitsiklis</a>: Communication Complexity of Algebraic Computation (Extended Abstract). 758-765 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LuoT90">BibTeX</a></font> <li><a name="CanettiG90" href="../../indices/a-tree/c/Canetti:Ran.html">Ran Canetti</a>, <a href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>: Bounds on Tradeoffs between Randomness and Communication Complexity. 766-775 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CanettiG90">BibTeX</a></font> <li><a name="Toda90" href="../../indices/a-tree/t/Toda:Seinosuke.html">Seinosuke Toda</a>: The Complexity of Finding Medians. 778-787 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Toda90">BibTeX</a></font> <li><a name="BussPT90" href="../../indices/a-tree/b/Buss:Samuel_R=.html">Samuel R. Buss</a>, <a href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>, <a href="../../indices/a-tree/t/Tsitsiklis:John_N=.html">John N. Tsitsiklis</a>: On the Predictability of Coupled Automata: An Allegory about Chaos. 788-793 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BussPT90">BibTeX</a></font> <li><a name="Papadimitriou90" href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: On Graph-Theoretic Lemmata and Complexity Classes (Extended Abstract). 794-801 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Papadimitriou90">BibTeX</a></font> <li><a name="Gurevich90" href="../../indices/a-tree/g/Gurevich:Yuri.html">Yuri Gurevich</a>: Matrix Decomposition Problem Is Complete for the Average Case. 802-811 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Gurevich90">BibTeX</a></font> <li><a name="ImpagliazzoL90" href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/l/Levin:Leonid_A=.html">Leonid A. Levin</a>: No Better Ways to Generate Hard NP Instances than Picking Uniformly at Random. 812-821 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ImpagliazzoL90">BibTeX</a></font> <li><a name="KoscielskiP90" href="../../indices/a-tree/k/Koscielski:Antoni.html">Antoni Koscielski</a>, <a href="../../indices/a-tree/p/Pacholski:Leszek.html">Leszek Pacholski</a>: Complexity of Unification in Free Groups and Free Semi-groups. 824-829 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KoscielskiP90">BibTeX</a></font> <li><a name="ValleeF90" href="../../indices/a-tree/v/Vall=eacute=e:Brigitte.html">Brigitte Vallée</a>, <a href="../../indices/a-tree/f/Flajolet:Philippe.html">Philippe Flajolet</a>: The Lattice Reduction Algorithm of Gauss: An Average Case Analysis. 830-839 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ValleeF90">BibTeX</a></font> <li><a name="GrigorievKS90" href="../../indices/a-tree/g/Grigoriev:Dima.html">Dima Grigoriev</a>, <a href="../../indices/a-tree/k/Karpinski:Marek.html">Marek Karpinski</a>, <a href="../../indices/a-tree/s/Singer:Michael_F=.html">Michael F. Singer</a>: Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents. 840-846 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GrigorievKS90">BibTeX</a></font> <li><a name="HorngH90" href="../../indices/a-tree/h/Horng:Gwoboa.html">Gwoboa Horng</a>, <a href="../../indices/a-tree/h/Huang:Ming=Deh_A=.html">Ming-Deh A. Huang</a>: Simplifying Nested Radicals and Solving Polynomials by Radicals in Minimum Depth. 847-856 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HorngH90">BibTeX</a></font> <li><a name="BabaiHKLS90" href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>, <a href="../../indices/a-tree/h/Hetyei:G=aacute=bor.html">Gábor Hetyei</a>, <a href="../../indices/a-tree/k/Kantor:William_M=.html">William M. Kantor</a>, <a href="../../indices/a-tree/l/Lubotzky:Alexander.html">Alexander Lubotzky</a>, <a href="../../indices/a-tree/s/Seress:=Aacute=kos.html">Ákos Seress</a>: On the Diameter of Finite Groups. 857-865 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BabaiHKLS90">BibTeX</a></font> <li><a name="BerkmanJKTV90" href="../../indices/a-tree/b/Berkman:Omer.html">Omer Berkman</a>, <a href="../../indices/a-tree/j/J=aacute=J=aacute=:Joseph.html">Joseph JáJá</a>, <a href="../../indices/a-tree/k/Krishnamurthy:Sridhar.html">Sridhar Krishnamurthy</a>, <a href="../../indices/a-tree/t/Thurimella:Ramakrishna.html">Ramakrishna Thurimella</a>, <a href="../../indices/a-tree/v/Vishkin:Uzi.html">Uzi Vishkin</a>: Some Triply-Logarithmic Parallel Algorithms (Extended Abstract). 871-881 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BerkmanJKTV90">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
