focs91.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>32. FOCS 1991: San Juan, Puerto Rico</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>32. <a href="index.html">FOCS</a> 1991: San Juan, Puerto Rico</h1> 32nd Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 1-4 October 1991. IEEE Computer Society <ul> <li><a name="FeigeGLSS91" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>, <a href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/l/Lov=aacute=sz:L=aacute=szl=oacute=.html">László Lovász</a>, <a href="../../indices/a-tree/s/Safra:Shmuel.html">Shmuel Safra</a>, <a href="../../indices/a-tree/s/Szegedy:Mario.html">Mario Szegedy</a>: Approximating Clique is Almost NP-Complete (Preliminary Version). 2-12 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FeigeGLSS91">BibTeX</a></font> <li><a name="LapidotS91" href="../../indices/a-tree/l/Lapidot:Dror.html">Dror Lapidot</a>, <a href="../../indices/a-tree/s/Shamir:Adi.html">Adi Shamir</a>: Fully Parallelized Multi Prover Protocols for NEXP-Time (Extended Abstract). 13-18 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LapidotS91">BibTeX</a></font> <li><a name="BeigelBFG91" href="../../indices/a-tree/b/Beigel:Richard.html">Richard Beigel</a>, <a href="../../indices/a-tree/b/Bellare:Mihir.html">Mihir Bellare</a>, <a href="../../indices/a-tree/f/Feigenbaum:Joan.html">Joan Feigenbaum</a>, <a href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>: Languages that Are Easier than their Proofs. 19-28 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BeigelBFG91">BibTeX</a></font> <li><a name="Chazelle91" href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>: An Optimal Convex Hull Algorithm and New Results on Cuttings (Extended Abstract). 29-38 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Chazelle91">BibTeX</a></font> <li><a name="HoffmanKK91" href="../../indices/a-tree/h/Hoffmann:Frank.html">Frank Hoffmann</a>, <a href="../../indices/a-tree/k/Kaufmann:Michael.html">Michael Kaufmann</a>, <a href="../../indices/a-tree/k/Kriegel:Klaus.html">Klaus Kriegel</a>: The Art Gallery Theorem for Polygons With Holes. 39-48 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HoffmanKK91">BibTeX</a></font> <li><a name="MatousekMPSSW91" href="../../indices/a-tree/m/Matousek:Jir=iacute=.html">Jirí Matousek</a>, <a href="../../indices/a-tree/m/Miller:Nathaly.html">Nathaly Miller</a>, <a href="../../indices/a-tree/p/Pach:J=aacute=nos.html">János Pach</a>, <a href="../../indices/a-tree/s/Sharir:Micha.html">Micha Sharir</a>, <a href="../../indices/a-tree/s/Sifrony:Shmuel.html">Shmuel Sifrony</a>, <a href="../../indices/a-tree/w/Welzl:Emo.html">Emo Welzl</a>: Fat Triangles Determine Linearly Many Holes. 49-58 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MatousekMPSSW91">BibTeX</a></font> <li><a name="GoldreichP91" href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/p/Petrank:Erez.html">Erez Petrank</a>: Quantifying Knowledge Complexity. 59-68 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldreichP91">BibTeX</a></font> <li><a name="BoyarBP91" href="../../indices/a-tree/b/Boyar:Joan.html">Joan Boyar</a>, <a href="../../indices/a-tree/b/Brassard:Gilles.html">Gilles Brassard</a>, <a href="../../indices/a-tree/p/Peralta:Ren=eacute=.html">René Peralta</a>: Subquadratic Zero-Knowledge. 69-78 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BoyarBP91">BibTeX</a></font> <li><a name="Zuckerman91" href="../../indices/a-tree/z/Zuckerman:David.html">David Zuckerman</a>: Simulating BPP Using a General Weak Random Source. 79-89 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Zuckerman91">BibTeX</a></font> <li><a name="BlumEGKN91" href="../../indices/a-tree/b/Blum:Manuel.html">Manuel Blum</a>, <a href="../../indices/a-tree/e/Evans:William_S=.html">William S. Evans</a>, <a href="../../indices/a-tree/g/Gemmell:Peter.html">Peter Gemmell</a>, <a href="../../indices/a-tree/k/Kannan:Sampath.html">Sampath Kannan</a>, <a href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>: Checking the Correctness of Memories. 90-99 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BlumEGKN91">BibTeX</a></font> <li><a name="BaruahKMRRS91" href="../../indices/a-tree/b/Baruah:Sanjoy_K=.html">Sanjoy K. Baruah</a>, <a href="../../indices/a-tree/k/Koren:Gilad.html">Gilad Koren</a>, <a href="../../indices/a-tree/m/Mishra:Bhubaneswar.html">Bhubaneswar Mishra</a>, <a href="../../indices/a-tree/r/Raghunathan:Arvind.html">Arvind Raghunathan</a>, <a href="../../indices/a-tree/r/Rosier:Louis_E=.html">Louis E. Rosier</a>, <a href="../../indices/a-tree/s/Shasha:Dennis.html">Dennis Shasha</a>: On-line Scheduling in the Presence of Overload. 100-110 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BaruahKMRRS91">BibTeX</a></font> <li><a name="FeldmannST91" href="../../indices/a-tree/f/Feldmann:Anja.html">Anja Feldmann</a>, <a href="../../indices/a-tree/s/Sgall:Jiri.html">Jiri Sgall</a>, <a href="../../indices/a-tree/t/Teng:Shang=Hua.html">Shang-Hua Teng</a>: Dynamic Scheduling on Parallel Machines. 111-120 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FeldmannST91">BibTeX</a></font> <li><a name="VitterK91" href="../../indices/a-tree/v/Vitter:Jeffrey_Scott.html">Jeffrey Scott Vitter</a>, <a href="../../indices/a-tree/k/Krishnan:P=.html">P. Krishnan</a>: Optimal Prefetching via Data Compression (Extended Abstract). 121-130 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/VitterK91">BibTeX</a></font> <li><a name="ShmoysWW91" href="../../indices/a-tree/s/Shmoys:David_B=.html">David B. Shmoys</a>, <a href="../../indices/a-tree/w/Wein:Joel.html">Joel Wein</a>, <a href="../../indices/a-tree/w/Williamson:David_P=.html">David P. Williamson</a>: Scheduling Parallel Machines On-Line. 131-140 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ShmoysWW91">BibTeX</a></font> <li><a name="Kunde91" href="../../indices/a-tree/k/Kunde:Manfred.html">Manfred Kunde</a>: Concentrated Regular Data Streams on Grids: Sorting and Routing Near to the Bisection Bound. 141-150 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Kunde91">BibTeX</a></font> <li><a name="WuK91" href="../../indices/a-tree/w/Wu:I=Chen.html">I-Chen Wu</a>, <a href="../../indices/a-tree/k/Kung:H=_T=.html">H. T. Kung</a>: Communication Complexity for Parallel Divide-and-Conquer. 151-162 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/WuK91">BibTeX</a></font> <li><a name="Papadimitriou91" href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: On Selecting a Satisfying Truth Assignment (Extended Abstract). 163-169 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Papadimitriou91">BibTeX</a></font> <li><a name="AizensteinP91" href="../../indices/a-tree/a/Aizenstein:Howard.html">Howard Aizenstein</a>, <a href="../../indices/a-tree/p/Pitt:Leonard.html">Leonard Pitt</a>: Exact Learning of Read-Twice DNF Formulas (Extended Abstract). 170-179 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AizensteinP91">BibTeX</a></font> <li><a name="Schwarzkopf91" href="../../indices/a-tree/s/Schwarzkopf:Otfried.html">Otfried Schwarzkopf</a>: Dynamic Maintenance of Geometric Structures Made Easy. 197-206 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Schwarzkopf91">BibTeX</a></font> <li><a name="Matousek91" href="../../indices/a-tree/m/Matousek:Jir=iacute=.html">Jirí Matousek</a>: Reporting Points in Halfspaces. 207-215 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Matousek91">BibTeX</a></font> <li><a name="Orlitsky91" href="../../indices/a-tree/o/Orlitsky:Alon.html">Alon Orlitsky</a>: Interactive Communication: Balanced Distributions, Correlated Files, and Average-Case Complexity. 228-238 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Orlitsky91">BibTeX</a></font> <li><a name="FederKN91" href="../../indices/a-tree/f/Feder:Tom=aacute=s.html">Tomás Feder</a>, <a href="../../indices/a-tree/k/Kushilevitz:Eyal.html">Eyal Kushilevitz</a>, <a href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>: Amortized Communication Complexity (Preliminary Version). 239-248 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FederKN91">BibTeX</a></font> <li><a name="EdmondsRIS91" href="../../indices/a-tree/e/Edmonds:Jeff.html">Jeff Edmonds</a>, <a href="../../indices/a-tree/r/Rudich:Steven.html">Steven Rudich</a>, <a href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/s/Sgall:Jiri.html">Jiri Sgall</a>: Communication Complexity Towards Lower Bounds on Circuit Depth. 249-257 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/EdmondsRIS91">BibTeX</a></font> <li><a name="AwerbuchV91" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/v/Varghese:George.html">George Varghese</a>: Distributed Program Checking: a Paradigm for Building Self-stabilizing Distributed Protocols (Extended Abstract). 258-267 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchV91">BibTeX</a></font> <li><a name="AwerbuchPV91" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/p/Patt=Shamir:Boaz.html">Boaz Patt-Shamir</a>, <a href="../../indices/a-tree/v/Varghese:George.html">George Varghese</a>: Self-Stabilization By Local Checking and Correction (Extended Abstract). 268-277 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchPV91">BibTeX</a></font> <li><a name="Wang91" href="../../indices/a-tree/w/Wang:Weiguo.html">Weiguo Wang</a>: An Asynchronous Two-Dimensional Self-Correcting Cellular Automaton. 278-285 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Wang91">BibTeX</a></font> <li><a name="FiatFKRRV91" href="../../indices/a-tree/f/Fiat:Amos.html">Amos Fiat</a>, <a href="../../indices/a-tree/f/Foster:Dean_P=.html">Dean P. Foster</a>, <a href="../../indices/a-tree/k/Karloff:Howard_J=.html">Howard J. Karloff</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>, <a href="../../indices/a-tree/v/Vishwanathan:Sundar.html">Sundar Vishwanathan</a>: Competitive Algorithms for Layered Graph Traversal. 288-297 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FiatFKRRV91">BibTeX</a></font> <li><a name="DengKP91" href="../../indices/a-tree/d/Deng:Xiaotie.html">Xiaotie Deng</a>, <a href="../../indices/a-tree/k/Kameda:Tiko.html">Tiko Kameda</a>, <a href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: How to Learn an Unknown Environment (Extended Abstract). 298-303 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DengKP91">BibTeX</a></font> <li><a name="Klein91" href="../../indices/a-tree/k/Klein:Rolf.html">Rolf Klein</a>: Walking an Unknown Street with Bounded Detour. 304-313 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Klein91">BibTeX</a></font> <li><a name="Radhakrishnan91" href="../../indices/a-tree/r/Radhakrishnan:Jaikumar.html">Jaikumar Radhakrishnan</a>: Better Bounds for Threshold Formulas. 314-323 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Radhakrishnan91">BibTeX</a></font> <li><a name="PatersonZ91" href="../../indices/a-tree/p/Paterson:Mike.html">Mike Paterson</a>, <a href="../../indices/a-tree/z/Zwick:Uri.html">Uri Zwick</a>: Shrinkage of de~Morgan formulae under restriction. 324-333 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PatersonZ91">BibTeX</a></font> <li><a name="BshoutyCE91" href="../../indices/a-tree/b/Bshouty:Nader_H=.html">Nader H. Bshouty</a>, <a href="../../indices/a-tree/c/Cleve:Richard.html">Richard Cleve</a>, <a href="../../indices/a-tree/e/Eberly:Wayne.html">Wayne Eberly</a>: Size-Depth Tradeoffs for Algebraic Formulae. 334-341 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BshoutyCE91">BibTeX</a></font> <li><a name="KapronC91" href="../../indices/a-tree/k/Kapron:Bruce_M=.html">Bruce M. Kapron</a>, <a href="../../indices/a-tree/c/Cook:Stephen_A=.html">Stephen A. Cook</a>: A New Characterization of Mehlhorn's Polynomial Time Functionals (Extended Abstract). 342-347 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KapronC91">BibTeX</a></font> <li><a name="Verma91" href="../../indices/a-tree/v/Verma:Rakesh_M=.html">Rakesh M. Verma</a>: A Theory of Using History for Equational Systems with Applications (Extended Abstract). 348-357 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Verma91">BibTeX</a></font> <li><a name="Klarlund91" href="../../indices/a-tree/k/Klarlund:Nils.html">Nils Klarlund</a>: Progress Measures for Complementation of omega-Automata with Applications to Temporal Logic. 358-367 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Klarlund91">BibTeX</a></font> <li><a name="EmersonJ91" href="../../indices/a-tree/e/Emerson:E=_Allen.html">E. Allen Emerson</a>, <a href="../../indices/a-tree/j/Jutla:Charanjit_S=.html">Charanjit S. Jutla</a>: Tree Automata, Mu-Calculus and Determinacy (Extended Abstract). 368-377 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/EmersonJ91">BibTeX</a></font> <li><a name="ShoupS91" href="../../indices/a-tree/s/Shoup:Victor.html">Victor Shoup</a>, <a href="../../indices/a-tree/s/Smolensky:Roman.html">Roman Smolensky</a>: Lower Bounds for Polynomial Evaluation and Interpolation Problems. 378-383 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ShoupS91">BibTeX</a></font> <li><a name="Gathen91" href="../../indices/a-tree/g/Gathen:Joachim_von_zur.html">Joachim von zur Gathen</a>: Efficient Exponentiation in Finite Fields (Extended Abstract). 384-391 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Gathen91">BibTeX</a></font> <li><a name="Morgenstern91" href="../../indices/a-tree/m/Morgenstern:Moshe.html">Moshe Morgenstern</a>: Explicit Construction of Natural Bounded Concentrators. 392-397 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Morgenstern91">BibTeX</a></font> <li><a name="Kahale91" href="../../indices/a-tree/k/Kahale:Nabil.html">Nabil Kahale</a>: Better Expansion for Ramanujan Graphs. 398-404 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Kahale91">BibTeX</a></font> <li><a name="EmirisC91" href="../../indices/a-tree/e/Emiris:Ioannis_Z=.html">Ioannis Z. Emiris</a>, <a href="../../indices/a-tree/c/Canny:John_F=.html">John F. Canny</a>: A General Approach to Removing Degeneracies. 405-413 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/EmirisC91">BibTeX</a></font> <li><a name="EdelsbrunnerT91" href="../../indices/a-tree/e/Edelsbrunner:Herbert.html">Herbert Edelsbrunner</a>, <a href="../../indices/a-tree/t/Tan:Tiow_Seng.html">Tiow Seng Tan</a>: A Quadratic Time Algorithm for The MinMax Length Triangulation (Extended Abstract). 414-423 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/EdelsbrunnerT91">BibTeX</a></font> <li><a name="MatousekWW91" href="../../indices/a-tree/m/Matousek:Jir=iacute=.html">Jirí Matousek</a>, <a href="../../indices/a-tree/w/Welzl:Emo.html">Emo Welzl</a>, <a href="../../indices/a-tree/w/Wernisch:Lorenz.html">Lorenz Wernisch</a>: Discrepancy and epsilon-approximations for bounded VC-dimension. 424-430 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MatousekWW91">BibTeX</a></font> <li><a name="DuZF91" href="../../indices/a-tree/d/Du:Ding=Zhu.html">Ding-Zhu Du</a>, <a href="../../indices/a-tree/z/Zhang:Yanjun.html">Yanjun Zhang</a>, <a href="../../indices/a-tree/f/Feng:Qing.html">Qing Feng</a>: On Better Heuristic for Euclidean Steiner Minimum Trees (Extended Abstract). 431-439 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DuZF91">BibTeX</a></font> <li><a name="AumannB91" href="../../indices/a-tree/a/Aumann:Yonatan.html">Yonatan Aumann</a>, <a href="../../indices/a-tree/b/Ben=Or:Michael.html">Michael Ben-Or</a>: Asymptotically Optimal PRAM Emulation on Faulty Hypercubes (Extended Abstract). 440-446 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AumannB91">BibTeX</a></font> <li><a name="GoldreichGL91" href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/l/Linial:Nathan.html">Nathan Linial</a>: Fault-tolerant Computation in the Full Information Model (Extended Abstract). 447-457 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldreichGL91">BibTeX</a></font> <li><a name="LeightonMP91" href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/m/Ma:Yuan.html">Yuan Ma</a>, <a href="../../indices/a-tree/p/Plaxton:C=_Greg.html">C. Greg Plaxton</a>: Highly Fault-Tolerant Sorting Circuits. 458-469 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LeightonMP91">BibTeX</a></font> <li><a name="LeightonS91" href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/s/Schwabe:Eric_J=.html">Eric J. Schwabe</a>: Efficient Algorithms for Dynamic Allocation of Distributed Memory. 470-479 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LeightonS91">BibTeX</a></font> <li><a name="AdlerB91" href="../../indices/a-tree/a/Adler:Ilan.html">Ilan Adler</a>, <a href="../../indices/a-tree/b/Beling:Peter_A=.html">Peter A. Beling</a>: Polynomial Algorithms for LP over a Subring of the Algebraic Integers with Applications to LP with Circulant Matrices. 480-487 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AdlerB91">BibTeX</a></font> <li><a name="Eppstein91" href="../../indices/a-tree/e/Eppstein:David.html">David Eppstein</a>: Dynamic Three-Dimensional Linear Programming. 488-494 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Eppstein91">BibTeX</a></font> <li><a name="PlotkinST91" 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>: Fast Approximation Algorithms for Fractional Packing and Covering Problems. 495-504 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PlotkinST91">BibTeX</a></font> <li><a name="AwerbuchS91" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/s/Schulman:Leonard_J=.html">Leonard J. Schulman</a>: The Maintenance of Common Data in a Distributed System. 505-514 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchS91">BibTeX</a></font> <li><a name="NaorR91" href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>, <a href="../../indices/a-tree/r/Roth:Ron_M=.html">Ron M. Roth</a>: Optimal File Sharing in Distributed Networks (Preliminary Version). 515-525 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NaorR91">BibTeX</a></font> <li><a name="HerlihySW91" href="../../indices/a-tree/h/Herlihy:Maurice.html">Maurice Herlihy</a>, <a href="../../indices/a-tree/s/Shavit:Nir.html">Nir Shavit</a>, <a href="../../indices/a-tree/w/Waarts:Orli.html">Orli Waarts</a>: Low Contention Linearizable Counting. 526-535 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HerlihySW91">BibTeX</a></font> <li><a name="MillerTV91" 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>, <a href="../../indices/a-tree/v/Vavasis:Stephen_A=.html">Stephen A. Vavasis</a>: A Unified Geometric Approach to Graph Separators. 538-547 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MillerTV91">BibTeX</a></font> <li><a name="HsuR91" href="../../indices/a-tree/h/Hsu:Tsan=sheng.html">Tsan-sheng Hsu</a>, <a href="../../indices/a-tree/r/Ramachandran:Vijaya.html">Vijaya Ramachandran</a>: A Linear Time Algorithm for Triconnectivity Augmentation (Extended Abstract). 548-559 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HsuR91">BibTeX</a></font> <li><a name="KargerKP91" href="../../indices/a-tree/k/Karger:David_R=.html">David R. Karger</a>, <a href="../../indices/a-tree/k/Koller:Daphne.html">Daphne Koller</a>, <a href="../../indices/a-tree/p/Phillips:Steven_J=.html">Steven J. Phillips</a>: Finding the Hidden Path: Time Bounds for All-Pairs Shortest Paths. 560-568 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KargerKP91">BibTeX</a></font> <li><a name="AlonGM91" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/m/Margalit:Oded.html">Oded Margalit</a>: On the Exponent of the All Pairs Shortest Path Problem. 569-575 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonGM91">BibTeX</a></font> <li><a name="LovaszNNW91" href="../../indices/a-tree/l/Lov=aacute=sz:L=aacute=szl=oacute=.html">László Lovász</a>, <a href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>, <a href="../../indices/a-tree/n/Newman:Ilan.html">Ilan Newman</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: Search Problems in the Decision Tree Model (Preliminary Version). 576-585 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LovaszNNW91">BibTeX</a></font> <li><a name="Alon91" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>: A parallel algorithmic version of the Local Lemma. 586-593 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Alon91">BibTeX</a></font> <li><a name="Gal91" href="../../indices/a-tree/g/G=aacute=l:Anna.html">Anna Gál</a>: Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates. 594-601 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Gal91">BibTeX</a></font> <li><a name="ReischukS91" href="../../indices/a-tree/r/Reischuk:R=uuml=diger.html">Rüdiger Reischuk</a>, <a href="../../indices/a-tree/s/Schmeltz:Bernd.html">Bernd Schmeltz</a>: Reliable Computation with Noisy Circuits and Decision Trees-A General n log n Lower Bound. 602-611 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ReischukS91">BibTeX</a></font> <li><a name="Sundar91" href="../../indices/a-tree/s/Sundar:Rajamani.html">Rajamani Sundar</a>: A Lower Bound for the Dictionary Problem under a Hashing Model. 612-621 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Sundar91">BibTeX</a></font> <li><a name="Ben-AmramG91" href="../../indices/a-tree/b/Ben=Amram:Amir_M=.html">Amir M. Ben-Amram</a>, <a href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>: Lower Bounds for Data Structure Problems on RAMs (Extended Abstract). 622-631 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ben-AmramG91">BibTeX</a></font> <li><a name="Frederickson91" href="../../indices/a-tree/f/Frederickson:Greg_N=.html">Greg N. Frederickson</a>: Ambivalent Data Structures for Dynamic 2-Edge-Connectivity and k Smallest Spanning Trees. 632-641 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Frederickson91">BibTeX</a></font> <li><a name="AnderssonO91" href="../../indices/a-tree/a/Andersson:Arne.html">Arne Andersson</a>, <a href="../../indices/a-tree/o/Ottmann:Thomas.html">Thomas Ottmann</a>: Faster Uniquely Represented Dictionaries. 642-649 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AnderssonO91">BibTeX</a></font> <li><a name="DonaldC91" href="../../indices/a-tree/d/Donald:Bruce_Randall.html">Bruce Randall Donald</a>, <a href="../../indices/a-tree/c/Chang:Davied_Renpan.html">Davied Renpan Chang</a>: On the Complexity of Computing the Homology Type of a Triangulation. 650-661 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DonaldC91">BibTeX</a></font> <li><a name="GrigorievK91" href="../../indices/a-tree/g/Grigoriev:Dima.html">Dima Grigoriev</a>, <a href="../../indices/a-tree/k/Karpinski:Marek.html">Marek Karpinski</a>: An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]. 662-669 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GrigorievK91">BibTeX</a></font> <li><a name="Blomer91" href="../../indices/a-tree/b/Bl=ouml=mer:Johannes.html">Johannes Blömer</a>: Computing Sums of Radicals in Polynomial Time. 670-677 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Blomer91">BibTeX</a></font> <li><a name="HuangI91" href="../../indices/a-tree/h/Huang:Ming=Deh_A=.html">Ming-Deh A. Huang</a>, <a href="../../indices/a-tree/i/Ierardi:Doug.html">Doug Ierardi</a>: Efficient Algorithms for the Riemann-Roch Problem and for Addition in the Jacobian of a Curve (Extended Abstract). 678-687 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HuangI91">BibTeX</a></font> <li><a name="JohnsonM91" href="../../indices/a-tree/j/Johnson:Donald_B=.html">Donald B. Johnson</a>, <a href="../../indices/a-tree/m/Metaxas:Panagiotis_Takis.html">Panagiotis Takis Metaxas</a>: Connected Components in O(\lg^3/2 |V|) Parallel Time for the CREW PRAM. 688-697 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/JohnsonM91">BibTeX</a></font> <li><a name="GilMV91" href="../../indices/a-tree/g/Gil:Joseph.html">Joseph Gil</a>, <a href="../../indices/a-tree/m/Matias:Yossi.html">Yossi Matias</a>, <a href="../../indices/a-tree/v/Vishkin:Uzi.html">Uzi Vishkin</a>: Towards a Theory of Nearly Constant Time Parallel Algorithms. 698-710 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GilMV91">BibTeX</a></font> <li><a name="Goodrich91" href="../../indices/a-tree/g/Goodrich:Michael_T=.html">Michael T. Goodrich</a>: Using Approximation Algorithms to Design Parallel Algorithms that May Ignore Processor Allocation (Preliminary Version). 711-722 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Goodrich91">BibTeX</a></font> <li><a name="Gazit91" href="../../indices/a-tree/g/Gazit:Hillel.html">Hillel Gazit</a>: A Deterministic Parallel Algorithm for Planar Graphs Isomorphism. 723-732 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Gazit91">BibTeX</a></font> <li><a name="BabaiF91" href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>, <a href="../../indices/a-tree/f/Friedl:Katalin.html">Katalin Friedl</a>: Approximate Representation Theory of Finite Groups. 733-742 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BabaiF91">BibTeX</a></font> <li><a name="SaranV91" href="../../indices/a-tree/s/Saran:Huzur.html">Huzur Saran</a>, <a href="../../indices/a-tree/v/Vazirani:Vijay_V=.html">Vijay V. Vazirani</a>: Finding k-cuts within Twice the Optimal. 743-751 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SaranV91">BibTeX</a></font> <li><a name="Shor91" href="../../indices/a-tree/s/Shor:Peter_W=.html">Peter W. Shor</a>: How to Pack Better than Best Fit: Tight Bounds for Average-Case On-Line Bin Packing. 752-759 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Shor91">BibTeX</a></font> <li><a name="AmirF91" href="../../indices/a-tree/a/Amir:Amihood.html">Amihood Amir</a>, <a href="../../indices/a-tree/f/Farach:Martin.html">Martin Farach</a>: Adaptive Dictionary Matching. 760-766 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AmirF91">BibTeX</a></font> <li><a name="MaassSS91" 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/Sontag:Eduardo_D=.html">Eduardo D. Sontag</a>: On the Computational Power of Sigmoid versus Boolean Threshold Circuits. 767-776 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MaassSS91">BibTeX</a></font> <li><a name="KrauseW91" href="../../indices/a-tree/k/Krause:Matthias.html">Matthias Krause</a>, <a href="../../indices/a-tree/w/Waack:Stephan.html">Stephan Waack</a>: Variation Ranks of Communication Matrices and Lower Bounds for Depth Two Circuits Having Symmetric Gates with Unbounded Fan-In. 777-782 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KrauseW91">BibTeX</a></font> <li><a name="BeigelT91" href="../../indices/a-tree/b/Beigel:Richard.html">Richard Beigel</a>, <a href="../../indices/a-tree/t/Tarui:Jun.html">Jun Tarui</a>: On ACC. 783-792 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BeigelT91">BibTeX</a></font> <li><a name="KanevskyTBC91" href="../../indices/a-tree/k/Kanevsky:Arkady.html">Arkady Kanevsky</a>, <a href="../../indices/a-tree/t/Tamassia:Roberto.html">Roberto Tamassia</a>, <a href="../../indices/a-tree/b/Battista:Giuseppe_Di.html">Giuseppe Di Battista</a>, <a href="../../indices/a-tree/c/Chen:Jianer.html">Jianer Chen</a>: On-Line Maintenance of the Four-Connected Components of a Graph (Extended Abstract). 793-801 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KanevskyTBC91">BibTeX</a></font> <li><a name="GuptaI91" href="../../indices/a-tree/g/Gupta:Arvind.html">Arvind Gupta</a>, <a href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>: Computing Planar Intertwines. 802-811 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GuptaI91">BibTeX</a></font> <li><a name="Gabow91" href="../../indices/a-tree/g/Gabow:Harold_N=.html">Harold N. Gabow</a>: Applications of a Poset Representation to Edge Connectivity and Graph Rigidity. 812-821 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Gabow91">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:26 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
