stoc1999.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>STOC 1999</title><link href="../../../dblp.css" rel="stylesheet" type="text/css" /></head> <body> <table width="100%"><tr><td align="left"><a href="../../index.html"><img alt="dblp.uni-trier.de" src="../../Logo.gif" border=0 height=60 width=170></a></td> <td align="right"><a href="http://www.uni-trier.de"><img alt="www.uni-trier.de" src="../../logo_universitaet-trier.gif" border=0 height=48 width=215></a></td></tr></table> <h1>31. <a href="index.html">STOC</a> 1999: Atlanta, Georgia, USA</h1> Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, May 1-4, 1999, Atlanta, Georgia, USA. ACM, 1999 <ul> <li><a name="CharikarGTS99" href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/g/Guha:Sudipto.html">Sudipto Guha</a>, <a href="../../indices/a-tree/t/Tardos:=Eacute=va.html">Éva Tardos</a>, <a href="../../indices/a-tree/s/Shmoys:David_B=.html">David B. Shmoys</a>: <br><b>A Constant-Factor Approximation Algorithm for the <i>k</i>-Median Problem (Extended Abstract). </b>1-10<br><a href="http://doi.acm.org/10.1145/301250.301257"><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/CharikarGTS99">BibTeX</a></font> <li><a name="Wayne99" href="../../indices/a-tree/w/Wayne:Kevin_D=.html">Kevin D. Wayne</a>: <br><b>A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow. </b>11-18<br><a href="http://doi.acm.org/10.1145/301250.301261"><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/Wayne99">BibTeX</a></font> <li><a name="GuruswamiKRSY99" href="../../indices/a-tree/g/Guruswami:Venkatesan.html">Venkatesan Guruswami</a>, <a href="../../indices/a-tree/k/Khanna:Sanjeev.html">Sanjeev Khanna</a>, <a href="../../indices/a-tree/r/Rajaraman:Rajmohan.html">Rajmohan Rajaraman</a>, <a href="../../indices/a-tree/s/Shepherd:F=_Bruce.html">F. Bruce Shepherd</a>, <a href="../../indices/a-tree/y/Yannakakis:Mihalis.html">Mihalis Yannakakis</a>: <br><b>Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. </b>19-28<br><a href="http://doi.acm.org/10.1145/301250.301262"><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/GuruswamiKRSY99">BibTeX</a></font> <li><a name="DinurFKRS99" href="../../indices/a-tree/d/Dinur:Irit.html">Irit Dinur</a>, <a href="../../indices/a-tree/f/Fischer:Eldar.html">Eldar Fischer</a>, <a href="../../indices/a-tree/k/Kindler:Guy.html">Guy Kindler</a>, <a 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>PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. </b>29-40<br><a href="http://doi.acm.org/10.1145/301250.301265"><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/DinurFKRS99">BibTeX</a></font> <li><a name="ErgunKR99" href="../../indices/a-tree/e/Erg=uuml=n:Funda.html">Funda Ergün</a>, <a href="../../indices/a-tree/k/Kumar:Ravi.html">Ravi Kumar</a>, <a href="../../indices/a-tree/r/Rubinfeld:Ronitt.html">Ronitt Rubinfeld</a>: <br><b>Fast Approximate PCPs. </b>41-50<br><a href="http://doi.acm.org/10.1145/301250.301267"><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/ErgunKR99">BibTeX</a></font> <li><a name="KiwiMS99" href="../../indices/a-tree/k/Kiwi:Marcos_A=.html">Marcos A. Kiwi</a>, <a href="../../indices/a-tree/m/Magniez:Fr=eacute=d=eacute=ric.html">Frédéric Magniez</a>, <a href="../../indices/a-tree/s/Santha:Miklos.html">Miklos Santha</a>: <br><b>Approximate Testing with Relative Error. </b>51-60<br><a href="http://doi.acm.org/10.1145/301250.301269"><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/KiwiMS99">BibTeX</a></font> <li><a name="Zwick99" href="../../indices/a-tree/z/Zwick:Uri.html">Uri Zwick</a>: <br><b>All Pairs Lightest Shortest Paths. </b>61-69<br><a href="http://doi.acm.org/10.1145/301250.301271"><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/Zwick99">BibTeX</a></font> <li><a name="GabowKT99" href="../../indices/a-tree/g/Gabow:Harold_N=.html">Harold N. Gabow</a>, <a href="../../indices/a-tree/k/Kaplan:Haim.html">Haim Kaplan</a>, <a href="../../indices/a-tree/t/Tarjan:Robert_Endre.html">Robert Endre Tarjan</a>: <br><b>Unique Maximum Matching Algorithms. </b>70-78<br><a href="http://doi.acm.org/10.1145/301250.301273"><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/GabowKT99">BibTeX</a></font> <li><a name="IshaiK99" href="../../indices/a-tree/i/Ishai:Yuval.html">Yuval Ishai</a>, <a href="../../indices/a-tree/k/Kushilevitz:Eyal.html">Eyal Kushilevitz</a>: <br><b>Improved Upper Bounds on Information-Theoretic Private Information Retrieval (Extended Abstract). </b>79-88<br><a href="http://doi.acm.org/10.1145/301250.301275"><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/IshaiK99">BibTeX</a></font> <li><a name="BeimelIKM99" href="../../indices/a-tree/b/Beimel:Amos.html">Amos Beimel</a>, <a href="../../indices/a-tree/i/Ishai:Yuval.html">Yuval Ishai</a>, <a href="../../indices/a-tree/k/Kushilevitz:Eyal.html">Eyal Kushilevitz</a>, <a href="../../indices/a-tree/m/Malkin:Tal.html">Tal Malkin</a>: <br><b>One-Way Functions Are Essential for Single-Server Private Information Retrieval. </b>89-98<br><a href="http://doi.acm.org/10.1145/301250.301277"><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/BeimelIKM99">BibTeX</a></font> <li><a name="CharikarKRRT99" href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a 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>On targeting Markov segments. </b>99-108<br><a href="http://doi.acm.org/10.1145/301250.301280"><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/CharikarKRRT99">BibTeX</a></font> <li><a name="CohenK99" href="../../indices/a-tree/c/Cohen:Edith.html">Edith Cohen</a>, <a href="../../indices/a-tree/k/Kaplan:Haim.html">Haim Kaplan</a>: <br><b>Exploiting Regularities in Web Traffic Patterns for Cache Replacement. </b>109-118<br><a href="http://doi.acm.org/10.1145/301250.301281"><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/CohenK99">BibTeX</a></font> <li><a name="ChenKLW99" href="../../indices/a-tree/c/Chen:Gen=Huey.html">Gen-Huey Chen</a>, <a href="../../indices/a-tree/k/Kao:Ming=Yang.html">Ming-Yang Kao</a>, <a href="../../indices/a-tree/l/Lyuu:Yuh=Dauh.html">Yuh-Dauh Lyuu</a>, <a href="../../indices/a-tree/w/Wong:Hsing=Kuo.html">Hsing-Kuo Wong</a>: <br><b>Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns. </b>119-128<br><a href="http://doi.acm.org/10.1145/301250.301284"><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/ChenKLW99">BibTeX</a></font> <li><a name="NisanR99" href="../../indices/a-tree/n/Nisan:Noam.html">Noam Nisan</a>, <a href="../../indices/a-tree/r/Ronen:Amir.html">Amir Ronen</a>: <br><b>Algorithmic Mechanism Design (Extended Abstract). </b>129-140<br><a href="http://doi.acm.org/10.1145/301250.301287"><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/NisanR99">BibTeX</a></font> <li><a name="Trevisan99" href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>: <br><b>Construction of Extractors Using Pseudo-Random Generators (Extended Abstract). </b>141-148<br><a href="http://doi.acm.org/10.1145/301250.301289"><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/Trevisan99">BibTeX</a></font> <li><a name="RazRV99" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>, <a href="../../indices/a-tree/r/Reingold:Omer.html">Omer Reingold</a>, <a href="../../indices/a-tree/v/Vadhan:Salil_P=.html">Salil P. Vadhan</a>: <br><b>Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. </b>149-158<br><a href="http://doi.acm.org/10.1145/301250.301292"><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/RazRV99">BibTeX</a></font> <li><a name="RazR99" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>, <a href="../../indices/a-tree/r/Reingold:Omer.html">Omer Reingold</a>: <br><b>On Recycling the Randomness of States in Space Bounded Computation. </b>159-168<br><a href="http://doi.acm.org/10.1145/301250.301294"><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/RazR99">BibTeX</a></font> <li><a name="CrescenzoI99" href="../../indices/a-tree/c/Crescenzo:Giovanni_Di.html">Giovanni Di Crescenzo</a>, <a href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>: <br><b>Security-Preserving Hardness-Amplification for Any Regular One-Way Function. </b>169-178<br><a href="http://doi.acm.org/10.1145/301250.301296"><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/CrescenzoI99">BibTeX</a></font> <li><a name="Edmonds99" href="../../indices/a-tree/e/Edmonds:Jeff.html">Jeff Edmonds</a>: <br><b>Scheduling in the Dark. </b>179-188<br><a href="http://doi.acm.org/10.1145/301250.301299"><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/Edmonds99">BibTeX</a></font> <li><a name="GoelHPT99" href="../../indices/a-tree/g/Goel:Ashish.html">Ashish Goel</a>, <a href="../../indices/a-tree/h/Henzinger:Monika_Rauch.html">Monika Rauch Henzinger</a>, <a href="../../indices/a-tree/p/Plotkin:Serge_A=.html">Serge A. Plotkin</a>, <a href="../../indices/a-tree/t/Tardos:=Eacute=va.html">Éva Tardos</a>: <br><b>Scheduling Data Transfers in a Network and the Set Scheduling Problem. </b>189-197<br><a href="http://doi.acm.org/10.1145/301250.301300"><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/GoelHPT99">BibTeX</a></font> <li><a name="AwerbuchALR99" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/a/Azar:Yossi.html">Yossi Azar</a>, <a href="../../indices/a-tree/l/Leonardi:Stefano.html">Stefano Leonardi</a>, <a href="../../indices/a-tree/r/Regev:Oded.html">Oded Regev</a>: <br><b>Minimizing the Flow Time Without Migration. </b>198-205<br><a href="http://doi.acm.org/10.1145/301250.301304"><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/AwerbuchALR99">BibTeX</a></font> <li><a name="Gamarnik99" href="../../indices/a-tree/g/Gamarnik:David.html">David Gamarnik</a>: <br><b>Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks. </b>206-214<br><a href="http://doi.acm.org/10.1145/301250.301306"><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/Gamarnik99">BibTeX</a></font> <li><a name="ScheidelerV99" href="../../indices/a-tree/s/Scheideler:Christian.html">Christian Scheideler</a>, <a href="../../indices/a-tree/v/V=ouml=cking:Berthold.html">Berthold Vöcking</a>: <br><b>From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols. </b>215-224<br><a href="http://doi.acm.org/10.1145/301250.301307"><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/ScheidelerV99">BibTeX</a></font> <li><a name="GoldreichRS99" href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/r/Ron:Dana.html">Dana Ron</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: <br><b>Chinese Remaindering with Errors. </b>225-234<br><a href="http://doi.acm.org/10.1145/301250.301309"><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/GoldreichRS99">BibTeX</a></font> <li><a name="OlshevskyS99" href="../../indices/a-tree/o/Olshevsky:Vadim.html">Vadim Olshevsky</a>, <a href="../../indices/a-tree/s/Shokrollahi:Mohammad_Amin.html">Mohammad Amin Shokrollahi</a>: <br><b>A Displacement Approach to Efficient Decoding of Algebraic-Geometric Codes. </b>235-244<br><a href="http://doi.acm.org/10.1145/301250.301311"><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/OlshevskyS99">BibTeX</a></font> <li><a name="NaorP99" href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>, <a href="../../indices/a-tree/p/Pinkas:Benny.html">Benny Pinkas</a>: <br><b>Oblivious Transfer and Polynomial Evaluation. </b>245-254<br><a href="http://doi.acm.org/10.1145/301250.301312"><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/NaorP99">BibTeX</a></font> <li><a name="CanettiO99" href="../../indices/a-tree/c/Canetti:Ran.html">Ran Canetti</a>, <a href="../../indices/a-tree/o/Ostrovsky:Rafail.html">Rafail Ostrovsky</a>: <br><b>Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (Extended Abstract). </b>255-264<br><a href="http://doi.acm.org/10.1145/301250.301313"><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/CanettiO99">BibTeX</a></font> <li><a name="DinitzMR99" href="../../indices/a-tree/d/Dinitz:Yefim.html">Yefim Dinitz</a>, <a href="../../indices/a-tree/m/Moran:Shlomo.html">Shlomo Moran</a>, <a href="../../indices/a-tree/r/Rajsbaum:Sergio.html">Sergio Rajsbaum</a>: <br><b>Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract). </b>265-274<br><a href="http://doi.acm.org/10.1145/301250.301314"><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/DinitzMR99">BibTeX</a></font> <li><a name="ChenLP99" href="../../indices/a-tree/c/Chen:Fang.html">Fang Chen</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/p/Pak:Igor.html">Igor Pak</a>: <br><b>Lifting Markov Chains to Speed up Mixing. </b>275-281<br><a href="http://doi.acm.org/10.1145/301250.301315"><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/ChenLP99">BibTeX</a></font> <li><a name="LovaszK99" href="../../indices/a-tree/l/Lov=aacute=sz:L=aacute=szl=oacute=.html">László Lovász</a>, <a href="../../indices/a-tree/k/Kannan:Ravi.html">Ravi Kannan</a>: <br><b>Faster Mixing via Average Conductance. </b>282-287<br><a href="http://doi.acm.org/10.1145/301250.301317"><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/LovaszK99">BibTeX</a></font> <li><a name="SchulmanV99" href="../../indices/a-tree/s/Schulman:Leonard_J=.html">Leonard J. Schulman</a>, <a href="../../indices/a-tree/v/Vazirani:Vijay_V=.html">Vijay V. Vazirani</a>: <br><b>Majorizing Estimators and the Approximation of #P-Complete Problems. </b>288-294<br><a href="http://doi.acm.org/10.1145/301250.301320"><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/SchulmanV99">BibTeX</a></font> <li><a name="BeameF99" href="../../indices/a-tree/b/Beame:Paul.html">Paul Beame</a>, <a href="../../indices/a-tree/f/Fich:Faith_E=.html">Faith E. Fich</a>: <br><b>Optimal Bounds for the Predecessor Problem. </b>295-304<br><a href="http://doi.acm.org/10.1145/301250.301323"><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/BeameF99">BibTeX</a></font> <li><a name="ChakrabartiCGL99" href="../../indices/a-tree/c/Chakrabarti:Amit.html">Amit Chakrabarti</a>, <a href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>, <a href="../../indices/a-tree/g/Gum:Benjamin.html">Benjamin Gum</a>, <a href="../../indices/a-tree/l/Lvov:Alexey.html">Alexey Lvov</a>: <br><b>A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube. </b>305-311<br><a href="http://doi.acm.org/10.1145/301250.301325"><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/ChakrabartiCGL99">BibTeX</a></font> <li><a name="BorodinOR99" href="../../indices/a-tree/b/Borodin:Allan.html">Allan Borodin</a>, <a 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>Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. </b>312-321<br><a href="http://doi.acm.org/10.1145/301250.301330"><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/BorodinOR99">BibTeX</a></font> <li><a name="SchulmanV99a" href="../../indices/a-tree/s/Schulman:Leonard_J=.html">Leonard J. Schulman</a>, <a href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>: <br><b>Molecular Scale Heat Engines and Scalable Quantum Computation. </b>322-329<br><a href="http://doi.acm.org/10.1145/301250.301332"><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/SchulmanV99a">BibTeX</a></font> <li><a name="HalesH99" href="../../indices/a-tree/h/Hales:Lisa.html">Lisa Hales</a>, <a href="../../indices/a-tree/h/Hallgren:Sean.html">Sean Hallgren</a>: <br><b>Quantum Fourier Sampling Simplified. </b>330-338<br><a href="http://doi.acm.org/10.1145/301250.301336"><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/HalesH99">BibTeX</a></font> <li><a name="RussellSZ99" href="../../indices/a-tree/r/Russell:Alexander.html">Alexander Russell</a>, <a href="../../indices/a-tree/s/Saks:Michael_E=.html">Michael E. Saks</a>, <a href="../../indices/a-tree/z/Zuckerman:David.html">David Zuckerman</a>: <br><b>Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. </b>339-347<br><a href="http://doi.acm.org/10.1145/301250.301337"><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/RussellSZ99">BibTeX</a></font> <li><a name="GalR99" href="../../indices/a-tree/g/G=aacute=l:Anna.html">Anna Gál</a>, <a href="../../indices/a-tree/r/Ros=eacute=n:Adi.html">Adi Rosén</a>: <br><b>A Theorem on Sensitivity and Applications in Private Computation. </b>348-357<br><a href="http://doi.acm.org/10.1145/301250.301340"><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/GalR99">BibTeX</a></font> <li><a name="Raz99" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>: <br><b>Exponential Separation of Quantum and Classical Communication Complexity. </b>358-367<br><a href="http://doi.acm.org/10.1145/301250.301343"><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/Raz99">BibTeX</a></font> <li><a name="AmanoI99" href="../../indices/a-tree/a/Amano:Masami.html">Masami Amano</a>, <a href="../../indices/a-tree/i/Iwama:Kazuo.html">Kazuo Iwama</a>: <br><b>Undecidability on Quantum Finite Automata. </b>368-375<br><a href="http://doi.acm.org/10.1145/301250.301344"><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/AmanoI99">BibTeX</a></font> <li><a name="AmbainisNTV99" href="../../indices/a-tree/a/Ambainis:Andris.html">Andris Ambainis</a>, <a href="../../indices/a-tree/n/Nayak:Ashwin.html">Ashwin Nayak</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>: <br><b>Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. </b>376-383<br><a href="http://doi.acm.org/10.1145/301250.301347"><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/AmbainisNTV99">BibTeX</a></font> <li><a name="NayakW99" href="../../indices/a-tree/n/Nayak:Ashwin.html">Ashwin Nayak</a>, <a href="../../indices/a-tree/w/Wu:Felix.html">Felix Wu</a>: <br><b>The Quantum Query Complexity of Approximating the Median and Related Statistics. </b>384-393<br><a href="http://doi.acm.org/10.1145/301250.301349"><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/NayakW99">BibTeX</a></font> <li><a name="JansenSS99" href="../../indices/a-tree/j/Jansen:Klaus.html">Klaus Jansen</a>, <a href="../../indices/a-tree/s/Solis=Oba:Roberto.html">Roberto Solis-Oba</a>, <a href="../../indices/a-tree/s/Sviridenko:Maxim.html">Maxim Sviridenko</a>: <br><b>Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme. </b>394-399<br><a href="http://doi.acm.org/10.1145/301250.301351"><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/JansenSS99">BibTeX</a></font> <li><a name="SkutellaW99" href="../../indices/a-tree/s/Skutella:Martin.html">Martin Skutella</a>, <a href="../../indices/a-tree/w/Woeginger:Gerhard_J=.html">Gerhard J. Woeginger</a>: <br><b>A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines. </b>400-407<br><a href="http://doi.acm.org/10.1145/301250.301356"><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/SkutellaW99">BibTeX</a></font> <li><a name="JansenP99" href="../../indices/a-tree/j/Jansen:Klaus.html">Klaus Jansen</a>, <a href="../../indices/a-tree/p/Porkolab:Lorant.html">Lorant Porkolab</a>: <br><b>Improved Approximation Schemes for Scheduling Unrelated Parallel Machines. </b>408-417<br><a href="http://doi.acm.org/10.1145/301250.301361"><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/JansenP99">BibTeX</a></font> <li><a name="ChenM99" href="../../indices/a-tree/c/Chen:Jianer.html">Jianer Chen</a>, <a href="../../indices/a-tree/m/Miranda:Antonio.html">Antonio Miranda</a>: <br><b>A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (Extended Abstract). </b>418-427<br><a href="http://doi.acm.org/10.1145/301250.301363"><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/ChenM99">BibTeX</a></font> <li><a name="Indyk99" href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>: <br><b>Sublinear Time Algorithms for Metric Space Problems. </b>428-434<br><a href="http://doi.acm.org/10.1145/301250.301366"><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/Indyk99">BibTeX</a></font> <li><a name="BorodinOR99a" href="../../indices/a-tree/b/Borodin:Allan.html">Allan Borodin</a>, <a 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>Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. </b>435-444<br><a href="http://doi.acm.org/10.1145/301250.301367"><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/BorodinOR99a">BibTeX</a></font> <li><a name="KumarR99" href="../../indices/a-tree/k/Kumar:V=_S=_Anil.html">V. S. Anil Kumar</a>, <a href="../../indices/a-tree/r/Ramesh:H=.html">H. Ramesh</a>: <br><b>Covering Rectilinear Polygons with Axis-Parallel Rectangles. </b>445-454<br><a href="http://doi.acm.org/10.1145/301250.301369"><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/KumarR99">BibTeX</a></font> <li><a name="MuthukrishnanPSS99" href="../../indices/a-tree/m/Muthukrishnan:S=.html">S. Muthukrishnan</a>, <a href="../../indices/a-tree/p/Paterson:Mike.html">Mike Paterson</a>, <a href="../../indices/a-tree/s/Sahinalp:S=uuml=leyman_Cenk.html">Süleyman Cenk Sahinalp</a>, <a href="../../indices/a-tree/s/Suel:Torsten.html">Torsten Suel</a>: <br><b>Compact Grid Layouts of Multi-Level Networks. </b>455-463<br><a href="http://doi.acm.org/10.1145/301250.301372"><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/MuthukrishnanPSS99">BibTeX</a></font> <li><a name="FederHKM99" href="../../indices/a-tree/f/Feder:Tom=aacute=s.html">Tomás Feder</a>, <a href="../../indices/a-tree/h/Hell:Pavol.html">Pavol Hell</a>, <a href="../../indices/a-tree/k/Klein:Sulamita.html">Sulamita Klein</a>, <a href="../../indices/a-tree/m/Motwani:Rajeev.html">Rajeev Motwani</a>: <br><b>Complexity of Graph Partition Problems. </b>464-472<br><a href="http://doi.acm.org/10.1145/301250.301373"><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/FederHKM99">BibTeX</a></font> <li><a name="LiMW99" href="../../indices/a-tree/l/Li:Ming.html">Ming Li</a>, <a href="../../indices/a-tree/m/Ma:Bin.html">Bin Ma</a>, <a href="../../indices/a-tree/w/Wang:Lusheng.html">Lusheng Wang</a>: <br><b>Finding Similar Regions in Many Strings. </b>473-482<br><a href="http://doi.acm.org/10.1145/301250.301376"><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/LiMW99">BibTeX</a></font> <li><a name="FerraginaMB99" href="../../indices/a-tree/f/Ferragina:Paolo.html">Paolo Ferragina</a>, <a href="../../indices/a-tree/m/Muthukrishnan:S=.html">S. Muthukrishnan</a>, <a href="../../indices/a-tree/b/Berg:Mark_de.html">Mark de Berg</a>: <br><b>Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems. </b>483-491<br><a href="http://doi.acm.org/10.1145/301250.301378"><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/FerraginaMB99">BibTeX</a></font> <li><a name="KingS99" href="../../indices/a-tree/k/King:Valerie.html">Valerie King</a>, <a href="../../indices/a-tree/s/Sagert:Garry.html">Garry Sagert</a>: <br><b>A Fully Dynamic Algorithm for Maintaining the Transitive Closure. </b>492-498<br><a href="http://doi.acm.org/10.1145/301250.301380"><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/KingS99">BibTeX</a></font> <li><a name="AlstrupBR99" href="../../indices/a-tree/a/Alstrup:Stephen.html">Stephen Alstrup</a>, <a href="../../indices/a-tree/b/Ben=Amram:Amir_M=.html">Amir M. Ben-Amram</a>, <a href="../../indices/a-tree/r/Rauhe:Theis.html">Theis Rauhe</a>: <br><b>Worst-Case and Amortised Optimality in Union-Find (Extended Abstract). </b>499-506<br><a href="http://doi.acm.org/10.1145/301250.301383"><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/AlstrupBR99">BibTeX</a></font> <li><a name="PanC99" href="../../indices/a-tree/p/Pan:Victor_Y=.html">Victor Y. Pan</a>, <a href="../../indices/a-tree/c/Chen:Zhao_Q=.html">Zhao Q. Chen</a>: <br><b>The Complexity of the Matrix Eigenproblem. </b>507-516<br><a href="http://doi.acm.org/10.1145/301250.301389"><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/PanC99">BibTeX</a></font> <li><a name="Ben-SassonW99" href="../../indices/a-tree/b/Ben=Sasson:Eli.html">Eli Ben-Sasson</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>Short Proofs are Narrow - Resolution Made Simple. </b>517-526<br><a href="http://doi.acm.org/10.1145/301250.301392"><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-SassonW99">BibTeX</a></font> <li><a name="Rojas99" href="../../indices/a-tree/r/Rojas:J=_Maurice.html">J. Maurice Rojas</a>: <br><b>On the Complexity of Diophantine Geometry in Low Dimensions (Extended Abstract). </b>527-536<br><a href="http://doi.acm.org/10.1145/301250.301395"><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/Rojas99">BibTeX</a></font> <li><a name="SudanTV99" href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>, <a href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>, <a href="../../indices/a-tree/v/Vadhan:Salil_P=.html">Salil P. Vadhan</a>: <br><b>Pseudorandom Generators Without the XOR Lemma (Extended Abstract). </b>537-546<br><a href="http://doi.acm.org/10.1145/301250.301397"><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/SudanTV99">BibTeX</a></font> <li><a name="BussGIP99" href="../../indices/a-tree/b/Buss:Samuel_R=.html">Samuel R. Buss</a>, <a href="../../indices/a-tree/g/Grigoriev:Dima.html">Dima Grigoriev</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>: <br><b>Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. </b>547-556<br><a href="http://doi.acm.org/10.1145/301250.301399"><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/BussGIP99">BibTeX</a></font> <li><a name="AndrewsZ99" 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>Packet Routing with Arbitrary End-to-End Delay Requirements. </b>557-565<br><a href="http://doi.acm.org/10.1145/301250.301401"><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/AndrewsZ99">BibTeX</a></font> <li><a name="PanduranganU99" href="../../indices/a-tree/p/Pandurangan:Gopal.html">Gopal Pandurangan</a>, <a href="../../indices/a-tree/u/Upfal:Eli.html">Eli Upfal</a>: <br><b>Static and Dynamic Evaluation of QoS Properties. </b>566-573<br><a href="http://doi.acm.org/10.1145/301250.301404"><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/PanduranganU99">BibTeX</a></font> <li><a name="GuhaMNS99" href="../../indices/a-tree/g/Guha:Sudipto.html">Sudipto Guha</a>, <a href="../../indices/a-tree/m/Moss:Anna.html">Anna Moss</a>, <a 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>Efficient Recovery from Power Outage (Extended Abstract). </b>574-582<br><a href="http://doi.acm.org/10.1145/301250.301406"><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/GuhaMNS99">BibTeX</a></font> <li><a name="Feige99" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>: <br><b>Nonmonotonic Phenomena in Packet Routing. </b>583-591<br><a href="http://doi.acm.org/10.1145/301250.301409"><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/Feige99">BibTeX</a></font> <li><a name="Schaefer99" href="../../indices/a-tree/s/Schaefer:Marcus.html">Marcus Schaefer</a>: <br><b>Graph Ramsey Theory and the Polynomial Hierarchy. </b>592-601<br><a href="http://doi.acm.org/10.1145/301250.301411"><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/Schaefer99">BibTeX</a></font> <li><a name="PonzioRV99" href="../../indices/a-tree/p/Ponzio:Stephen.html">Stephen Ponzio</a>, <a href="../../indices/a-tree/r/Radhakrishnan:Jaikumar.html">Jaikumar Radhakrishnan</a>, <a href="../../indices/a-tree/v/Venkatesh:Srinivasan.html">Srinivasan Venkatesh</a>: <br><b>The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling. </b>602-611<br><a href="http://doi.acm.org/10.1145/301250.301413"><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/PonzioRV99">BibTeX</a></font> <li><a name="CohenKZ99" href="../../indices/a-tree/c/Cohen:Edith.html">Edith Cohen</a>, <a href="../../indices/a-tree/k/Kaplan:Haim.html">Haim Kaplan</a>, <a href="../../indices/a-tree/z/Zwick:Uri.html">Uri Zwick</a>: <br><b>Connection Caching. </b>612-621<br><a href="http://doi.acm.org/10.1145/301250.301416"><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/CohenKZ99">BibTeX</a></font> <li><a name="Bar-NoyGNS99" href="../../indices/a-tree/b/Bar=Noy:Amotz.html">Amotz Bar-Noy</a>, <a href="../../indices/a-tree/g/Guha:Sudipto.html">Sudipto Guha</a>, <a 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>Approximating the Throughput of Multiple Machines Under Real-Time Scheduling. </b>622-631<br><a href="http://doi.acm.org/10.1145/301250.301420"><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/Bar-NoyGNS99">BibTeX</a></font> <li><a name="Ajtai99" href="../../indices/a-tree/a/Ajtai:Mikl=oacute=s.html">Miklós Ajtai</a>: <br><b>Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract). </b>632-641<br><a href="http://doi.acm.org/10.1145/301250.301424"><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/Ajtai99">BibTeX</a></font> <li><a name="Valiant99" href="../../indices/a-tree/v/Valiant:Leslie_G=.html">Leslie G. Valiant</a>: <br><b>Robust Logics. </b>642-651<br><a href="http://doi.acm.org/10.1145/301250.301425"><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/Valiant99">BibTeX</a></font> <li><a name="Luks99" href="../../indices/a-tree/l/Luks:Eugene_M=.html">Eugene M. Luks</a>: <br><b>Hypergraph Isomorphism and Structural Equivalence of Boolean Functions. </b>652-658<br><a href="http://doi.acm.org/10.1145/301250.301427"><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/Luks99">BibTeX</a></font> <li><a name="KlivansM99" href="../../indices/a-tree/k/Klivans:Adam.html">Adam Klivans</a>, <a href="../../indices/a-tree/m/Melkebeek:Dieter_van.html">Dieter van Melkebeek</a>: <br><b>Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. </b>659-667<br><a href="http://doi.acm.org/10.1145/301250.301428"><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/KlivansM99">BibTeX</a></font> <li><a name="KargerKSTY99" href="../../indices/a-tree/k/Karger:David_R=.html">David R. Karger</a>, <a href="../../indices/a-tree/k/Klein:Philip_N=.html">Philip N. Klein</a>, <a href="../../indices/a-tree/s/Stein:Clifford.html">Clifford Stein</a>, <a href="../../indices/a-tree/t/Thorup:Mikkel.html">Mikkel Thorup</a>, <a href="../../indices/a-tree/y/Young:Neal_E=.html">Neal E. Young</a>: <br><b>Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. </b>668-678<br><a href="http://doi.acm.org/10.1145/301250.301430"><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/KargerKSTY99">BibTeX</a></font> <li><a name="Zwick99a" href="../../indices/a-tree/z/Zwick:Uri.html">Uri Zwick</a>: <br><b>Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems. </b>679-687<br><a href="http://doi.acm.org/10.1145/301250.301431"><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/Zwick99a">BibTeX</a></font> <li><a name="AroraK99" href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>, <a href="../../indices/a-tree/k/Karakostas:George.html">George Karakostas</a>: <br><b>Approximation Schemes for Minimum Latency Problems. </b>688-693<br><a href="http://doi.acm.org/10.1145/301250.301432"><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/AroraK99">BibTeX</a></font> <li><a name="Gupta99" href="../../indices/a-tree/g/Gupta:Anupam.html">Anupam Gupta</a>: <br><b>Embedding Tree Metrics Into Low Dimensional Euclidean Spaces. </b>694-700<br><a href="http://doi.acm.org/10.1145/301250.301434"><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/Gupta99">BibTeX</a></font> <li><a name="Servedio99" href="../../indices/a-tree/s/Servedio:Rocco_A=.html">Rocco A. Servedio</a>: <br><b>Computational Sample Complexity and Attribute-Efficient Learning. </b>701-710<br><a href="http://doi.acm.org/10.1145/301250.301437"><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/Servedio99">BibTeX</a></font> <li><a name="BlomerS99" href="../../indices/a-tree/b/Bl=ouml=mer:Johannes.html">Johannes Blömer</a>, <a href="../../indices/a-tree/s/Seifert:Jean=Pierre.html">Jean-Pierre Seifert</a>: <br><b>On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice. </b>711-720<br><a href="http://doi.acm.org/10.1145/301250.301441"><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/BlomerS99">BibTeX</a></font> <li><a name="Plandowski99" href="../../indices/a-tree/p/Plandowski:Wojciech.html">Wojciech Plandowski</a>: <br><b>Satisfiability of Word Equations with Constants is in NEXPTIME. </b>721-725<br><a href="http://doi.acm.org/10.1145/301250.301443"><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/Plandowski99">BibTeX</a></font> <li><a name="CaiNS99" 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>, <a href="../../indices/a-tree/s/Sivakumar:D=.html">D. Sivakumar</a>: <br><b>Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. </b>726-735<br><a href="http://doi.acm.org/10.1145/301250.301444"><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/CaiNS99">BibTeX</a></font> <li><a name="Indyk99a" href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>: <br><b>Inerpolation of Symmetric Functions and a New Type of Combinatorial Design. </b>736-740<br><a href="http://doi.acm.org/10.1145/301250.301445"><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/Indyk99a">BibTeX</a></font> <li><a name="CapalboK99" href="../../indices/a-tree/c/Capalbo:Michael_R=.html">Michael R. Capalbo</a>, <a href="../../indices/a-tree/k/Kosaraju:S=_Rao.html">S. Rao Kosaraju</a>: <br><b>Small Universal Graphs. </b>741-749<br><a href="http://doi.acm.org/10.1145/301250.301446"><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/CapalboK99">BibTeX</a></font> <li><a name="DodisK99" href="../../indices/a-tree/d/Dodis:Yevgeniy.html">Yevgeniy Dodis</a>, <a href="../../indices/a-tree/k/Khanna:Sanjeev.html">Sanjeev Khanna</a>: <br><b>Design Networks with Bounded Pairwise Distance. </b>750-759<br><a href="http://doi.acm.org/10.1145/301250.301447"><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/DodisK99">BibTeX</a></font> <li><a name="Schaeffer99" href="../../indices/a-tree/s/Schaeffer:Gilles.html">Gilles Schaeffer</a>: <br><b>Random Sampling of Large Planar Maps and Convex Polyhedra. </b>760-769<br><a href="http://doi.acm.org/10.1145/301250.301448"><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/Schaeffer99">BibTeX</a></font> <li><a name="Kapoor99" href="../../indices/a-tree/k/Kapoor:Sanjiv.html">Sanjiv Kapoor</a>: <br><b>Efficient Computation of Geodesic Shortest Paths. </b>770-779<br><a href="http://doi.acm.org/10.1145/301250.301449"><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/Kapoor99">BibTeX</a></font> <li><a name="Ben-AmramP99" href="../../indices/a-tree/b/Ben=Amram:Amir_M=.html">Amir M. Ben-Amram</a>, <a href="../../indices/a-tree/p/Petersen:Holger.html">Holger Petersen</a>: <br><b>Backing Up in Singly Linked Lists. </b>780-786<br><a href="http://doi.acm.org/10.1145/301250.301450"><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-AmramP99">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:12 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
