focs98.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>39. FOCS 1998: Palo Alto, California</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>39. <a href="index.html">FOCS</a> 1998: Palo Alto, California, USA</h1> 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8-11, 1998, Palo Alto, California, USA. IEEE Computer Society, 1998 <h2>Tutorial I</h2> <ul> <li><a name="Matousek98" href="../../indices/a-tree/m/Matousek:Jir=iacute=.html">Jirí Matousek</a>: <br><b>Geometric Computation and the Art of Sampling. </b>2<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720002.pdf"><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/Matousek98">BibTeX</a></font> </ul> <h2>Tutorial II</h2> <ul> <li><a name="Kearns98" href="../../indices/a-tree/k/Kearns:Michael_J=.html">Michael J. Kearns</a>: <br><b>Theoretical Issues in Probabilistic Artificial Intelligence. </b>4<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720004.pdf"><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/Kearns98">BibTeX</a></font> </ul> <h2>Tutorial III</h2> <ul> <li><a name="BroderH98" href="../../indices/a-tree/b/Broder:Andrei_Z=.html">Andrei Z. Broder</a>, <a href="../../indices/a-tree/h/Henzinger:Monika_Rauch.html">Monika Rauch Henzinger</a>: <br><b>Information Retrieval on the Web. </b>6<br><a href="http://computer.org/conferen/proceed/focs/9172/91720006abs.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/BroderH98">BibTeX</a></font> </ul> <h2>Session 1A</h2> <ul> <li><a name="GuruswamiLST98" href="../../indices/a-tree/g/Guruswami:Venkatesan.html">Venkatesan Guruswami</a>, <a href="../../indices/a-tree/l/Lewin:Daniel.html">Daniel Lewin</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>, <a href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>: <br><b>A Tight Characterization of NP with 3 Query PCPs. </b>8-17<br><a href="http://computer.org/conferen/proceed/focs/9172/91720008abs.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/GuruswamiLST98">BibTeX</a></font> <li><a name="SudanT98" href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>, <a href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>: <br><b>Probabilistically Checkable Proofs with Low Amortized Query Complexity. </b>18-27<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720018.pdf"><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/SudanT98">BibTeX</a></font> <li><a name="GuruswamiS98" href="../../indices/a-tree/g/Guruswami:Venkatesan.html">Venkatesan Guruswami</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: <br><b>Improved Decoding of Reed-Solomon and Algebraic-Geometric Codes. </b>28-39<br><a href="http://computer.org/conferen/proceed/focs/9172/91720028abs.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/GuruswamiS98">BibTeX</a></font> </ul> <h2>Session 1B</h2> <ul> <li><a name="AndrewsZ98" href="../../indices/a-tree/a/Andrews:Matthew.html">Matthew Andrews</a>, <a href="../../indices/a-tree/z/Zhang:Lisa.html">Lisa Zhang</a>: <br><b>The Access Network Design Problem. </b>40-59<br><a href="http://computer.org/conferen/proceed/focs/9172/91720040abs.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/AndrewsZ98">BibTeX</a></font> <li><a name="MansourP98" href="../../indices/a-tree/m/Mansour:Yishay.html">Yishay Mansour</a>, <a href="../../indices/a-tree/p/Patt=Shamir:Boaz.html">Boaz Patt-Shamir</a>: <br><b>Jitter Control in QoS Networks. </b>50-59<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720050.pdf"><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/MansourP98">BibTeX</a></font> <li><a name="Gamarnik98" href="../../indices/a-tree/g/Gamarnik:David.html">David Gamarnik</a>: <br><b>Stability of Adversarial Queues via Fluid Models. </b>60-70<br><a href="http://computer.org/conferen/proceed/focs/9172/91720060abs.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/Gamarnik98">BibTeX</a></font> <li><a name="AlbersCM98" href="../../indices/a-tree/a/Albers:Susanne.html">Susanne Albers</a>, <a href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/m/Mitzenmacher:Michael.html">Michael Mitzenmacher</a>: <br><b>Delayed Information and Action in On-line Algorithms. </b>71-81<br><a href="http://computer.org/conferen/proceed/focs/9172/91720071abs.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/AlbersCM98">BibTeX</a></font> </ul> <h2>Session 2A</h2> <ul> <li><a name="Unger98" href="../../indices/a-tree/u/Unger:Walter.html">Walter Unger</a>: <br><b>The Complexity of the Approximation of the Bandwidth Problem. </b>82-91<br><a href="http://computer.org/conferen/proceed/focs/9172/91720082abs.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/Unger98">BibTeX</a></font> <li><a name="Micciancio98" href="../../indices/a-tree/m/Micciancio:Daniele.html">Daniele Micciancio</a>: <br><b>The Shortest Vector in a Lattice is Hard to Approximate to Within Some Constant. </b>92-98<br><a href="http://computer.org/conferen/proceed/focs/9172/91720092abs.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/Micciancio98">BibTeX</a></font> <li><a name="DinurKS98" href="../../indices/a-tree/d/Dinur:Irit.html">Irit Dinur</a>, <a href="../../indices/a-tree/k/Kindler:Guy.html">Guy Kindler</a>, <a href="../../indices/a-tree/s/Safra:Shmuel.html">Shmuel Safra</a>: <br><b>Approximating-CVP to Within Almost-Polynomial Factors is NP-Hard. </b>99-111<br><a href="http://computer.org/conferen/proceed/focs/9172/91720099abs.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/DinurKS98">BibTeX</a></font> </ul> <h2>Session 2B</h2> <ul> <li><a name="Gutierrez98" href="../../indices/a-tree/g/Guti=eacute=rrez:Claudio.html">Claudio Gutiérrez</a>: <br><b>Satisfiability of Word Equations with Constants is in Exponential Space. </b>112-119<br><a href="http://computer.org/conferen/proceed/focs/9172/91720112abs.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/Gutierrez98">BibTeX</a></font> <li><a name="Senizergues98" href="../../indices/a-tree/s/S=eacute=nizergues:G=eacute=raud.html">Géraud Sénizergues</a>: <br><b>Decidability of Bisimulation Equivalence for Equational Graphs of Finite Out-Degree. </b>120-129<br><a href="http://computer.org/conferen/proceed/focs/9172/91720120abs.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/Senizergues98">BibTeX</a></font> <li><a name="Bouziane98" href="../../indices/a-tree/b/Bouziane:Zakaria.html">Zakaria Bouziane</a>: <br><b>A Primitive Recursive Algorithm for the General Petri Net Reachability Problem. </b>130-136<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720130.pdf"><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/Bouziane98">BibTeX</a></font> <li><a name="Szegedy98" href="../../indices/a-tree/s/Szegedy:Mario.html">Mario Szegedy</a>: <br><b>Algorithms to Tile the Infinite Grid with Finite Clusters. </b>137-147<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720137.pdf"><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/Szegedy98">BibTeX</a></font> </ul> <h2>Session 3A</h2> <ul> <li><a name="Indyk98" href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>: <br><b>On Approximate Nearest Neighbors in Non-Euclidean Spaces. </b>148-155<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720148.pdf"><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/Indyk98">BibTeX</a></font> <li><a name="CardozeS98" href="../../indices/a-tree/c/Cardoze:David_E=.html">David E. Cardoze</a>, <a href="../../indices/a-tree/s/Schulman:Leonard_J=.html">Leonard J. Schulman</a>: <br><b>Pattern Matching for Spatial Point Sets. </b>156-165<br><a href="http://computer.org/conferen/proceed/focs/9172/91720156abs.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/CardozeS98">BibTeX</a></font> <li><a name="Indyk98a" href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>: <br><b>Faster Algorithms for String Matching Problems: Matching the Convolution Bound. </b>166-173<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720166.pdf"><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/Indyk98a">BibTeX</a></font> <li><a name="FarachFM98" href="../../indices/a-tree/f/Farach:Martin.html">Martin Farach</a>, <a href="../../indices/a-tree/f/Ferragina:Paolo.html">Paolo Ferragina</a>, <a href="../../indices/a-tree/m/Muthukrishnan:S=.html">S. Muthukrishnan</a>: <br><b>Overcoming the Memory Bottleneck in Suffix Tree Construction. </b>174-185<br><a href="http://computer.org/conferen/proceed/focs/9172/91720174abs.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/FarachFM98">BibTeX</a></font> </ul> <h2>Session 3B</h2> <ul> <li><a name="Blaser98" href="../../indices/a-tree/b/Bl=auml=ser:Markus.html">Markus Bläser</a>: <br><b>Bivariate Polynomial Multiplication. </b>186-191<br><a href="http://computer.org/conferen/proceed/focs/9172/91720186abs.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/Blaser98">BibTeX</a></font> <li><a name="OlshevskyP98" href="../../indices/a-tree/o/Olshevsky:Vadim.html">Vadim Olshevsky</a>, <a href="../../indices/a-tree/p/Pan:Victor_Y=.html">Victor Y. Pan</a>: <br><b>A Unified Superfast Algorithm for Boundary Rational Tangential Interpolation Problems and for Inversion and Factorization of Dense Structured Matrices. </b>192-201<br><a href="http://computer.org/conferen/proceed/focs/9172/91720192abs.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/OlshevskyP98">BibTeX</a></font> <li><a name="Woods98" href="../../indices/a-tree/w/Woods:Alan_R=.html">Alan R. Woods</a>: <br><b>Unsatisfiable Systems of Equations, Over a Finite Field. </b>202-211<br><a href="http://computer.org/conferen/proceed/focs/9172/91720202abs.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/Woods98">BibTeX</a></font> <li><a name="Schonhage98" href="../../indices/a-tree/s/Sch=ouml=nhage:Arnold.html">Arnold Schönhage</a>: <br><b>Multiplicative Complexity of Taylor Shifts and a New Twist of the Substitution Method. </b>212-217<br><a href="http://computer.org/conferen/proceed/focs/9172/91720212abs.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/Schonhage98">BibTeX</a></font> </ul> <h2>Session 4A</h2> <ul> <li><a name="KannanN98" href="../../indices/a-tree/k/Kannan:Ravi.html">Ravi Kannan</a>, <a href="../../indices/a-tree/n/Nolte:Andreas.html">Andreas Nolte</a>: <br><b>Local Search in Smooth Convex Sets. </b>218-226<br><a href="http://computer.org/conferen/proceed/focs/9172/91720218abs.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/KannanN98">BibTeX</a></font> <li><a name="CaiDZ98" href="../../indices/a-tree/c/Cai:Mao=cheng.html">Mao-cheng Cai</a>, <a href="../../indices/a-tree/d/Deng:Xiaotie.html">Xiaotie Deng</a>, <a href="../../indices/a-tree/z/Zang:Wenan.html">Wenan Zang</a>: <br><b>A TDI System and its Application to Approximation Algorithms. </b>227-243<br><a href="http://computer.org/conferen/proceed/focs/9172/91720227abs.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/CaiDZ98">BibTeX</a></font> <li><a name="SmithW98" href="../../indices/a-tree/s/Smith:Warren_D=.html">Warren D. Smith</a>, <a href="../../indices/a-tree/w/Wormald:Nicholas_C=.html">Nicholas C. Wormald</a>: <br><b>Geometric Separator Theorems & Applications. </b>232-243<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720232.pdf"><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/SmithW98">BibTeX</a></font> <li><a name="BriedenGKKLS98" href="../../indices/a-tree/b/Brieden:Andreas.html">Andreas Brieden</a>, <a href="../../indices/a-tree/g/Gritzmann:Peter.html">Peter Gritzmann</a>, <a href="../../indices/a-tree/k/Kannan:Ravi.html">Ravi Kannan</a>, <a href="../../indices/a-tree/k/Klee:Victor.html">Victor Klee</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/Simonovits:Mikl=oacute=s.html">Miklós Simonovits</a>: <br><b>Approximation of Diameters: Randomization Doesn't Help. </b>244-251<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720244.pdf"><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/BriedenGKKLS98">BibTeX</a></font> </ul> <h2>Session 4B</h2> <ul> <li><a name="BeameST98" href="../../indices/a-tree/b/Beame:Paul.html">Paul Beame</a>, <a href="../../indices/a-tree/s/Saks:Michael_E=.html">Michael E. Saks</a>, <a href="../../indices/a-tree/t/Thathachar:Jayram_S=.html">Jayram S. Thathachar</a>: <br><b>Time-Space Tradeoffs for Branching Programs. </b>254-263<br><a href="http://computer.org/conferen/proceed/focs/9172/91720254abs.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/BeameST98">BibTeX</a></font> <li><a name="PagterR98" href="../../indices/a-tree/p/Pagter:Jakob.html">Jakob Pagter</a>, <a href="../../indices/a-tree/r/Rauhe:Theis.html">Theis Rauhe</a>: <br><b>Optimal Time-Space Trade-Offs for Sorting. </b>264-268<br><a href="http://computer.org/conferen/proceed/focs/9172/91720264abs.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/PagterR98">BibTeX</a></font> <li><a name="GrigorievR98" href="../../indices/a-tree/g/Grigoriev:Dima.html">Dima Grigoriev</a>, <a href="../../indices/a-tree/r/Razborov:Alexander_A=.html">Alexander A. Razborov</a>: <br><b>Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields. </b>269-278<br><a href="http://computer.org/conferen/proceed/focs/9172/91720269abs.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/GrigorievR98">BibTeX</a></font> <li><a name="GrolmuszT98" href="../../indices/a-tree/g/Grolmusz:Vince.html">Vince Grolmusz</a>, <a href="../../indices/a-tree/t/Tardos:G=aacute=bor.html">Gábor Tardos</a>: <br><b>Lower Bounds for (MOD p - MOD m) Circuits. </b>279-289<br><a href="http://computer.org/conferen/proceed/focs/9172/91720279abs.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/GrolmuszT98">BibTeX</a></font> </ul> <h2>Session 5A</h2> <ul> <li><a name="DinitzGG98" href="../../indices/a-tree/d/Dinitz:Yefim.html">Yefim Dinitz</a>, <a href="../../indices/a-tree/g/Garg:Naveen.html">Naveen Garg</a>, <a href="../../indices/a-tree/g/Goemans:Michel_X=.html">Michel X. Goemans</a>: <br><b>On the Single-Source Unsplittable Flow Problem. </b>290-299<br><a href="http://computer.org/conferen/proceed/focs/9172/91720290abs.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/DinitzGG98">BibTeX</a></font> <li><a name="GargK98" href="../../indices/a-tree/g/Garg:Naveen.html">Naveen Garg</a>, <a href="../../indices/a-tree/k/K=ouml=nemann:Jochen.html">Jochen Könemann</a>: <br><b>Faster and Simpler Algorithms for Multicommodity Flow and Other Fractional Packing Problems. </b>300-309<br><a href="http://computer.org/conferen/proceed/focs/9172/91720300abs.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/GargK98">BibTeX</a></font> <li><a name="Zwick98" href="../../indices/a-tree/z/Zwick:Uri.html">Uri Zwick</a>: <br><b>All Pairs Shortest Paths in Weighted Directed Graphs ¾ Exact and Almost Exact Algorithms. </b>310-319<br><a href="http://computer.org/conferen/proceed/focs/9172/91720310abs.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/Zwick98">BibTeX</a></font> <li><a name="Varadarajan98" href="../../indices/a-tree/v/Varadarajan:Kasturi_R=.html">Kasturi R. Varadarajan</a>: <br><b>A Divide-and-Conquer Algorithm for Min-Cost Perfect Matching in the Plane. </b>320-331<br><a href="http://computer.org/conferen/proceed/focs/9172/91720320abs.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/Varadarajan98">BibTeX</a></font> </ul> <h2>Session 5B</h2> <ul> <li><a name="AmbainisF98" href="../../indices/a-tree/a/Ambainis:Andris.html">Andris Ambainis</a>, <a href="../../indices/a-tree/f/Freivalds:Rusins.html">Rusins Freivalds</a>: <br><b>1-Way Quantum Finite Automata: Strengths, Weaknesses and Generalizations. </b>332-341<br><a href="http://computer.org/conferen/proceed/focs/9172/91720332abs.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/AmbainisF98">BibTeX</a></font> <li><a name="AmbainisSTVW98" href="../../indices/a-tree/a/Ambainis:Andris.html">Andris Ambainis</a>, <a href="../../indices/a-tree/s/Schulman:Leonard_J=.html">Leonard J. Schulman</a>, <a href="../../indices/a-tree/t/Ta=Shma:Amnon.html">Amnon Ta-Shma</a>, <a href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>The Quantum Communication Complexity of Sampling. </b>342-351<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720342.pdf"><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/AmbainisSTVW98">BibTeX</a></font> <li><a name="BealsBCMW98" href="../../indices/a-tree/b/Beals:Robert.html">Robert Beals</a>, <a href="../../indices/a-tree/b/Buhrman:Harry.html">Harry Buhrman</a>, <a href="../../indices/a-tree/c/Cleve:Richard.html">Richard Cleve</a>, <a href="../../indices/a-tree/m/Mosca:Michele.html">Michele Mosca</a>, <a href="../../indices/a-tree/w/Wolf:Ronald_de.html">Ronald de Wolf</a>: <br><b>Quantum Lower Bounds by Polynomials. </b>352-361<br><a href="http://computer.org/conferen/proceed/focs/9172/91720352abs.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/BealsBCMW98">BibTeX</a></font> <li><a name="Dam98" href="../../indices/a-tree/d/Dam:Wim_van.html">Wim van Dam</a>: <br><b>Quantum Oracle Interrogation: Getting All Information for Almost Half the Price. </b>362-367<br><a href="http://computer.org/conferen/proceed/focs/9172/91720362abs.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/Dam98">BibTeX</a></font> </ul> <h2>Session 6A</h2> <ul> <li><a name="FriezeKV98" href="../../indices/a-tree/f/Frieze:Alan_M=.html">Alan M. Frieze</a>, <a href="../../indices/a-tree/k/Kannan:Ravi.html">Ravi Kannan</a>, <a href="../../indices/a-tree/v/Vempala:Santosh.html">Santosh Vempala</a>: <br><b>Fast Monte-Carlo Algorithms for Finding Low-Rank Approximations. </b>370-378<br><a href="http://computer.org/conferen/proceed/focs/9172/91720370abs.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/FriezeKV98">BibTeX</a></font> <li><a name="CharikarCGGP98" href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/c/Chekuri:Chandra.html">Chandra Chekuri</a>, <a href="../../indices/a-tree/g/Goel:Ashish.html">Ashish Goel</a>, <a href="../../indices/a-tree/g/Guha:Sudipto.html">Sudipto Guha</a>, <a href="../../indices/a-tree/p/Plotkin:Serge_A=.html">Serge A. Plotkin</a>: <br><b>Approximating a Finite Metric by a Small Number of Tree Metrics. </b>379-388<br><a href="http://computer.org/conferen/proceed/focs/9172/91720379abs.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/CharikarCGGP98">BibTeX</a></font> <li><a name="Vempala98" href="../../indices/a-tree/v/Vempala:Santosh.html">Santosh Vempala</a>: <br><b>Random Projection: A New Approach to VLSI Layout. </b>389-395<br><a href="http://computer.org/conferen/proceed/focs/9172/91720389abs.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/Vempala98">BibTeX</a></font> <li><a name="Thorup98" href="../../indices/a-tree/t/Thorup:Mikkel.html">Mikkel Thorup</a>: <br><b>Map Graphs in Polynomial Time. </b>396-405<br><a href="http://computer.org/conferen/proceed/focs/9172/91720396abs.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/Thorup98">BibTeX</a></font> </ul> <h2>Session 6B</h2> <ul> <li><a name="BlumBL98" href="../../indices/a-tree/b/Blum:Avrim.html">Avrim Blum</a>, <a href="../../indices/a-tree/b/Burch:Carl.html">Carl Burch</a>, <a href="../../indices/a-tree/l/Langford:John.html">John Langford</a>: <br><b>On Learning Monotone Boolean Functions. </b>408-415<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720408.pdf"><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/BlumBL98">BibTeX</a></font> <li><a name="JiangKL98" href="../../indices/a-tree/j/Jiang:Tao.html">Tao Jiang</a>, <a href="../../indices/a-tree/k/Kearney:Paul_E=.html">Paul E. Kearney</a>, <a href="../../indices/a-tree/l/Li:Ming.html">Ming Li</a>: <br><b>Orchestrating Quartets: Approximation and Data Correction. </b>416-425<br><a href="http://computer.org/conferen/proceed/focs/9172/91720416abs.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/JiangKL98">BibTeX</a></font> <li><a name="GoldreichGLR98" 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/Lehman:Eric.html">Eric Lehman</a>, <a href="../../indices/a-tree/r/Ron:Dana.html">Dana Ron</a>: <br><b>Testing Monotonicity. </b>426-435<br><a href="http://computer.org/conferen/proceed/focs/9172/91720426abs.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/GoldreichGLR98">BibTeX</a></font> <li><a name="CryanGG98" href="../../indices/a-tree/c/Cryan:Mary.html">Mary Cryan</a>, <a href="../../indices/a-tree/g/Goldberg:Leslie_Ann.html">Leslie Ann Goldberg</a>, <a href="../../indices/a-tree/g/Goldberg:Paul_W=.html">Paul W. Goldberg</a>: <br><b>Evolutionary Trees can be Learned in Polynomial Time in the Two-State General Markov Model. </b>436-445<br><a href="http://computer.org/conferen/proceed/focs/9172/91720436abs.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/CryanGG98">BibTeX</a></font> </ul> <h2>Session 7A</h2> <ul> <li><a name="Jain98" href="../../indices/a-tree/j/Jain:Kamal.html">Kamal Jain</a>: <br><b>Factor 2 Approximation Algorithm for the Generalized Steiner Network Problem. </b>448-457<br><a href="http://computer.org/conferen/proceed/focs/9172/91720448abs.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/Jain98">BibTeX</a></font> <li><a name="CharikarR98" href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/r/Raghavachari:Balaji.html">Balaji Raghavachari</a>: <br><b>The Finite Capacity Dial-A-Ride Problem. </b>458-467<br><a href="http://computer.org/conferen/proceed/focs/9172/91720458abs.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/CharikarR98">BibTeX</a></font> <li><a name="VegaK98" href="../../indices/a-tree/v/Vega:Wenceslas_Fernandez_de_la.html">Wenceslas Fernandez de la Vega</a>, <a href="../../indices/a-tree/k/Kenyon:Claire.html">Claire Kenyon</a>: <br><b>A Randomized Approximation Scheme for Metric MAX-CUT. </b>468-471<br><a href="http://computer.org/conferen/proceed/focs/9172/91720468abs.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/VegaK98">BibTeX</a></font> <li><a name="Skutella98" href="../../indices/a-tree/s/Skutella:Martin.html">Martin Skutella</a>: <br><b>Semidefinite Relaxations for Parallel Machine Scheduling. </b>472-481<br><a href="http://computer.org/conferen/proceed/focs/9172/91720472abs.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/Skutella98">BibTeX</a></font> </ul> <h2>Session 7B</h2> <ul> <li><a name="KilianPR98" href="../../indices/a-tree/k/Kilian:Joe.html">Joe Kilian</a>, <a href="../../indices/a-tree/p/Petrank:Erez.html">Erez Petrank</a>, <a href="../../indices/a-tree/r/Rackoff:Charles.html">Charles Rackoff</a>: <br><b>Lower Bounds for Zero Knowledge on the Internet. </b>484-492<br><a href="http://computer.org/conferen/proceed/focs/9172/91720484abs.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/KilianPR98">BibTeX</a></font> <li><a name="CachinCM98" href="../../indices/a-tree/c/Cachin:Christian.html">Christian Cachin</a>, <a href="../../indices/a-tree/c/Cr=eacute=peau:Claude.html">Claude Crépeau</a>, <a href="../../indices/a-tree/m/Marcil:Julien.html">Julien Marcil</a>: <br><b>Oblivious Transfer with a Memory-Bounded Receiver. </b>493-502<br><a href="http://computer.org/conferen/proceed/focs/9172/91720493abs.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/CachinCM98">BibTeX</a></font> <li><a name="MayersY98" href="../../indices/a-tree/m/Mayers:Dominic.html">Dominic Mayers</a>, <a href="../../indices/a-tree/y/Yao:Andrew_Chi=Chih.html">Andrew Chi-Chih Yao</a>: <br><b>Quantum Cryptography with Imperfect Apparatus. </b>503-509<br><a href="http://computer.org/conferen/proceed/focs/9172/91720503abs.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/MayersY98">BibTeX</a></font> <li><a name="HastadN98" href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>, <a href="../../indices/a-tree/n/N=auml=slund:Mats.html">Mats Näslund</a>: <br><b>The Security of Individual RSA Bits. </b>510-521<br><a href="http://computer.org/conferen/proceed/focs/9172/91720510abs.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/HastadN98">BibTeX</a></font> </ul> <h2>Session 8A</h2> <ul> <li><a name="AdlerM98" href="../../indices/a-tree/a/Adler:Micah.html">Micah Adler</a>, <a href="../../indices/a-tree/m/Maggs:Bruce_M=.html">Bruce M. Maggs</a>: <br><b>Protocols for Asymmetric Communication Channels. </b>522-533<br><a href="http://computer.org/conferen/proceed/focs/9172/91720522abs.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/AdlerM98">BibTeX</a></font> <li><a name="AlstrupHR98" href="../../indices/a-tree/a/Alstrup:Stephen.html">Stephen Alstrup</a>, <a href="../../indices/a-tree/h/Husfeldt:Thore.html">Thore Husfeldt</a>, <a href="../../indices/a-tree/r/Rauhe:Theis.html">Theis Rauhe</a>: <br><b>Marked Ancestor Problems. </b>534-544<br><a href="http://computer.org/conferen/proceed/focs/9172/91720534abs.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/AlstrupHR98">BibTeX</a></font> <li><a name="CarterG98" href="../../indices/a-tree/c/Carter:Larry.html">Larry Carter</a>, <a href="../../indices/a-tree/g/Gatlin:Kang_Su.html">Kang Su Gatlin</a>: <br><b>Towards an Optimal Bit-Reversal Permutation Program. </b>544-555<br><a href="http://computer.org/conferen/proceed/focs/9172/91720544abs.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/CarterG98">BibTeX</a></font> </ul> <h2>Session 8B</h2> <ul> <li><a name="Umans98" href="../../indices/a-tree/u/Umans:Christopher.html">Christopher Umans</a>: <br><b>The Minimum Equivalent DNF Problem and Shortest Implicants. </b>556-563<br><a href="http://computer.org/conferen/proceed/focs/9172/91720556abs.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/Umans98">BibTeX</a></font> <li><a name="AlfaroHK98" href="../../indices/a-tree/a/Alfaro:Luca_de.html">Luca de Alfaro</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>Concurrent Reachability Games. </b>564-575<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720564.pdf"><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/AlfaroHK98">BibTeX</a></font> <li><a name="RussellZ98" href="../../indices/a-tree/r/Russell:Alexander.html">Alexander Russell</a>, <a href="../../indices/a-tree/z/Zuckerman:David.html">David Zuckerman</a>: <br><b>Perfect Information Leader Election in log*<i>n</i> + <i>O</i>(1) Rounds. </b>576-583<br><a href="http://computer.org/conferen/proceed/focs/9172/91720576abs.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/RussellZ98">BibTeX</a></font> </ul> <h2>Session 9A</h2> <ul> <li><a name="Chan98" href="../../indices/a-tree/c/Chan:Timothy_M=.html">Timothy M. Chan</a>: <br><b>Sampling, Halfspace Range Reporting, and Construction of (<= k)-Levels in Three Dimensions. </b>586-595<br><a href="http://computer.org/conferen/proceed/focs/9172/91720586abs.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/Chan98">BibTeX</a></font> <li><a name="AgarwalEGH98" href="../../indices/a-tree/a/Agarwal:Pankaj_K=.html">Pankaj K. Agarwal</a>, <a href="../../indices/a-tree/e/Eppstein:David.html">David Eppstein</a>, <a href="../../indices/a-tree/g/Guibas:Leonidas_J=.html">Leonidas J. Guibas</a>, <a href="../../indices/a-tree/h/Henzinger:Monika_Rauch.html">Monika Rauch Henzinger</a>: <br><b>Parametric and Kinetic Minimum Spanning Trees. </b>596-605<br><a href="http://computer.org/conferen/proceed/focs/9172/91720596abs.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/AgarwalEGH98">BibTeX</a></font> <li><a name="Basu98" href="../../indices/a-tree/b/Basu:Saugata.html">Saugata Basu</a>: <br><b>On the Combinatorial and Topological Complexity of a Single Cell. </b>606-616<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720606.pdf"><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/Basu98">BibTeX</a></font> <li><a name="PachT98" href="../../indices/a-tree/p/Pach:J=aacute=nos.html">János Pach</a>, <a href="../../indices/a-tree/t/T=oacute=th:G=eacute=za.html">Géza Tóth</a>: <br><b>Which Crossing Number is it, Anyway? </b>617-627<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720617.pdf"><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/PachT98">BibTeX</a></font> </ul> <h2>Session 9B</h2> <ul> <li><a name="PaturiPSZ98" 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/s/Saks:Michael_E=.html">Michael E. Saks</a>, <a href="../../indices/a-tree/z/Zane:Francis.html">Francis Zane</a>: <br><b>An Improved Exponential-Time Algorithm for <i>k</i>-SAT. </b>628-637<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720628.pdf"><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/PaturiPSZ98">BibTeX</a></font> <li><a name="BonetEGJ98" href="../../indices/a-tree/b/Bonet:Maria_Luisa.html">Maria Luisa Bonet</a>, <a href="../../indices/a-tree/e/Esteban:Juan_Luis.html">Juan Luis Esteban</a>, <a href="../../indices/a-tree/g/Galesi:Nicola.html">Nicola Galesi</a>, <a href="../../indices/a-tree/j/Johannsen:Jan.html">Jan Johannsen</a>: <br><b>Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems. </b>638-647<br><a href="http://computer.org/conferen/proceed/focs/9172/91720638abs.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/BonetEGJ98">BibTeX</a></font> <li><a name="Grigoriev98" href="../../indices/a-tree/g/Grigoriev:Dima.html">Dima Grigoriev</a>: <br><b>Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs. </b>648-652<br><a href="http://computer.org/conferen/proceed/focs/9172/91720648abs.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/Grigoriev98">BibTeX</a></font> <li><a name="ImpagliazzoPZ98" href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/p/Paturi:Ramamohan.html">Ramamohan Paturi</a>, <a href="../../indices/a-tree/z/Zane:Francis.html">Francis Zane</a>: <br><b>Which Problems Have Strongly Exponential Complexity? </b>653-663<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720653.pdf"><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/ImpagliazzoPZ98">BibTeX</a></font> </ul> <h2>Session 10A</h2> <ul> <li><a name="KumarRRT98" href="../../indices/a-tree/k/Kumar:Ravi.html">Ravi Kumar</a>, <a href="../../indices/a-tree/r/Raghavan:Prabhakar.html">Prabhakar Raghavan</a>, <a href="../../indices/a-tree/r/Rajagopalan:Sridhar.html">Sridhar Rajagopalan</a>, <a href="../../indices/a-tree/t/Tomkins:Andrew.html">Andrew Tomkins</a>: <br><b>Recommendation Systems: A Probabilistic Analysis. </b>664-673<br><a href="http://computer.org/conferen/proceed/focs/9172/91720664abs.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/KumarRRT98">BibTeX</a></font> <li><a name="FeigeK98" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>, <a href="../../indices/a-tree/k/Kilian:Joe.html">Joe Kilian</a>: <br><b>Heuristics for Finding Large Independent Sets, with Applications to Coloring Semi-Random Graphs. </b>674-683<br><a href="http://computer.org/conferen/proceed/focs/9172/91720674abs.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/FeigeK98">BibTeX</a></font> <li><a name="RadhakrishnanS98" href="../../indices/a-tree/r/Radhakrishnan:Jaikumar.html">Jaikumar Radhakrishnan</a>, <a href="../../indices/a-tree/s/Srinivasan:Aravind.html">Aravind Srinivasan</a>: <br><b>Improved Bounds and Algorithms for Hypergraph Two-Coloring. </b>684-693<br><a href="http://computer.org/conferen/proceed/focs/9172/91720684abs.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/RadhakrishnanS98">BibTeX</a></font> <li><a name="RabaniSW98" href="../../indices/a-tree/r/Rabani:Yuval.html">Yuval Rabani</a>, <a href="../../indices/a-tree/s/Sinclair:Alistair.html">Alistair Sinclair</a>, <a href="../../indices/a-tree/w/Wanka:Rolf.html">Rolf Wanka</a>: <br><b>Local Divergence of Markov Chains and the Analysis of Iterative Load Balancing Schemes. </b>694-705<br><a href="http://computer.org/conferen/proceed/focs/9172/91720694abs.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/RabaniSW98">BibTeX</a></font> </ul> <h2>Session 10B</h2> <ul> <li><a name="GottlobLS98" href="../../indices/a-tree/g/Gottlob:Georg.html">Georg Gottlob</a>, <a href="../../indices/a-tree/l/Leone:Nicola.html">Nicola Leone</a>, <a href="../../indices/a-tree/s/Scarcello:Francesco.html">Francesco Scarcello</a>: <br><b>The Complexity of Acyclic Conjunctive Queries. </b>706-715<br><a href="http://computer.org/conferen/proceed/focs/9172/91720706abs.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/GottlobLS98">BibTeX</a></font> <li><a name="Leivant98" href="../../indices/a-tree/l/Leivant:Daniel.html">Daniel Leivant</a>: <br><b>A Characterization of NC by Tree Recurrence. </b>716-724<br><a href="http://computer.org/conferen/proceed/focs/9172/91720716abs.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/Leivant98">BibTeX</a></font> <li><a name="MitchellMS98" href="../../indices/a-tree/m/Mitchell:John_C=.html">John C. Mitchell</a>, <a href="../../indices/a-tree/m/Mitchell:Mark.html">Mark Mitchell</a>, <a href="../../indices/a-tree/s/Scedrov:Andre.html">Andre Scedrov</a>: <br><b>A Linguistic Characterization of Bounded Oracle Computation and Probabilistic Polynomial Time. </b>725-733<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720725.pdf"><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/MitchellMS98">BibTeX</a></font> <li><a name="ImpagliazzoW98" href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>Randomness vs. Time: De-Randomization under a Uniform Assumption. </b>734-743<br><a href="http://dlib.computer.org/conferen/focs/9172/pdf/91720734.pdf"><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/ImpagliazzoW98">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
