stoc1997.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>STOC 1997</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>29. <a href="index.html">STOC</a> 1997: El Paso, Texas, USA</h1> Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997. ACM, 1997, ISBN 0-89791-888-6 <h2>Session 1A</h2> <ul> <li><a name="Hastad97" href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>: <br><b>Some Optimal Inapproximability Results. </b>1-10<br><a href="http://doi.acm.org/10.1145/258533.258536"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Hastad97">BibTeX</a></font> <li><a name="KhannaSW97" href="../../indices/a-tree/k/Khanna:Sanjeev.html">Sanjeev Khanna</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>, <a href="../../indices/a-tree/w/Williamson:David_P=.html">David P. Williamson</a>: <br><b>A Complete Classification of the Approximability of Maximization Problems Derived from Boolean Constraint Satisfaction. </b>11-20<br><a href="http://doi.acm.org/10.1145/258533.258538"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KhannaSW97">BibTeX</a></font> <li><a name="Trevisan97" href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>: <br><b>When Hamming Meets Euclid: The Approximability of Geometric TSP and MST (Extended Abstract). </b>21-29<br><a href="http://doi.acm.org/10.1145/258533.258541"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Trevisan97">BibTeX</a></font> </ul> <h2>Session 1B</h2> <ul> <li><a name="Reif97" href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>: <br><b>Approximate Complex Polynomial Evaluation in Near Constant Work Per Point. </b>30-39<br><a href="http://doi.acm.org/10.1145/258533.258543"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Reif97">BibTeX</a></font> <li><a name="BuhlerSS97" href="../../indices/a-tree/b/Buhler:Joe.html">Joe Buhler</a>, <a href="../../indices/a-tree/s/Shokrollahi:Mohammad_Amin.html">Mohammad Amin Shokrollahi</a>, <a href="../../indices/a-tree/s/Stemann:Volker.html">Volker Stemann</a>: <br><b>Fast and Precise Computations of Discrete Fourier Transforms Using Cyclotomic Integers. </b>40-47<br><a href="http://doi.acm.org/10.1145/258533.258545"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BuhlerSS97">BibTeX</a></font> <li><a name="Beals97" href="../../indices/a-tree/b/Beals:Robert.html">Robert Beals</a>: <br><b>Quantum Computation of Fourier Transforms over Symmetric Groups. </b>48-53<br><a href="http://doi.acm.org/10.1145/258533.258548"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Beals97">BibTeX</a></font> </ul> <h2>Session 2A</h2> <ul> <li><a name="KaoLPST97" href="../../indices/a-tree/k/Kao:Ming=Yang.html">Ming-Yang Kao</a>, <a href="../../indices/a-tree/l/Lam:Tak_Wah.html">Tak Wah Lam</a>, <a href="../../indices/a-tree/p/Przytycka:Teresa_M=.html">Teresa M. Przytycka</a>, <a href="../../indices/a-tree/s/Sung:Wing=Kin.html">Wing-Kin Sung</a>, <a href="../../indices/a-tree/t/Ting:Hing=Fung.html">Hing-Fung Ting</a>: <br><b>General Techniques for Comparing Unrooted Evolutionary Trees. </b>54-65<br><a href="http://doi.acm.org/10.1145/258533.258550"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KaoLPST97">BibTeX</a></font> <li><a name="ColeH97" href="../../indices/a-tree/c/Cole:Richard.html">Richard Cole</a>, <a href="../../indices/a-tree/h/Hariharan:Ramesh.html">Ramesh Hariharan</a>: <br><b>Tree Pattern Matching and Subset Matching in Randomized O(n log<sup>3</sup>m) Time. </b>66-75<br><a href="http://doi.acm.org/10.1145/258533.258553"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ColeH97">BibTeX</a></font> </ul> <h2>Session 2B</h2> <ul> <li><a name="GrigorievK97" href="../../indices/a-tree/g/Grigoriev:Dima.html">Dima Grigoriev</a>, <a href="../../indices/a-tree/k/Karpinski:Marek.html">Marek Karpinski</a>: <br><b>Randomized Omega(n<sup>2</sup>) Lower Bound for Knapsack. </b>76-85<br><a href="http://doi.acm.org/10.1145/258533.258555"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GrigorievK97">BibTeX</a></font> <li><a name="PaturiSZ97" href="../../indices/a-tree/p/Paturi:Ramamohan.html">Ramamohan Paturi</a>, <a href="../../indices/a-tree/s/Saks:Michael_E=.html">Michael E. Saks</a>, <a href="../../indices/a-tree/z/Zane:Francis.html">Francis Zane</a>: <br><b>Exponential Lower Bounds for Depth 3 Boolean Circuits. </b>86-91<br><a href="http://doi.acm.org/10.1145/258533.258556"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/PaturiSZ97">BibTeX</a></font> </ul> <h2>Invited Session I</h2> <ul> <li><a name="Vardy97" href="../../indices/a-tree/v/Vardy:Alexander.html">Alexander Vardy</a>: <br><b>Algorithmic Complexity in Coding Theory and the Minimum Distance Problem. </b>92-109<br><a href="http://doi.acm.org/10.1145/258533.258559"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Vardy97">BibTeX</a></font> </ul> <h2>Session 3A</h2> <ul> <li><a name="LeonardiR97" href="../../indices/a-tree/l/Leonardi:Stefano.html">Stefano Leonardi</a>, <a href="../../indices/a-tree/r/Raz:Danny.html">Danny Raz</a>: <br><b>Approximating Total Flow Time on Parallel Machines. </b>110-119<br><a href="http://doi.acm.org/10.1145/258533.258562"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LeonardiR97">BibTeX</a></font> <li><a name="EdmondsCBD97" href="../../indices/a-tree/e/Edmonds:Jeff.html">Jeff Edmonds</a>, <a href="../../indices/a-tree/c/Chinn:Donald_D=.html">Donald D. Chinn</a>, <a href="../../indices/a-tree/b/Brecht:Tim.html">Tim Brecht</a>, <a href="../../indices/a-tree/d/Deng:Xiaotie.html">Xiaotie Deng</a>: <br><b>Non-clairvoyant Multiprocessor Scheduling of Jobs with Changing Execution Characteristics (Extended Abstract). </b>120-129<br><a href="http://doi.acm.org/10.1145/258533.258565"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/EdmondsCBD97">BibTeX</a></font> <li><a name="Albers97" href="../../indices/a-tree/a/Albers:Susanne.html">Susanne Albers</a>: <br><b>Better Bounds for Online Scheduling. </b>130-139<br><a href="http://doi.acm.org/10.1145/258533.258566"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Albers97">BibTeX</a></font> <li><a name="PhillipsSTW97" href="../../indices/a-tree/p/Phillips:Cynthia_A=.html">Cynthia A. Phillips</a>, <a href="../../indices/a-tree/s/Stein:Clifford.html">Clifford Stein</a>, <a href="../../indices/a-tree/t/Torng:Eric.html">Eric Torng</a>, <a href="../../indices/a-tree/w/Wein:Joel.html">Joel Wein</a>: <br><b>Optimal Time-Critical Scheduling via Resource Augmentation (Extended Abstract). </b>140-149<br><a href="http://doi.acm.org/10.1145/258533.258570"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/PhillipsSTW97">BibTeX</a></font> </ul> <h2>Session 3B</h2> <ul> <li><a name="LubyMSSS97" href="../../indices/a-tree/l/Luby:Michael.html">Michael Luby</a>, <a href="../../indices/a-tree/m/Mitzenmacher:Michael.html">Michael Mitzenmacher</a>, <a href="../../indices/a-tree/s/Shokrollahi:Mohammad_Amin.html">Mohammad Amin Shokrollahi</a>, <a href="../../indices/a-tree/s/Spielman:Daniel_A=.html">Daniel A. Spielman</a>, <a href="../../indices/a-tree/s/Stemann:Volker.html">Volker Stemann</a>: <br><b>Practical Loss-Resilient Codes. </b>150-159<br><a href="http://doi.acm.org/10.1145/258533.258573"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LubyMSSS97">BibTeX</a></font> <li><a name="LaffertyR97" href="../../indices/a-tree/l/Lafferty:John_D=.html">John D. Lafferty</a>, <a href="../../indices/a-tree/r/Rockmore:Daniel_N=.html">Daniel N. Rockmore</a>: <br><b>Spectral Techniques for Expander Codes. </b>160-167<br><a href="http://doi.acm.org/10.1145/258533.258575"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LaffertyR97">BibTeX</a></font> <li><a name="Pan97" href="../../indices/a-tree/p/Pan:Victor_Y=.html">Victor Y. Pan</a>: <br><b>Faster Solution of the Key Equation for Decoding BCH Error-Correcting Codes. </b>168-175<br><a href="http://doi.acm.org/10.1145/258533.258577"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Pan97">BibTeX</a></font> <li><a name="AharonovB97" href="../../indices/a-tree/a/Aharonov:Dorit.html">Dorit Aharonov</a>, <a href="../../indices/a-tree/b/Ben=Or:Michael.html">Michael Ben-Or</a>: <br><b>Fault-Tolerant Quantum Computation With Constant Error. </b>176-188<br><a href="http://doi.acm.org/10.1145/258533.258579"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AharonovB97">BibTeX</a></font> </ul> <h2>Session 4A</h2> <ul> <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>On the Construction of Pseudo-Random Permutations: Luby-Rackoff Revisited (Extended Abstract). </b>189-199<br><a href="http://doi.acm.org/10.1145/258533.258581"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/NaorR97">BibTeX</a></font> <li><a name="ChenK97" href="../../indices/a-tree/c/Chen:Zhi=Zhong.html">Zhi-Zhong Chen</a>, <a href="../../indices/a-tree/k/Kao:Ming=Yang.html">Ming-Yang Kao</a>: <br><b>Reducing Randomness via Irrational Numbers. </b>200-209<br><a href="http://doi.acm.org/10.1145/258533.258583"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChenK97">BibTeX</a></font> <li><a name="Mulmuley97" href="../../indices/a-tree/m/Mulmuley:Ketan.html">Ketan Mulmuley</a>: <br><b>Is There an Algebraic Proof for <i>P != NC</i>? (Extended Abstract). </b>210-219<br><a href="http://doi.acm.org/10.1145/258533.258586"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Mulmuley97">BibTeX</a></font> <li><a name="ImpagliazzoW97" 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><i>P = BPP</i> if <i>E</i> Requires Exponential Circuits: Derandomizing the XOR Lemma. </b>220-229<br><a href="http://doi.acm.org/10.1145/258533.258590"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ImpagliazzoW97">BibTeX</a></font> <li><a name="ArmoniTWZ97" href="../../indices/a-tree/a/Armoni:Roy.html">Roy Armoni</a>, <a href="../../indices/a-tree/t/Ta=Shma:Amnon.html">Amnon Ta-Shma</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>, <a href="../../indices/a-tree/z/Zhou:Shiyu.html">Shiyu Zhou</a>: <br><b>SL <= L<sup>4/3</sup>. </b>230-239<br><a href="http://doi.acm.org/10.1145/258533.258593"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ArmoniTWZ97">BibTeX</a></font> </ul> <h2>Session 4B</h2> <ul> <li><a name="Karger97" href="../../indices/a-tree/k/Karger:David_R=.html">David R. Karger</a>: <br><b>Using Random Sampling to Find Maximum Flows in Uncapacitated Undirected Graphs. </b>240-249<br><a href="http://doi.acm.org/10.1145/258533.258596"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Karger97">BibTeX</a></font> <li><a name="BelingV97" href="../../indices/a-tree/b/Beling:Peter_A=.html">Peter A. Beling</a>, <a href="../../indices/a-tree/v/Verma:Sushil.html">Sushil Verma</a>: <br><b>Combinatorial Complexity of the Central Curve. </b>250-255<br><a href="http://doi.acm.org/10.1145/258533.258598"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BelingV97">BibTeX</a></font> <li><a name="DuhF97" href="../../indices/a-tree/d/Duh:Rong=chii.html">Rong-chii Duh</a>, <a href="../../indices/a-tree/f/F=uuml=rer:Martin.html">Martin Fürer</a>: <br><b>Approximation of <i>k</i>-Set Cover by Semi-Local Optimization. </b>256-264<br><a href="http://doi.acm.org/10.1145/258533.258599"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DuhF97">BibTeX</a></font> <li><a name="ShmoysTA97" 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>, <a href="../../indices/a-tree/a/Aardal:Karen.html">Karen Aardal</a>: <br><b>Approximation Algorithms for Facility Location Problems (Extended Abstract). </b>265-274<br><a href="http://doi.acm.org/10.1145/258533.258600"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ShmoysTA97">BibTeX</a></font> <li><a name="AsanoKTT97" href="../../indices/a-tree/a/Asano:Tetsuo.html">Tetsuo Asano</a>, <a href="../../indices/a-tree/k/Katoh:Naoki.html">Naoki Katoh</a>, <a href="../../indices/a-tree/t/Tamaki:Hisao.html">Hisao Tamaki</a>, <a href="../../indices/a-tree/t/Tokuyama:Takeshi.html">Takeshi Tokuyama</a>: <br><b>Covering Points in the Plane by <i>k</i>-Tours: Towards a Polynomial Time Approximation Scheme for General <i>k</i>. </b>275-283<br><a href="http://doi.acm.org/10.1145/258533.258602"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AsanoKTT97">BibTeX</a></font> </ul> <h2>Session 5A</h2> <ul> <li><a name="AjtaiD97" href="../../indices/a-tree/a/Ajtai:Mikl=oacute=s.html">Miklós Ajtai</a>, <a href="../../indices/a-tree/d/Dwork:Cynthia.html">Cynthia Dwork</a>: <br><b>A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. </b>284-293<br><a href="http://doi.acm.org/10.1145/258533.258604"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AjtaiD97">BibTeX</a></font> <li><a name="OstrovskyS97" href="../../indices/a-tree/o/Ostrovsky:Rafail.html">Rafail Ostrovsky</a>, <a href="../../indices/a-tree/s/Shoup:Victor.html">Victor Shoup</a>: <br><b>Private Information Storage (Extended Abstract). </b>294-303<br><a href="http://doi.acm.org/10.1145/258533.258606"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/OstrovskyS97">BibTeX</a></font> <li><a name="ChorG97" href="../../indices/a-tree/c/Chor:Benny.html">Benny Chor</a>, <a href="../../indices/a-tree/g/Gilboa:Niv.html">Niv Gilboa</a>: <br><b>Computationally Private Information Retrieval (Extended Abstract). </b>304-313<br><a href="http://doi.acm.org/10.1145/258533.258609"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChorG97">BibTeX</a></font> </ul> <h2>Session 5B</h2> <ul> <li><a name="AuerLS97" href="../../indices/a-tree/a/Auer:Peter.html">Peter Auer</a>, <a href="../../indices/a-tree/l/Long:Philip_M=.html">Philip M. Long</a>, <a href="../../indices/a-tree/s/Srinivasan:Aravind.html">Aravind Srinivasan</a>: <br><b>Approximating Hyper-Rectangles: Learning and Pseudo-Random Sets. </b>314-323<br><a href="http://doi.acm.org/10.1145/258533.258611"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AuerLS97">BibTeX</a></font> <li><a name="Ben-DavidBK97" href="../../indices/a-tree/b/Ben=David:Shai.html">Shai Ben-David</a>, <a href="../../indices/a-tree/b/Bshouty:Nader_H=.html">Nader H. Bshouty</a>, <a href="../../indices/a-tree/k/Kushilevitz:Eyal.html">Eyal Kushilevitz</a>: <br><b>A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes. </b>324-333<br><a href="http://doi.acm.org/10.1145/258533.258614"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Ben-DavidBK97">BibTeX</a></font> <li><a name="FreundSSW97" href="../../indices/a-tree/f/Freund:Yoav.html">Yoav Freund</a>, <a href="../../indices/a-tree/s/Schapire:Robert_E=.html">Robert E. Schapire</a>, <a href="../../indices/a-tree/s/Singer:Yoram.html">Yoram Singer</a>, <a href="../../indices/a-tree/w/Warmuth:Manfred_K=.html">Manfred K. Warmuth</a>: <br><b>Using and Combining Predictors That Specialize. </b>334-343<br><a href="http://doi.acm.org/10.1145/258533.258616"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FreundSSW97">BibTeX</a></font> </ul> <h2>Session 6A</h2> <ul> <li><a name="BermanC97" href="../../indices/a-tree/b/Berman:Piotr.html">Piotr Berman</a>, <a href="../../indices/a-tree/c/Coulston:Chris.html">Chris Coulston</a>: <br><b>On-Line Algorithms for Steiner Tree Problems (Extended Abstract). </b>344-353<br><a href="http://doi.acm.org/10.1145/258533.258618"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BermanC97">BibTeX</a></font> <li><a name="AwerbuchS97" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/s/Singh:Tripurari.html">Tripurari Singh</a>: <br><b>Online Algorithms for Selective Multicast and Maximal Dense Trees. </b>354-362<br><a href="http://doi.acm.org/10.1145/258533.258619"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AwerbuchS97">BibTeX</a></font> </ul> <h2>Session 6B</h2> <ul> <li><a name="ParnafesRW97" href="../../indices/a-tree/p/Parnafes:Itzhak.html">Itzhak Parnafes</a>, <a href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>Direct Product Results and the GCD Problem, in Old and New Communication Models. </b>363-372<br><a href="http://doi.acm.org/10.1145/258533.258620"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ParnafesRW97">BibTeX</a></font> <li><a name="Dietzfelbinger97" href="../../indices/a-tree/d/Dietzfelbinger:Martin.html">Martin Dietzfelbinger</a>: <br><b>The Linear-Array Problem in Communication Complexity Resolved. </b>373-382<br><a href="http://doi.acm.org/10.1145/258533.258622"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Dietzfelbinger97">BibTeX</a></font> </ul> <h2>Invited Session II</h2> <ul> <li><a name="Babai97" href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>: <br><b>Paul Erdös (1913-1996): His Influence on the Theory of Computing. </b>383-401<br><a href="http://doi.acm.org/10.1145/258533.258624"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Babai97">BibTeX</a></font> </ul> <h2>Session 7A</h2> <ul> <li><a name="McCuaigRST97" href="../../indices/a-tree/m/McCuaig:William.html">William McCuaig</a>, <a href="../../indices/a-tree/r/Robertson:Neil.html">Neil Robertson</a>, <a href="../../indices/a-tree/s/Seymour:Paul_D=.html">Paul D. Seymour</a>, <a href="../../indices/a-tree/t/Thomas:Robin.html">Robin Thomas</a>: <br><b>Permanents, Pfaffian Orientations, and Even Directed Circuits (Extended Abstract). </b>402-405<br><a href="http://doi.acm.org/10.1145/258533.258625"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/McCuaigRST97">BibTeX</a></font> <li><a name="GoldreichR97" href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/r/Ron:Dana.html">Dana Ron</a>: <br><b>Property Testing in Bounded Degree Graphs. </b>406-415<br><a href="http://doi.acm.org/10.1145/258533.258627"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldreichR97">BibTeX</a></font> <li><a name="AlbersH97" href="../../indices/a-tree/a/Albers:Susanne.html">Susanne Albers</a>, <a href="../../indices/a-tree/h/Henzinger:Monika_Rauch.html">Monika Rauch Henzinger</a>: <br><b>Exploring Unknown Environments. </b>416-425<br><a href="http://doi.acm.org/10.1145/258533.258630"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AlbersH97">BibTeX</a></font> <li><a name="He97" href="../../indices/a-tree/h/He:Xin.html">Xin He</a>: <br><b>On Floorplans of Planar Graphs. </b>426-435<br><a href="http://doi.acm.org/10.1145/258533.258633"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/He97">BibTeX</a></font> </ul> <h2>Session 7B</h2> <ul> <li><a name="CramerD97" href="../../indices/a-tree/c/Cramer:Ronald.html">Ronald Cramer</a>, <a href="../../indices/a-tree/d/Damg=aring=rd:Ivan.html">Ivan Damgård</a>: <br><b>Linear Zero-Knowledge - A Note on Efficient Zero-Knowledge Proofs and Arguments. </b>436-445<br><a href="http://doi.acm.org/10.1145/258533.258635"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CramerD97">BibTeX</a></font> <li><a name="Beaver97" href="../../indices/a-tree/b/Beaver:Donald.html">Donald Beaver</a>: <br><b>Commodity-Based Cryptography (Extended Abstract). </b>446-455<br><a href="http://doi.acm.org/10.1145/258533.258637"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Beaver97">BibTeX</a></font> <li><a name="Micciancio97" href="../../indices/a-tree/m/Micciancio:Daniele.html">Daniele Micciancio</a>: <br><b>Oblivious Data Structures: Applications to Cryptography. </b>456-464<br><a href="http://doi.acm.org/10.1145/258533.258638"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Micciancio97">BibTeX</a></font> <li><a name="AlonDMPT97" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/d/Dietzfelbinger:Martin.html">Martin Dietzfelbinger</a>, <a href="../../indices/a-tree/m/Miltersen:Peter_Bro.html">Peter Bro Miltersen</a>, <a href="../../indices/a-tree/p/Petrank:Erez.html">Erez Petrank</a>, <a href="../../indices/a-tree/t/Tardos:G=aacute=bor.html">Gábor Tardos</a>: <br><b>Is Linear Hashing Good? </b>465-474<br><a href="http://doi.acm.org/10.1145/258533.258639"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AlonDMPT97">BibTeX</a></font> </ul> <h2>Session 8A</h2> <ul> <li><a name="RazS97" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>, <a href="../../indices/a-tree/s/Safra:Shmuel.html">Shmuel Safra</a>: <br><b>A Sub-Constant Error-Probability Low-Degree Test, and a Sub-Constant Error-Probability PCP Characterization of NP. </b>475-484<br><a href="http://doi.acm.org/10.1145/258533.258641"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/RazS97">BibTeX</a></font> <li><a name="AroraS97" href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: <br><b>Improved Low-Degree Testing and its Applications. </b>485-495<br><a href="http://doi.acm.org/10.1145/258533.258642"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AroraS97">BibTeX</a></font> <li><a name="KilianPT97" 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/t/Tardos:G=aacute=bor.html">Gábor Tardos</a>: <br><b>Probabilistically Checkable Proofs with Zero Knowledge. </b>496-505<br><a href="http://doi.acm.org/10.1145/258533.258643"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KilianPT97">BibTeX</a></font> <li><a name="FeigeK97" 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>Making Games Short (Extended Abstract). </b>506-516<br><a href="http://doi.acm.org/10.1145/258533.258644"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FeigeK97">BibTeX</a></font> </ul> <h2>Session 8B</h2> <ul> <li><a name="MaggsV97" href="../../indices/a-tree/m/Maggs:Bruce_M=.html">Bruce M. Maggs</a>, <a href="../../indices/a-tree/v/V=ouml=cking:Berthold.html">Berthold Vöcking</a>: <br><b>Improved Routing and Sorting on Multibutterflies. </b>517-530<br><a href="http://doi.acm.org/10.1145/258533.258645"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MaggsV97">BibTeX</a></font> <li><a name="BroderFU97" href="../../indices/a-tree/b/Broder:Andrei_Z=.html">Andrei Z. Broder</a>, <a href="../../indices/a-tree/f/Frieze:Alan_M=.html">Alan M. Frieze</a>, <a href="../../indices/a-tree/u/Upfal:Eli.html">Eli Upfal</a>: <br><b>Static and Dynamic Path Selection on Expander Graphs: A Random Walk Approach (Preliminary Version). </b>531-539<br><a href="http://doi.acm.org/10.1145/258533.258646"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BroderFU97">BibTeX</a></font> <li><a name="ArgeFGV97" href="../../indices/a-tree/a/Arge:Lars.html">Lars Arge</a>, <a href="../../indices/a-tree/f/Ferragina:Paolo.html">Paolo Ferragina</a>, <a href="../../indices/a-tree/g/Grossi:Roberto.html">Roberto Grossi</a>, <a href="../../indices/a-tree/v/Vitter:Jeffrey_Scott.html">Jeffrey Scott Vitter</a>: <br><b>On Sorting Strings in External Memory (Extended Abstract). </b>540-548<br><a href="http://doi.acm.org/10.1145/258533.258647"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ArgeFGV97">BibTeX</a></font> <li><a name="NisanB97" href="../../indices/a-tree/n/Nisan:Noam.html">Noam Nisan</a>, <a href="../../indices/a-tree/b/Bar=Yossef:Ziv.html">Ziv Bar-Yossef</a>: <br><b>Pointer Jumping Requires Concurrent Read. </b>549-558<br><a href="http://doi.acm.org/10.1145/258533.258648"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/NisanB97">BibTeX</a></font> </ul> <h2>Session 9A</h2> <ul> <li><a name="Aspnes97" href="../../indices/a-tree/a/Aspnes:James.html">James Aspnes</a>: <br><b>Lower Bounds for Distributed Coin-Flipping and Randomized Consensus. </b>559-568<br><a href="http://doi.acm.org/10.1145/258533.258649"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Aspnes97">BibTeX</a></font> <li><a name="MalkhiR97" href="../../indices/a-tree/m/Malkhi:Dahlia.html">Dahlia Malkhi</a>, <a href="../../indices/a-tree/r/Reiter:Michael_K=.html">Michael K. Reiter</a>: <br><b>Byzantine Quorum Systems. </b>569-578<br><a href="http://doi.acm.org/10.1145/258533.258650"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MalkhiR97">BibTeX</a></font> <li><a name="LoH97" href="../../indices/a-tree/l/Lo:Wai=Kau.html">Wai-Kau Lo</a>, <a href="../../indices/a-tree/h/Hadzilacos:Vassos.html">Vassos Hadzilacos</a>: <br><b>All of Us are Smarter Than Any of Us: Wait-Free Hierarchies are not Robust. </b>579-588<br><a href="http://doi.acm.org/10.1145/258533.258651"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LoH97">BibTeX</a></font> <li><a name="HerlihyR97" href="../../indices/a-tree/h/Herlihy:Maurice.html">Maurice Herlihy</a>, <a href="../../indices/a-tree/r/Rajsbaum:Sergio.html">Sergio Rajsbaum</a>: <br><b>The Decidability of Distributed Decision Tasks (Extended Abstract). </b>589-598<br><a href="http://doi.acm.org/10.1145/258533.258652"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HerlihyR97">BibTeX</a></font> </ul> <h2>Session 9B</h2> <ul> <li><a name="Kleinberg97" href="../../indices/a-tree/k/Kleinberg:Jon_M=.html">Jon M. Kleinberg</a>: <br><b>Two Algorithms for Nearest-Neighbor Search in High Dimensions. </b>599-608<br><a href="http://doi.acm.org/10.1145/258533.258653"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Kleinberg97">BibTeX</a></font> <li><a name="Clarkson97" href="../../indices/a-tree/c/Clarkson:Kenneth_L=.html">Kenneth L. Clarkson</a>: <br><b>Nearest Neighbor Queries in Metric Spaces. </b>609-617<br><a href="http://doi.acm.org/10.1145/258533.258655"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Clarkson97">BibTeX</a></font> <li><a name="IndykMRV97" href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</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/Vempala:Santosh.html">Santosh Vempala</a>: <br><b>Locality-Preserving Hashing in Multidimensional Spaces. </b>618-625<br><a href="http://doi.acm.org/10.1145/258533.258656"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/IndykMRV97">BibTeX</a></font> <li><a name="CharikarCFM97" 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/f/Feder:Tom=aacute=s.html">Tomás Feder</a>, <a href="../../indices/a-tree/m/Motwani:Rajeev.html">Rajeev Motwani</a>: <br><b>Incremental Clustering and Dynamic Information Retrieval. </b>626-635<br><a href="http://doi.acm.org/10.1145/258533.258657"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CharikarCFM97">BibTeX</a></font> </ul> <h2>Session 10A</h2> <ul> <li><a name="SrinivasanT97" href="../../indices/a-tree/s/Srinivasan:Aravind.html">Aravind Srinivasan</a>, <a href="../../indices/a-tree/t/Teo:Chung=Piaw.html">Chung-Piaw Teo</a>: <br><b>A Constant-Factor Approximation Algorithm for Packet Routing, and Balancing Local vs. Global Criteria. </b>636-643<br><a href="http://doi.acm.org/10.1145/258533.258658"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/SrinivasanT97">BibTeX</a></font> <li><a name="OstrovskyR97" href="../../indices/a-tree/o/Ostrovsky:Rafail.html">Rafail Ostrovsky</a>, <a href="../../indices/a-tree/r/Rabani:Yuval.html">Yuval Rabani</a>: <br><b>Universal <i>O</i>(Congestion + Dilation + log<sup>1+epsilon</sup><i>N</i>) Local Control Packet Switching Algorithms. </b>644-653<br><a href="http://doi.acm.org/10.1145/258533.258659"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/OstrovskyR97">BibTeX</a></font> <li><a name="KargerLLPLL97" href="../../indices/a-tree/k/Karger:David_R=.html">David R. Karger</a>, <a href="../../indices/a-tree/l/Lehman:Eric.html">Eric Lehman</a>, <a href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/p/Panigrahy:Rina.html">Rina Panigrahy</a>, <a href="../../indices/a-tree/l/Levine:Matthew_S=.html">Matthew S. Levine</a>, <a href="../../indices/a-tree/l/Lewin:Daniel.html">Daniel Lewin</a>: <br><b>Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. </b>654-663<br><a href="http://doi.acm.org/10.1145/258533.258660"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KargerLLPLL97">BibTeX</a></font> <li><a name="KleinbergRT97" href="../../indices/a-tree/k/Kleinberg:Jon_M=.html">Jon M. Kleinberg</a>, <a href="../../indices/a-tree/r/Rabani:Yuval.html">Yuval Rabani</a>, <a href="../../indices/a-tree/t/Tardos:=Eacute=va.html">Éva Tardos</a>: <br><b>Allocating Bandwidth for Bursty Connections. </b>664-673<br><a href="http://doi.acm.org/10.1145/258533.258661"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KleinbergRT97">BibTeX</a></font> </ul> <h2>Session 10B</h2> <ul> <li><a name="GoreJ97" href="../../indices/a-tree/g/Gore:Vivek.html">Vivek Gore</a>, <a href="../../indices/a-tree/j/Jerrum:Mark.html">Mark Jerrum</a>: <br><b>The Swendsen-Wang Process Does Not Always Mix Rapidly. </b>674-681<br><a href="http://doi.acm.org/10.1145/258533.258662"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoreJ97">BibTeX</a></font> <li><a name="LubyV97" href="../../indices/a-tree/l/Luby:Michael.html">Michael Luby</a>, <a href="../../indices/a-tree/v/Vigoda:Eric.html">Eric Vigoda</a>: <br><b>Approximately Counting Up To Four (Extended Abstract). </b>682-687<br><a href="http://doi.acm.org/10.1145/258533.258663"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LubyV97">BibTeX</a></font> <li><a name="Fill97" href="../../indices/a-tree/f/Fill:James_Allen.html">James Allen Fill</a>: <br><b>An Interruptible Algorithm for Perfect Sampling via Markov Chains. </b>688-695<br><a href="http://doi.acm.org/10.1145/258533.258664"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Fill97">BibTeX</a></font> <li><a name="KannanV97" 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>Sampling Lattice Points. </b>696-700<br><a href="http://doi.acm.org/10.1145/258533.258665"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KannanV97">BibTeX</a></font> </ul> <h2>Session 11A</h2> <ul> <li><a name="Irani97" href="../../indices/a-tree/i/Irani:Sandy.html">Sandy Irani</a>: <br><b>Page Replacement with Multi-Size Pages and Applications to Web Caching. </b>701-710<br><a href="http://doi.acm.org/10.1145/258533.258666"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Irani97">BibTeX</a></font> <li><a name="BartalBBT97" href="../../indices/a-tree/b/Bartal:Yair.html">Yair Bartal</a>, <a 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/t/Tomkins:Andrew.html">Andrew Tomkins</a>: <br><b>A polylog(<i>n</i>)-Competitive Algorithm for Metrical Task Systems. </b>711-719<br><a href="http://doi.acm.org/10.1145/258533.258667"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BartalBBT97">BibTeX</a></font> </ul> <h2>Session 11B</h2> <ul> <li><a name="MacielP97" href="../../indices/a-tree/m/Maciel:Alexis.html">Alexis Maciel</a>, <a href="../../indices/a-tree/p/Pitassi:Toniann.html">Toniann Pitassi</a>: <br><b>On ACC<sup>0</sup>[<i>p<sup>k</sup></i>] Frege Proofs. </b>720-729<br><a href="http://doi.acm.org/10.1145/258533.258669"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MacielP97">BibTeX</a></font> <li><a name="AgrawalAIPR97" href="../../indices/a-tree/a/Agrawal:Manindra.html">Manindra Agrawal</a>, <a href="../../indices/a-tree/a/Allender:Eric.html">Eric Allender</a>, <a href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/p/Pitassi:Toniann.html">Toniann Pitassi</a>, <a href="../../indices/a-tree/r/Rudich:Steven.html">Steven Rudich</a>: <br><b>Reducing the Complexity of Reductions. </b>730-738<br><a href="http://doi.acm.org/10.1145/258533.258671"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AgrawalAIPR97">BibTeX</a></font> <li><a name="RazborovWY97" href="../../indices/a-tree/r/Razborov:Alexander_A=.html">Alexander A. Razborov</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>, <a href="../../indices/a-tree/y/Yao:Andrew_Chi=Chih.html">Andrew Chi-Chih Yao</a>: <br><b>Read-Once Branching Programs, Rectangular Proofs of the Pigeonhole Principle and the Transversal Calculus. </b>739-748<br><a href="http://doi.acm.org/10.1145/258533.258673"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/RazborovWY97">BibTeX</a></font> </ul> <h2>Errata</h2> <ul> <li><a name="ChungY97" href="../../indices/a-tree/c/Chung:Fan_R=_K=.html">Fan R. K. Chung</a>, <a href="../../indices/a-tree/y/Yau:S==T=.html">S.-T. Yau</a>: <br><b>Eigenvalues, Flows and Separators of Graphs. </b>749<br><a href="http://doi.acm.org/10.1145/258533.258675"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChungY97">BibTeX</a></font> <li><a name="FortnowS97" href="../../indices/a-tree/f/Fortnow:Lance.html">Lance Fortnow</a>, <a href="../../indices/a-tree/s/Sipser:Michael.html">Michael Sipser</a>: <br><b>Retraction of Probabilistic Computation and Linear Time. </b>750<br><a href="http://doi.acm.org/10.1145/258533.258677"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FortnowS97">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:43:11 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
