focs97.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>38. FOCS 1997: Miami Beach, Florida, USA</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>38. <a href="index.html">FOCS</a> 1997: Miami Beach, Florida, USA</h1> 38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997. IEEE Computer Society <h2>Session 1A</h2> <ul> <li><a name="GoldbergR97" href="../../indices/a-tree/g/Goldberg:Andrew_V=.html">Andrew V. Goldberg</a>, <a href="../../indices/a-tree/r/Rao:Satish.html">Satish Rao</a>: <br><b>Beyond the Flow Decomposition Barrier. </b>2-11<br><a href="http://computer.org/proceedings/focs/8197/81970002abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldbergR97">BibTeX</a></font> <li><a name="Thorup97" href="../../indices/a-tree/t/Thorup:Mikkel.html">Mikkel Thorup</a>: <br><b>Undirected Single Source Shortest Path in Linear Time. </b>12-21<br><a href="http://computer.org/proceedings/focs/8197/81970012abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Thorup97">BibTeX</a></font> <li><a name="Chazelle97" href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>: <br><b>A Faster Deterministic Algorithm for Minimum Spanning Trees. </b>22-31<br><a href="http://computer.org/proceedings/focs/8197/81970022abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Chazelle97">BibTeX</a></font> <li><a name="GoldbergR97a" href="../../indices/a-tree/g/Goldberg:Andrew_V=.html">Andrew V. Goldberg</a>, <a href="../../indices/a-tree/r/Rao:Satish.html">Satish Rao</a>: <br><b>Flows in Undirected Unit Capacity Networks. </b>32-34<br><a href="http://computer.org/proceedings/focs/8197/81970032abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldbergR97a">BibTeX</a></font> </ul> <h2>Session 1B: </h2> <ul> <li><a name="Koiran97" href="../../indices/a-tree/k/Koiran:Pascal.html">Pascal Koiran</a>: <br><b>Randomized and Deterministic Algorithms for the Dimension of Algebraic Varieties. </b>36-45<br><a href="http://computer.org/proceedings/focs/8197/81970036abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Koiran97">BibTeX</a></font> <li><a name="SanderS97" href="../../indices/a-tree/s/Sander:Tomas.html">Tomas Sander</a>, <a href="../../indices/a-tree/s/Shokrollahi:Mohammad_Amin.html">Mohammad Amin Shokrollahi</a>: <br><b>Deciding Properties of Polynomials Without Factoring. </b>46-55<br><a href="http://computer.org/proceedings/focs/8197/81970046abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SanderS97">BibTeX</a></font> <li><a name="Basu97" href="../../indices/a-tree/b/Basu:Saugata.html">Saugata Basu</a>: <br><b>An Improved Algorithm for Quantifier Elimination Over Real Closed Fields. </b>56-65<br><a href="http://computer.org/proceedings/focs/8197/81970056abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Basu97">BibTeX</a></font> <li><a name="KondacsW97" href="../../indices/a-tree/k/Kondacs:Attila.html">Attila Kondacs</a>, <a href="../../indices/a-tree/w/Watrous:John.html">John Watrous</a>: <br><b>On the Power of Quantum Finite State Automata. </b>66-75<br><a href="http://computer.org/proceedings/focs/8197/81970066abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KondacsW97">BibTeX</a></font> </ul> <h2>Invited Talk</h2> <ul> <li><a name="Pnueli97" href="../../indices/a-tree/p/Pnueli:Amir.html">Amir Pnueli</a>: <br><b>Two Decades of Temporal Logic: Achievements and Challenges (Abstract). </b>78<br><a href="http://computer.org/proceedings/focs/8197/81970078abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Pnueli97">BibTeX</a></font> </ul> <h2>Session 2A</h2> <ul> <li><a name="Havlicek97" href="../../indices/a-tree/h/Havlicek:John.html">John Havlicek</a>: <br><b>Computable Obstructions to Wait-free Computability. </b>80-89<br><a href="http://computer.org/proceedings/focs/8197/81970080abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Havlicek97">BibTeX</a></font> <li><a name="Gacs97" href="../../indices/a-tree/g/G=aacute=cs:P=eacute=ter.html">Péter Gács</a>: <br><b>Reliable Cellular Automata with Self-Organization. </b>90-99<br><a href="http://computer.org/proceedings/focs/8197/81970090abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Gacs97">BibTeX</a></font> <li><a name="AlurHK97" 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 href="../../indices/a-tree/k/Kupferman:Orna.html">Orna Kupferman</a>: <br><b>Alternating-time Temporal Logic. </b>100-109<br><a href="http://computer.org/proceedings/focs/8197/81970100abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlurHK97">BibTeX</a></font> <li><a name="LiptonMN97" href="../../indices/a-tree/l/Lipton:Richard_J=.html">Richard J. Lipton</a>, <a href="../../indices/a-tree/m/Martino:Paul_J=.html">Paul J. Martino</a>, <a href="../../indices/a-tree/n/Neitzke:Andy.html">Andy Neitzke</a>: <br><b>On the Complexity of a Set-Union Problem. </b>110-115<br><a href="http://computer.org/proceedings/focs/8197/81970110abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LiptonMN97">BibTeX</a></font> </ul> <h2>Session 2B</h2> <ul> <li><a name="MunroR97" href="../../indices/a-tree/m/Munro:J=_Ian.html">J. Ian Munro</a>, <a href="../../indices/a-tree/r/Raman:Venkatesh.html">Venkatesh Raman</a>: <br><b>Succinct Representation of Balanced Parentheses, Static Trees and Planar Graphs. </b>118-126<br><a href="http://computer.org/proceedings/focs/8197/81970118abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MunroR97">BibTeX</a></font> <li><a name="Indyk97" href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>: <br><b>Deterministic Superimposed Coding with Applications to Pattern Matching. </b>127-136<br><a href="http://computer.org/proceedings/focs/8197/81970127abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Indyk97">BibTeX</a></font> <li><a name="Farach97" href="../../indices/a-tree/f/Farach:Martin.html">Martin Farach</a>: <br><b>Optimal Suffix Tree Construction with Large Alphabets. </b>137-143<br><a href="http://computer.org/proceedings/focs/8197/81970137abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Farach97">BibTeX</a></font> <li><a name="AmirALLL97" href="../../indices/a-tree/a/Amir:Amihood.html">Amihood Amir</a>, <a href="../../indices/a-tree/a/Aumann:Yonatan.html">Yonatan Aumann</a>, <a href="../../indices/a-tree/l/Landau:Gad_M=.html">Gad M. Landau</a>, <a href="../../indices/a-tree/l/Lewenstein:Moshe.html">Moshe Lewenstein</a>, <a href="../../indices/a-tree/l/Lewenstein:Noa.html">Noa Lewenstein</a>: <br><b>Pattern Matching with Swaps. </b>144-153<br><a href="http://computer.org/proceedings/focs/8197/81970144abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AmirALLL97">BibTeX</a></font> </ul> <h2>Session 3A</h2> <ul> <li><a name="Dey97" href="../../indices/a-tree/d/Dey:Tamal_K=.html">Tamal K. Dey</a>: <br><b>Improved Bounds on Planar k-sets and k-levels. </b>165-161<br><a href="http://computer.org/proceedings/focs/8197/81970156abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Dey97">BibTeX</a></font> <li><a name="KhachiyanP97" href="../../indices/a-tree/k/Khachiyan:Leonid.html">Leonid Khachiyan</a>, <a href="../../indices/a-tree/p/Porkolab:Lorant.html">Lorant Porkolab</a>: <br><b>Computing Integral Points in Convex Semi-algebraic Sets. </b>162-171<br><a href="http://computer.org/proceedings/focs/8197/81970162abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KhachiyanP97">BibTeX</a></font> <li><a name="HassLP97" href="../../indices/a-tree/h/Hass:Joel.html">Joel Hass</a>, <a href="../../indices/a-tree/l/Lagarias:J=_C=.html">J. C. Lagarias</a>, <a href="../../indices/a-tree/p/Pippenger:Nicholas.html">Nicholas Pippenger</a>: <br><b>The Computational Complexity of Knot and Link Problems. </b>172-181<br><a href="http://computer.org/proceedings/focs/8197/81970172abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HassLP97">BibTeX</a></font> <li><a name="VaradarajanA97" href="../../indices/a-tree/v/Varadarajan:Kasturi_R=.html">Kasturi R. Varadarajan</a>, <a href="../../indices/a-tree/a/Agarwal:Pankaj_K=.html">Pankaj K. Agarwal</a>: <br><b>Approximating Shortest Paths on an Nonconvex Polyhedron. </b>182-191<br><a href="http://computer.org/proceedings/focs/8197/81970182abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/VaradarajanA97">BibTeX</a></font> </ul> <h2>Session 3B</h2> <ul> <li><a name="CzumajS97" href="../../indices/a-tree/c/Czumaj:Artur.html">Artur Czumaj</a>, <a href="../../indices/a-tree/s/Stemann:Volker.html">Volker Stemann</a>: <br><b>Randomized Allocation Processes. </b>194-203<br><a href="http://computer.org/proceedings/focs/8197/81970194abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CzumajS97">BibTeX</a></font> <li><a name="AchlioptasM97" href="../../indices/a-tree/a/Achlioptas:Dimitris.html">Dimitris Achlioptas</a>, <a href="../../indices/a-tree/m/Molloy:Michael_S=_O=.html">Michael S. O. Molloy</a>: <br><b>The Analysis of a List-Coloring Algorithm on a Random Graph. </b>204-212<br><a href="http://computer.org/proceedings/focs/8197/81970204abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AchlioptasM97">BibTeX</a></font> <li><a name="GoldbergM97" href="../../indices/a-tree/g/Goldberg:Leslie_Ann.html">Leslie Ann Goldberg</a>, <a href="../../indices/a-tree/m/MacKenzie:Philip_D=.html">Philip D. MacKenzie</a>: <br><b>Contention Resolution with Guaranteed Constant Expected Delay. </b>213-222<br><a href="http://computer.org/proceedings/focs/8197/81970213abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldbergM97">BibTeX</a></font> <li><a name="BubleyD97" href="../../indices/a-tree/b/Bubley:Russ.html">Russ Bubley</a>, <a href="../../indices/a-tree/d/Dyer:Martin_E=.html">Martin E. Dyer</a>: <br><b>Path Coupling: A Technique for Proving Rapid Mixing in Markov Chains. </b>223-231<br><a href="http://computer.org/proceedings/focs/8197/81970223abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BubleyD97">BibTeX</a></font> </ul> <h2>Session 4A</h2> <ul> <li><a name="RazM97" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>, <a href="../../indices/a-tree/m/McKenzie:Pierre.html">Pierre McKenzie</a>: <br><b>Separation of the Monotone NC Hierarchy. </b>234-243<br><a href="http://computer.org/proceedings/focs/8197/81970234abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RazM97">BibTeX</a></font> <li><a name="ReinhardtA97" href="../../indices/a-tree/r/Reinhardt:Klaus.html">Klaus Reinhardt</a>, <a href="../../indices/a-tree/a/Allender:Eric.html">Eric Allender</a>: <br><b>Making Nondeterminism Unambiguous. </b>244-253<br><a href="http://computer.org/proceedings/focs/8197/81970244abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ReinhardtA97">BibTeX</a></font> <li><a name="BonetPR97" href="../../indices/a-tree/b/Bonet:Maria_Luisa.html">Maria Luisa Bonet</a>, <a href="../../indices/a-tree/p/Pitassi:Toniann.html">Toniann Pitassi</a>, <a href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>: <br><b>No Feasible Interpolation for TC0-Frege Proofs. </b>254-263<br><a href="http://computer.org/proceedings/focs/8197/81970254abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BonetPR97">BibTeX</a></font> <li><a name="AndreevCRT97" href="../../indices/a-tree/a/Andreev:Alexander_E=.html">Alexander E. Andreev</a>, <a href="../../indices/a-tree/c/Clementi:Andrea_E=_F=.html">Andrea E. F. Clementi</a>, <a href="../../indices/a-tree/r/Rolim:Jos=eacute=_D=_P=.html">José D. P. Rolim</a>, <a href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>: <br><b>Weak Random Sources, Hitting Sets, and BPP Simulations. </b>264-272<br><a href="http://computer.org/proceedings/focs/8197/81970264abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AndreevCRT97">BibTeX</a></font> </ul> <h2>Session 4B</h2> <ul> <li><a name="BornsteinMMR97" href="../../indices/a-tree/b/Bornstein:Claudson_F=.html">Claudson F. Bornstein</a>, <a href="../../indices/a-tree/m/Maggs:Bruce_M=.html">Bruce M. Maggs</a>, <a href="../../indices/a-tree/m/Miller:Gary_L=.html">Gary L. Miller</a>, <a href="../../indices/a-tree/r/Ravi:R=.html">R. Ravi</a>: <br><b>Parallelizing Elimination Orders with Linear Fill. </b>274-283<br><a href="http://computer.org/proceedings/focs/8197/81970274abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BornsteinMMR97">BibTeX</a></font> <li><a name="MaggsHVW97" href="../../indices/a-tree/m/Maggs:Bruce_M=.html">Bruce M. Maggs</a>, <a href="../../indices/a-tree/h/Heide:Friedhelm_Meyer_auf_der.html">Friedhelm Meyer auf der Heide</a>, <a href="../../indices/a-tree/v/V=ouml=cking:Berthold.html">Berthold Vöcking</a>, <a href="../../indices/a-tree/w/Westermann:Matthias.html">Matthias Westermann</a>: <br><b>Exploiting Locality for Data Management in Systems of Limited Bandwidth. </b>284-293<br><a href="http://computer.org/proceedings/focs/8197/81970284abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MaggsHVW97">BibTeX</a></font> <li><a name="AndrewsFHLZ97" href="../../indices/a-tree/a/Andrews:Matthew.html">Matthew Andrews</a>, <a href="../../indices/a-tree/f/Fern=aacute=ndez:Antonio.html">Antonio Fernández</a>, <a href="../../indices/a-tree/h/Harchol=Balter:Mor.html">Mor Harchol-Balter</a>, <a href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/z/Zhang:Lisa.html">Lisa Zhang</a>: <br><b>General Dynamic Routing with Per-Packet Delay Guarantees of O(distance + 1 / session rate). </b>294-302<br><a href="http://computer.org/proceedings/focs/8197/81970294abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AndrewsFHLZ97">BibTeX</a></font> <li><a name="BartalBR97" href="../../indices/a-tree/b/Bartal:Yair.html">Yair Bartal</a>, <a href="../../indices/a-tree/b/Byers:John_W=.html">John W. Byers</a>, <a href="../../indices/a-tree/r/Raz:Danny.html">Danny Raz</a>: <br><b>Global Optimization Using Local Information with Applications to Flow Control. </b>303-312<br><a href="http://computer.org/proceedings/focs/8197/81970303abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BartalBR97">BibTeX</a></font> </ul> <h2>Invited Talk</h2> <ul> <li><a name="Goldwasser97" href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>: <br><b>New Directions in Cryptography: Twenty Some Years Later. </b>314-324<br><a href="http://computer.org/proceedings/focs/8197/81970314abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Goldwasser97">BibTeX</a></font> </ul> <h2>Session 5A</h2> <ul> <li><a name="FiatM97" href="../../indices/a-tree/f/Fiat:Amos.html">Amos Fiat</a>, <a href="../../indices/a-tree/m/Mendel:Manor.html">Manor Mendel</a>: <br><b>Truly Online Paging with Locality of Reference. </b>326-335<br><a href="http://computer.org/proceedings/focs/8197/81970326abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FiatM97">BibTeX</a></font> <li><a name="al-Binali97" href="../../indices/a-tree/a/al=Binali:Sabah.html">Sabah al-Binali</a>: <br><b>The Competitive Analysis of Risk Taking with Applications to Online Trading. </b>336-344<br><a href="http://computer.org/proceedings/focs/8197/81970336abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/al-Binali97">BibTeX</a></font> <li><a name="KalyanasundaramP97" href="../../indices/a-tree/k/Kalyanasundaram:Bala.html">Bala Kalyanasundaram</a>, <a href="../../indices/a-tree/p/Pruhs:Kirk.html">Kirk Pruhs</a>: <br><b>Minimizing Flow Time Nonclairvoyantly. </b>345-352<br><a href="http://computer.org/proceedings/focs/8197/81970345abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KalyanasundaramP97">BibTeX</a></font> <li><a name="KleinbergMRV97" href="../../indices/a-tree/k/Kleinberg:Jon_M=.html">Jon M. Kleinberg</a>, <a href="../../indices/a-tree/m/Motwani:Rajeev.html">Rajeev Motwani</a>, <a href="../../indices/a-tree/r/Raghavan:Prabhakar.html">Prabhakar Raghavan</a>, <a href="../../indices/a-tree/v/Venkatasubramanian:Suresh.html">Suresh Venkatasubramanian</a>: <br><b>Storage Management for Evolving Databases. </b>353-362<br><a href="http://computer.org/proceedings/focs/8197/81970353abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KleinbergMRV97">BibTeX</a></font> </ul> <h2>Session 5B</h2> <ul> <li><a name="KushilevitzO97" href="../../indices/a-tree/k/Kushilevitz:Eyal.html">Eyal Kushilevitz</a>, <a href="../../indices/a-tree/o/Ostrovsky:Rafail.html">Rafail Ostrovsky</a>: <br><b>Replication is NOT Needed: SINGLE Database, Computationally-Private Information Retrieval. </b>364-373<br><a href="http://computer.org/proceedings/focs/8197/81970364abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KushilevitzO97">BibTeX</a></font> <li><a name="BellareIN97" href="../../indices/a-tree/b/Bellare:Mihir.html">Mihir Bellare</a>, <a href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>: <br><b>Does Parallel Repetition Lower the Error in Computationally Sound Protocols? </b>374-383<br><a href="http://computer.org/proceedings/focs/8197/81970374abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BellareIN97">BibTeX</a></font> <li><a name="FrankelGMY97" href="../../indices/a-tree/f/Frankel:Yair.html">Yair Frankel</a>, <a href="../../indices/a-tree/g/Gemmell:Peter.html">Peter Gemmell</a>, <a href="../../indices/a-tree/m/MacKenzie:Philip_D=.html">Philip D. MacKenzie</a>, <a href="../../indices/a-tree/y/Yung:Moti.html">Moti Yung</a>: <br><b>Optimal Resilience Proactive Public-Key Cryptosystems. </b>384-393<br><a href="http://computer.org/proceedings/focs/8197/81970384abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FrankelGMY97">BibTeX</a></font> <li><a name="BellareDJR97" href="../../indices/a-tree/b/Bellare:Mihir.html">Mihir Bellare</a>, <a href="../../indices/a-tree/d/Desai:Anand.html">Anand Desai</a>, <a href="../../indices/a-tree/j/Jokipii:E=.html">E. Jokipii</a>, <a href="../../indices/a-tree/r/Rogaway:Phillip.html">Phillip Rogaway</a>: <br><b>A Concrete Security Treatment of Symmetric Encryption. </b>394-403<br><a href="http://computer.org/proceedings/focs/8197/81970394abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BellareDJR97">BibTeX</a></font> </ul> <h2>Session 6A</h2> <ul> <li><a name="KarloffZ97" href="../../indices/a-tree/k/Karloff:Howard_J=.html">Howard J. Karloff</a>, <a href="../../indices/a-tree/z/Zwick:Uri.html">Uri Zwick</a>: <br><b>A 7/8-Approximation Algorithm for MAX 3SAT? </b>406-415<br><a href="http://computer.org/proceedings/focs/8197/81970406abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KarloffZ97">BibTeX</a></font> <li><a name="Srinivasan97" href="../../indices/a-tree/s/Srinivasan:Aravind.html">Aravind Srinivasan</a>: <br><b>Improved Approximations for Edge-Disjoint Paths, Unsplittable Flow, and Related Routing Problems. </b>416-425<br><a href="http://computer.org/proceedings/focs/8197/81970416abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Srinivasan97">BibTeX</a></font> <li><a name="KolliopoulosS97" href="../../indices/a-tree/k/Kolliopoulos:Stavros_G=.html">Stavros G. Kolliopoulos</a>, <a href="../../indices/a-tree/s/Stein:Clifford.html">Clifford Stein</a>: <br><b>Improved Approximation Algorithms for Unsplittable Flow Problems. </b>426-435<br><a href="http://computer.org/proceedings/focs/8197/81970426abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KolliopoulosS97">BibTeX</a></font> </ul> <h2>Session 6B</h2> <ul> <li><a name="Fischlin97" href="../../indices/a-tree/f/Fischlin:Marc.html">Marc Fischlin</a>: <br><b>Lower Bounds for the Signature Size of Incremental Schemes. </b>438-447<br><a href="http://computer.org/proceedings/focs/8197/81970438abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Fischlin97">BibTeX</a></font> <li><a name="SahaiV97" href="../../indices/a-tree/s/Sahai:Amit.html">Amit Sahai</a>, <a href="../../indices/a-tree/v/Vadhan:Salil_P=.html">Salil P. Vadhan</a>: <br><b>A Complete Promise Problem for Statistical Zero-Knowledge. </b>448-457<br><a href="http://computer.org/proceedings/focs/8197/81970448abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SahaiV97">BibTeX</a></font> <li><a name="NaorR97" href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>, <a href="../../indices/a-tree/r/Reingold:Omer.html">Omer Reingold</a>: <br><b>Number-theoretic Constructions of Efficient Pseudo-random Functions. </b>458-467<br><a href="http://computer.org/proceedings/focs/8197/81970458abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NaorR97">BibTeX</a></font> <li><a name="CaiN97" href="../../indices/a-tree/c/Cai:Jin=yi.html">Jin-yi Cai</a>, <a href="../../indices/a-tree/n/Nerurkar:Ajay.html">Ajay Nerurkar</a>: <br><b>An Improved Worst-Case to Average-Case Connection for Lattice Problems. </b>468-477<br><a href="http://computer.org/proceedings/focs/8197/81970468abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CaiN97">BibTeX</a></font> </ul> <h2>Session 7A</h2> <ul> <li><a name="ConfortiCKV97" href="../../indices/a-tree/c/Conforti:Michele.html">Michele Conforti</a>, <a href="../../indices/a-tree/c/Cornu=eacute=jols:G=eacute=rard.html">Gérard Cornuéjols</a>, <a href="../../indices/a-tree/k/Kapoor:Ajai.html">Ajai Kapoor</a>, <a href="../../indices/a-tree/v/Vuskovic:Kristina.html">Kristina Vuskovic</a>: <br><b>Finding an Even Hole in a Graph. </b>480-485<br><a href="http://computer.org/proceedings/focs/8197/81970480abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ConfortiCKV97">BibTeX</a></font> <li><a name="Bang-JensenJ97" href="../../indices/a-tree/b/Bang=Jensen:J=oslash=rgen.html">Jørgen Bang-Jensen</a>, <a href="../../indices/a-tree/j/Jord=aacute=n:Tibor.html">Tibor Jordán</a>: <br><b>Edge-Connectivity Augmentation Preserving Simplicity. </b>486-495<br><a href="http://computer.org/proceedings/focs/8197/81970486abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Bang-JensenJ97">BibTeX</a></font> <li><a name="UmansL97" href="../../indices/a-tree/u/Umans:Christopher.html">Christopher Umans</a>, <a href="../../indices/a-tree/l/Lenhart:William.html">William Lenhart</a>: <br><b>Hamiltonian Cycles in Solid Grid Graphs. </b>496-505<br><a href="http://computer.org/proceedings/focs/8197/81970496abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/UmansL97">BibTeX</a></font> </ul> <h2>Session 7B</h2> <ul> <li><a name="Vempala97" href="../../indices/a-tree/v/Vempala:Santosh.html">Santosh Vempala</a>: <br><b>A Random Sampling Based Algorithm for Learning the Intersection of Half-spaces. </b>508-513<br><a href="http://computer.org/proceedings/focs/8197/81970508abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Vempala97">BibTeX</a></font> <li><a name="Cohen97" href="../../indices/a-tree/c/Cohen:Edith.html">Edith Cohen</a>: <br><b>Learning Noisy Perceptrons by a Perceptron in Polynomial Time. </b>514-523<br><a href="http://computer.org/proceedings/focs/8197/81970514abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Cohen97">BibTeX</a></font> <li><a name="AmbainisDFK97" href="../../indices/a-tree/a/Ambainis:Andris.html">Andris Ambainis</a>, <a href="../../indices/a-tree/d/Desper:Richard.html">Richard Desper</a>, <a href="../../indices/a-tree/f/Farach:Martin.html">Martin Farach</a>, <a href="../../indices/a-tree/k/Kannan:Sampath.html">Sampath Kannan</a>: <br><b>Nearly Tight Bounds on the Learnability of Evolution. </b>524-533<br><a href="http://computer.org/proceedings/focs/8197/81970524abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AmbainisDFK97">BibTeX</a></font> </ul> <h2>Session 8A</h2> <ul> <li><a name="NaorS97" href="../../indices/a-tree/n/Naor:Joseph.html">Joseph Naor</a>, <a href="../../indices/a-tree/s/Schieber:Baruch.html">Baruch Schieber</a>: <br><b>Improved Approximations for Shallow-Light Spanning Trees. </b>536-541<br><a href="http://computer.org/proceedings/focs/8197/81970536abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NaorS97">BibTeX</a></font> <li><a name="AwerbuchA97" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/a/Azar:Yossi.html">Yossi Azar</a>: <br><b>Buy-at-Bulk Network Design. </b>542-547<br><a href="http://computer.org/proceedings/focs/8197/81970542abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchA97">BibTeX</a></font> <li><a name="NaorZ97" href="../../indices/a-tree/n/Naor:Joseph.html">Joseph Naor</a>, <a href="../../indices/a-tree/z/Zosin:Leonid.html">Leonid Zosin</a>: <br><b>A 2-Approximation Algorithm for the Directed Multiway Cut Problem. </b>548-553<br><a href="http://computer.org/proceedings/focs/8197/81970548abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NaorZ97">BibTeX</a></font> <li><a name="Arora97" href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>: <br><b>Nearly Linear Time Approximation Schemes for Euclidean TSP and other Geometric Problems. </b>554-563<br><a href="http://computer.org/proceedings/focs/8197/81970554abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Arora97">BibTeX</a></font> </ul> <h2>Session 8B</h2> <ul> <li><a name="PaturiPZ97" href="../../indices/a-tree/p/Paturi:Ramamohan.html">Ramamohan Paturi</a>, <a href="../../indices/a-tree/p/Pudl=aacute=k:Pavel.html">Pavel Pudlák</a>, <a href="../../indices/a-tree/z/Zane:Francis.html">Francis Zane</a>: <br><b>Satisfiability Coding Lemma. </b>566-574<br><a href="http://computer.org/proceedings/focs/8197/81970566abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PaturiPZ97">BibTeX</a></font> <li><a name="HemaspaandraW97" href="../../indices/a-tree/h/Hemaspaandra:Edith.html">Edith Hemaspaandra</a>, <a href="../../indices/a-tree/w/Wechsung:Gerd.html">Gerd Wechsung</a>: <br><b>The Minimization Problem for Boolean Formulas. </b>575-584<br><a href="http://computer.org/proceedings/focs/8197/81970575abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HemaspaandraW97">BibTeX</a></font> <li><a name="RadhakrishnanT97" href="../../indices/a-tree/r/Radhakrishnan:Jaikumar.html">Jaikumar Radhakrishnan</a>, <a href="../../indices/a-tree/t/Ta=Shma:Amnon.html">Amnon Ta-Shma</a>: <br><b>Tight Bounds for Depth-two Superconcentrators. </b>585-594<br><a href="http://computer.org/proceedings/focs/8197/81970585abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RadhakrishnanT97">BibTeX</a></font> <li><a name="CaiSS97" href="../../indices/a-tree/c/Cai:Jin=yi.html">Jin-yi Cai</a>, <a href="../../indices/a-tree/s/Sivakumar:D=.html">D. Sivakumar</a>, <a href="../../indices/a-tree/s/Strauss:Martin.html">Martin Strauss</a>: <br><b>Constant Depth Circuits and the Lutz Hypothesis. </b>595-604<br><a href="http://computer.org/proceedings/focs/8197/81970595abs.htm"><i>Electronic Edition</i></a> (<a href="http://www.computer.org/publications/dlib/index.htm">IEEE Computer Society DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CaiSS97">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
