stoc2002.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>STOC 2002</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>34. <a href="index.html">STOC</a> 2002: Montréal, Québec, Canada</h1> Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada. ACM, 2002 <ul> <li><a name="SchaeferSS02" href="../../indices/a-tree/s/Schaefer:Marcus.html">Marcus Schaefer</a>, <a href="../../indices/a-tree/s/Sedgwick:Eric.html">Eric Sedgwick</a>, <a href="../../indices/a-tree/s/Stefankovic:Daniel.html">Daniel Stefankovic</a>: <br><b>Recognizing string graphs in NP. </b>1-6<br><a href="http://doi.acm.org/10.1145/509907.509910"><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/SchaeferSS02">BibTeX</a></font> <li><a name="Chan02" href="../../indices/a-tree/c/Chan:Timothy_M=.html">Timothy M. Chan</a>: <br><b>Dynamic subgraph connectivity with geometric applications. </b>7-13<br><a href="http://doi.acm.org/10.1145/509907.509911"><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/Chan02">BibTeX</a></font> <li><a name="EiterGM02" href="../../indices/a-tree/e/Eiter:Thomas.html">Thomas Eiter</a>, <a href="../../indices/a-tree/g/Gottlob:Georg.html">Georg Gottlob</a>, <a href="../../indices/a-tree/m/Makino:Kazuhisa.html">Kazuhisa Makino</a>: <br><b>New results on monotone dualization and generating hypergraph transversals. </b>14-22<br><a href="http://doi.acm.org/10.1145/509907.509912"><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/EiterGM02">BibTeX</a></font> <li><a name="AdlemanCGHKER02" href="../../indices/a-tree/a/Adleman:Leonard_M=.html">Leonard M. Adleman</a>, <a href="../../indices/a-tree/c/Cheng:Qi.html">Qi Cheng</a>, <a href="../../indices/a-tree/g/Goel:Ashish.html">Ashish Goel</a>, <a href="../../indices/a-tree/h/Huang:Ming=Deh_A=.html">Ming-Deh A. Huang</a>, <a href="../../indices/a-tree/k/Kempe:David.html">David Kempe</a>, <a href="../../indices/a-tree/e/Espan=eacute=s:Pablo_Moisset_de.html">Pablo Moisset de Espanés</a>, <a href="../../indices/a-tree/r/Rothemund:Paul_W=_K=.html">Paul W. K. Rothemund</a>: <br><b>Combinatorial optimization problems in self-assembly. </b>23-32<br><a href="http://doi.acm.org/10.1145/509907.509913"><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/AdlemanCGHKER02">BibTeX</a></font> <li><a name="DinurS02" href="../../indices/a-tree/d/Dinur:Irit.html">Irit Dinur</a>, <a href="../../indices/a-tree/s/Safra:Shmuel.html">Shmuel Safra</a>: <br><b>The importance of being biased. </b>33-42<br><a href="http://doi.acm.org/10.1145/509907.509915"><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/DinurS02">BibTeX</a></font> <li><a name="HastadV02" href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>, <a href="../../indices/a-tree/v/Venkatesh:Srinivasan.html">Srinivasan Venkatesh</a>: <br><b>On the advantage over a random assignment. </b>43-52<br><a href="http://doi.acm.org/10.1145/509907.509916"><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/HastadV02">BibTeX</a></font> <li><a name="GoldbergKP02" href="../../indices/a-tree/g/Goldberg:Leslie_Ann.html">Leslie Ann Goldberg</a>, <a href="../../indices/a-tree/k/Kelk:Steven.html">Steven Kelk</a>, <a href="../../indices/a-tree/p/Paterson:Mike.html">Mike Paterson</a>: <br><b>The complexity of choosing an H-colouring (nearly) uniformly at random. </b>53-62<br><a href="http://doi.acm.org/10.1145/509907.509917"><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/GoldbergKP02">BibTeX</a></font> <li><a name="KargerL02" href="../../indices/a-tree/k/Karger:David_R=.html">David R. Karger</a>, <a href="../../indices/a-tree/l/Levine:Matthew_S=.html">Matthew S. Levine</a>: <br><b>Random sampling in residual graphs. </b>63-66<br><a href="http://doi.acm.org/10.1145/509907.509918"><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/KargerL02">BibTeX</a></font> <li><a name="DengPS02" href="../../indices/a-tree/d/Deng:Xiaotie.html">Xiaotie Deng</a>, <a href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>, <a href="../../indices/a-tree/s/Safra:Shmuel.html">Shmuel Safra</a>: <br><b>On the complexity of equilibria. </b>67-71<br><a href="http://doi.acm.org/10.1145/509907.509920"><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/DengPS02">BibTeX</a></font> <li><a name="FiatGHK02" href="../../indices/a-tree/f/Fiat:Amos.html">Amos Fiat</a>, <a href="../../indices/a-tree/g/Goldberg:Andrew_V=.html">Andrew V. Goldberg</a>, <a href="../../indices/a-tree/h/Hartline:Jason_D=.html">Jason D. Hartline</a>, <a href="../../indices/a-tree/k/Karlin:Anna_R=.html">Anna R. Karlin</a>: <br><b>Competitive generalized auctions. </b>72-81<br><a href="http://doi.acm.org/10.1145/509907.509921"><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/FiatGHK02">BibTeX</a></font> <li><a name="DrineasKR02" href="../../indices/a-tree/d/Drineas:Petros.html">Petros Drineas</a>, <a href="../../indices/a-tree/k/Kerenidis:Iordanis.html">Iordanis Kerenidis</a>, <a href="../../indices/a-tree/r/Raghavan:Prabhakar.html">Prabhakar Raghavan</a>: <br><b>Competitive recommendation systems. </b>82-90<br><a href="http://doi.acm.org/10.1145/509907.509922"><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/DrineasKR02">BibTeX</a></font> <li><a name="Molloy02" href="../../indices/a-tree/m/Molloy:Michael.html">Michael Molloy</a>: <br><b>The Glauber dynamics on colourings of a graph with high girth and maximum degree. </b>91-98<br><a href="http://doi.acm.org/10.1145/509907.509924"><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/Molloy02">BibTeX</a></font> <li><a name="Gacs02" href="../../indices/a-tree/g/G=aacute=cs:P=eacute=ter.html">Péter Gács</a>: <br><b>Clairvoyant scheduling of random walks. </b>99-108<br><a href="http://doi.acm.org/10.1145/509907.509925"><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/Gacs02">BibTeX</a></font> <li><a name="BertsimasV02" href="../../indices/a-tree/b/Bertsimas:Dimitris.html">Dimitris Bertsimas</a>, <a href="../../indices/a-tree/v/Vempala:Santosh.html">Santosh Vempala</a>: <br><b>Solving convex programs by random walks. </b>109-115<br><a href="http://doi.acm.org/10.1145/509907.509926"><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/BertsimasV02">BibTeX</a></font> <li><a name="Papadimitriou02" href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: <br><b>The Joy of Theory. </b>116<br><a href="http://doi.acm.org/10.1145/509907.509908"><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/Papadimitriou02">BibTeX</a></font> <li><a name="BaswanaHS02" href="../../indices/a-tree/b/Baswana:Surender.html">Surender Baswana</a>, <a href="../../indices/a-tree/h/Hariharan:Ramesh.html">Ramesh Hariharan</a>, <a href="../../indices/a-tree/s/Sen:Sandeep.html">Sandeep Sen</a>: <br><b>Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths. </b>117-123<br><a href="http://doi.acm.org/10.1145/509907.509928"><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/BaswanaHS02">BibTeX</a></font> <li><a name="Kontogiannis02" href="../../indices/a-tree/k/Kontogiannis:Spyros_C=.html">Spyros C. Kontogiannis</a>: <br><b>Lower bounds & competitive algorithms for online scheduling of unit-size tasks to related machines. </b>124-133<br><a href="http://doi.acm.org/10.1145/509907.509929"><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/Kontogiannis02">BibTeX</a></font> <li><a name="Albers02" href="../../indices/a-tree/a/Albers:Susanne.html">Susanne Albers</a>: <br><b>On randomized online scheduling. </b>134-143<br><a href="http://doi.acm.org/10.1145/509907.509930"><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/Albers02">BibTeX</a></font> <li><a name="Raz02" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>: <br><b>On the complexity of matrix product. </b>144-151<br><a href="http://doi.acm.org/10.1145/509907.509932"><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/Raz02">BibTeX</a></font> <li><a name="GilbertGIMS02" href="../../indices/a-tree/g/Gilbert:Anna_C=.html">Anna C. Gilbert</a>, <a href="../../indices/a-tree/g/Guha:Sudipto.html">Sudipto Guha</a>, <a href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>, <a href="../../indices/a-tree/m/Muthukrishnan:S=.html">S. Muthukrishnan</a>, <a href="../../indices/a-tree/s/Strauss:Martin.html">Martin Strauss</a>: <br><b>Near-optimal sparse fourier representations via sampling. </b>152-161<br><a href="http://doi.acm.org/10.1145/509907.509933"><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/GilbertGIMS02">BibTeX</a></font> <li><a name="AroraK02" href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>, <a href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>: <br><b>Fitting algebraic curves to noisy data. </b>162-169<br><a href="http://doi.acm.org/10.1145/509907.509934"><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/AroraK02">BibTeX</a></font> <li><a name="ScharbrodtSS02" href="../../indices/a-tree/s/Scharbrodt:Mark.html">Mark Scharbrodt</a>, <a href="../../indices/a-tree/s/Schickinger:Thomas.html">Thomas Schickinger</a>, <a href="../../indices/a-tree/s/Steger:Angelika.html">Angelika Steger</a>: <br><b>A new average case analysis for completion time scheduling. </b>170-178<br><a href="http://doi.acm.org/10.1145/509907.509936"><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/ScharbrodtSS02">BibTeX</a></font> <li><a name="ChanLTW02" href="../../indices/a-tree/c/Chan:Wun=Tat.html">Wun-Tat Chan</a>, <a href="../../indices/a-tree/l/Lam:Tak_Wah.html">Tak Wah Lam</a>, <a href="../../indices/a-tree/t/Ting:Hing=Fung.html">Hing-Fung Ting</a>, <a href="../../indices/a-tree/w/Wong:Prudence_W=_H=.html">Prudence W. H. Wong</a>: <br><b>A unified analysis of hot video schedulers. </b>179-188<br><a href="http://doi.acm.org/10.1145/509907.509937"><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/ChanLTW02">BibTeX</a></font> <li><a name="SrinivasanA02" href="../../indices/a-tree/s/Srinivasan:Anand.html">Anand Srinivasan</a>, <a href="../../indices/a-tree/a/Anderson:James_H=.html">James H. Anderson</a>: <br><b>Optimal rate-based scheduling on multiprocessors. </b>189-198<br><a href="http://doi.acm.org/10.1145/509907.509938"><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/SrinivasanA02">BibTeX</a></font> <li><a name="AchlioptasM02" href="../../indices/a-tree/a/Achlioptas:Dimitris.html">Dimitris Achlioptas</a>, <a href="../../indices/a-tree/m/Moore:Cristopher.html">Cristopher Moore</a>: <br><b>Almost all graphs with average degree 4 are 3-colorable. </b>199-208<br><a href="http://doi.acm.org/10.1145/509907.509940"><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/AchlioptasM02">BibTeX</a></font> <li><a name="Molloy02a" href="../../indices/a-tree/m/Molloy:Michael.html">Michael Molloy</a>: <br><b>Models and thresholds for random constraint satisfaction problems. </b>209-217<br><a href="http://doi.acm.org/10.1145/509907.509941"><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/Molloy02a">BibTeX</a></font> <li><a name="Smyth02" href="../../indices/a-tree/s/Smyth:Clifford_D=.html">Clifford D. Smyth</a>: <br><b>Reimer's inequality and tardos' conjecture. </b>218-221<br><a href="http://doi.acm.org/10.1145/509907.509942"><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/Smyth02">BibTeX</a></font> <li><a name="ChienRS02" href="../../indices/a-tree/c/Chien:Steve.html">Steve Chien</a>, <a href="../../indices/a-tree/r/Rasmussen:Lars_Eilstrup.html">Lars Eilstrup Rasmussen</a>, <a href="../../indices/a-tree/s/Sinclair:Alistair.html">Alistair Sinclair</a>: <br><b>Clifford algebras and approximating the permanent. </b>222-231<br><a href="http://doi.acm.org/10.1145/509907.509944"><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/ChienRS02">BibTeX</a></font> <li><a name="AlonVKK02" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/v/Vega:Wenceslas_Fernandez_de_la.html">Wenceslas Fernandez de la Vega</a>, <a href="../../indices/a-tree/k/Kannan:Ravi.html">Ravi Kannan</a>, <a href="../../indices/a-tree/k/Karpinski:Marek.html">Marek Karpinski</a>: <br><b>Random sampling and approximation of MAX-CSP problems. </b>232-239<br><a href="http://doi.acm.org/10.1145/509907.509945"><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/AlonVKK02">BibTeX</a></font> <li><a name="CryanD02" href="../../indices/a-tree/c/Cryan:Mary.html">Mary Cryan</a>, <a href="../../indices/a-tree/d/Dyer:Martin_E=.html">Martin E. Dyer</a>: <br><b>A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant. </b>240-249<br><a href="http://doi.acm.org/10.1145/509907.509946"><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/CryanD02">BibTeX</a></font> <li><a name="BadoiuHI02" href="../../indices/a-tree/b/Badoiu:Mihai.html">Mihai Badoiu</a>, <a href="../../indices/a-tree/h/Har=Peled:Sariel.html">Sariel Har-Peled</a>, <a href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>: <br><b>Approximate clustering via core-sets. </b>250-257<br><a href="http://doi.acm.org/10.1145/509907.509947"><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/BadoiuHI02">BibTeX</a></font> <li><a name="AlbersFG02" href="../../indices/a-tree/a/Albers:Susanne.html">Susanne Albers</a>, <a href="../../indices/a-tree/f/Favrholdt:Lene_M=.html">Lene M. Favrholdt</a>, <a href="../../indices/a-tree/g/Giel:Oliver.html">Oliver Giel</a>: <br><b>On paging with locality of reference. </b>258-267<br><a href="http://doi.acm.org/10.1145/509907.509949"><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/AlbersFG02">BibTeX</a></font> <li><a name="ArgeBDHM02" href="../../indices/a-tree/a/Arge:Lars.html">Lars Arge</a>, <a href="../../indices/a-tree/b/Bender:Michael_A=.html">Michael A. Bender</a>, <a href="../../indices/a-tree/d/Demaine:Erik_D=.html">Erik D. Demaine</a>, <a href="../../indices/a-tree/h/Holland=Minkley:Bryan.html">Bryan Holland-Minkley</a>, <a href="../../indices/a-tree/m/Munro:J=_Ian.html">J. Ian Munro</a>: <br><b>Cache-oblivious priority queue and graph algorithm applications. </b>268-276<br><a href="http://doi.acm.org/10.1145/509907.509950"><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/ArgeBDHM02">BibTeX</a></font> <li><a name="Bachmat02" href="../../indices/a-tree/b/Bachmat:Eitan.html">Eitan Bachmat</a>: <br><b>Average case analysis for batched disk scheduling and increasing subsequences. </b>277-286<br><a href="http://doi.acm.org/10.1145/509907.509951"><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/Bachmat02">BibTeX</a></font> <li><a name="CzumajKV02" href="../../indices/a-tree/c/Czumaj:Artur.html">Artur Czumaj</a>, <a href="../../indices/a-tree/k/Krysta:Piotr.html">Piotr Krysta</a>, <a href="../../indices/a-tree/v/V=ouml=cking:Berthold.html">Berthold Vöcking</a>: <br><b>Selfish traffic allocation for server farms. </b>287-296<br><a href="http://doi.acm.org/10.1145/509907.509952"><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/CzumajKV02">BibTeX</a></font> <li><a name="ChekuriK02" href="../../indices/a-tree/c/Chekuri:Chandra.html">Chandra Chekuri</a>, <a href="../../indices/a-tree/k/Khanna:Sanjeev.html">Sanjeev Khanna</a>: <br><b>Approximation schemes for preemptive weighted flow time. </b>297-305<br><a href="http://doi.acm.org/10.1145/509907.509954"><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/ChekuriK02">BibTeX</a></font> <li><a name="CheriyanVV02" href="../../indices/a-tree/c/Cheriyan:Joseph.html">Joseph Cheriyan</a>, <a href="../../indices/a-tree/v/Vempala:Santosh.html">Santosh Vempala</a>, <a href="../../indices/a-tree/v/Vetta:Adrian.html">Adrian Vetta</a>: <br><b>Approximation algorithms for minimum-cost k-vertex connected subgraphs. </b>306-312<br><a href="http://doi.acm.org/10.1145/509907.509955"><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/CheriyanVV02">BibTeX</a></font> <li><a name="JainV02" href="../../indices/a-tree/j/Jain:Kamal.html">Kamal Jain</a>, <a href="../../indices/a-tree/v/Vazirani:Vijay_V=.html">Vijay V. Vazirani</a>: <br><b>Equitable cost allocations via primal-dual-type algorithms. </b>313-321<br><a href="http://doi.acm.org/10.1145/509907.509956"><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/JainV02">BibTeX</a></font> <li><a name="DworkS02" href="../../indices/a-tree/d/Dwork:Cynthia.html">Cynthia Dwork</a>, <a href="../../indices/a-tree/s/Stockmeyer:Larry_J=.html">Larry J. Stockmeyer</a>: <br><b>2-round zero knowledge and proof auditors. </b>322-331<br><a href="http://doi.acm.org/10.1145/509907.509958"><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/DworkS02">BibTeX</a></font> <li><a name="Goldreich02" href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>: <br><b>Concurrent zero-knowledge with timing, revisited. </b>332-340<br><a href="http://doi.acm.org/10.1145/509907.509959"><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/Goldreich02">BibTeX</a></font> <li><a name="DziembowskiM02" href="../../indices/a-tree/d/Dziembowski:Stefan.html">Stefan Dziembowski</a>, <a href="../../indices/a-tree/m/Maurer:Ueli_M=.html">Ueli M. Maurer</a>: <br><b>Tight security proofs for the bounded-storage model. </b>341-350<br><a href="http://doi.acm.org/10.1145/509907.509960"><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/DziembowskiM02">BibTeX</a></font> <li><a name="Khot02" href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>: <br><b>Hardness results for approximate hypergraph coloring. </b>351-359<br><a href="http://doi.acm.org/10.1145/509907.509962"><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/Khot02">BibTeX</a></font> <li><a name="SaksS02" href="../../indices/a-tree/s/Saks:Michael_E=.html">Michael E. Saks</a>, <a href="../../indices/a-tree/s/Sun:Xiaodong.html">Xiaodong Sun</a>: <br><b>Space lower bounds for distance approximation in the data stream model. </b>360-369<br><a href="http://doi.acm.org/10.1145/509907.509963"><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/SaksS02">BibTeX</a></font> <li><a name="AjtaiJKS02" href="../../indices/a-tree/a/Ajtai:Mikl=oacute=s.html">Miklós Ajtai</a>, <a href="../../indices/a-tree/j/Jayram:T=_S=.html">T. S. Jayram</a>, <a href="../../indices/a-tree/k/Kumar:Ravi.html">Ravi Kumar</a>, <a href="../../indices/a-tree/s/Sivakumar:D=.html">D. Sivakumar</a>: <br><b>Approximate counting of inversions in a data stream. </b>370-379<br><a href="http://doi.acm.org/10.1145/509907.509964"><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/AjtaiJKS02">BibTeX</a></font> <li><a name="Charikar02" href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>: <br><b>Similarity estimation techniques from rounding algorithms. </b>380-388<br><a href="http://doi.acm.org/10.1145/509907.509965"><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/Charikar02">BibTeX</a></font> <li><a name="GilbertGIKMS02" href="../../indices/a-tree/g/Gilbert:Anna_C=.html">Anna C. Gilbert</a>, <a href="../../indices/a-tree/g/Guha:Sudipto.html">Sudipto Guha</a>, <a href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>, <a href="../../indices/a-tree/k/Kotidis:Yannis.html">Yannis Kotidis</a>, <a href="../../indices/a-tree/m/Muthukrishnan:S=.html">S. Muthukrishnan</a>, <a href="../../indices/a-tree/s/Strauss:Martin.html">Martin Strauss</a>: <br><b>Fast, small-space algorithms for approximate histogram maintenance. </b>389-398<br><a href="http://doi.acm.org/10.1145/509907.509966"><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/GilbertGIKMS02">BibTeX</a></font> <li><a name="AnshelevichKK02" href="../../indices/a-tree/a/Anshelevich:Elliot.html">Elliot Anshelevich</a>, <a href="../../indices/a-tree/k/Kempe:David.html">David Kempe</a>, <a href="../../indices/a-tree/k/Kleinberg:Jon_M=.html">Jon M. Kleinberg</a>: <br><b>Stability of load balancing algorithms in dynamic adversarial systems. </b>399-406<br><a href="http://doi.acm.org/10.1145/509907.509968"><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/AnshelevichKK02">BibTeX</a></font> <li><a name="Adler02" href="../../indices/a-tree/a/Adler:Micah.html">Micah Adler</a>: <br><b>Tradeoffs in probabilistic packet marking for IP traceback. </b>407-418<br><a href="http://doi.acm.org/10.1145/509907.509969"><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/Adler02">BibTeX</a></font> <li><a name="CooperF02" href="../../indices/a-tree/c/Cooper:Colin.html">Colin Cooper</a>, <a href="../../indices/a-tree/f/Frieze:Alan_M=.html">Alan M. Frieze</a>: <br><b>Crawling on web graphs. </b>419-427<br><a href="http://doi.acm.org/10.1145/509907.509970"><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/CooperF02">BibTeX</a></font> <li><a name="Roughgarden02" href="../../indices/a-tree/r/Roughgarden:Tim.html">Tim Roughgarden</a>: <br><b>The price of anarchy is independent of the network topology. </b>428-437<br><a href="http://doi.acm.org/10.1145/509907.509971"><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/Roughgarden02">BibTeX</a></font> <li><a name="ElkinK02" href="../../indices/a-tree/e/Elkin:Michael.html">Michael Elkin</a>, <a href="../../indices/a-tree/k/Kortsarz:Guy.html">Guy Kortsarz</a>: <br><b>Combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. </b>438-447<br><a href="http://doi.acm.org/10.1145/509907.509972"><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/ElkinK02">BibTeX</a></font> <li><a name="AlekhnovichJPU02" href="../../indices/a-tree/a/Alekhnovich:Michael.html">Michael Alekhnovich</a>, <a href="../../indices/a-tree/j/Johannsen:Jan.html">Jan Johannsen</a>, <a href="../../indices/a-tree/p/Pitassi:Toniann.html">Toniann Pitassi</a>, <a href="../../indices/a-tree/u/Urquhart:Alasdair.html">Alasdair Urquhart</a>: <br><b>An exponential separation between regular and general resolution. </b>448-456<br><a href="http://doi.acm.org/10.1145/509907.509974"><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/AlekhnovichJPU02">BibTeX</a></font> <li><a name="Ben-Sasson02" href="../../indices/a-tree/b/Ben=Sasson:Eli.html">Eli Ben-Sasson</a>: <br><b>Size space tradeoffs for resolution. </b>457-464<br><a href="http://doi.acm.org/10.1145/509907.509975"><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-Sasson02">BibTeX</a></font> <li><a name="HellersteinR02" href="../../indices/a-tree/h/Hellerstein:Lisa.html">Lisa Hellerstein</a>, <a href="../../indices/a-tree/r/Raghavan:Vijay.html">Vijay Raghavan</a>: <br><b>Exact learning of DNF formulas using DNF hypotheses. </b>465-473<br><a href="http://doi.acm.org/10.1145/509907.509976"><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/HellersteinR02">BibTeX</a></font> <li><a name="FischerLNRRS02" href="../../indices/a-tree/f/Fischer:Eldar.html">Eldar Fischer</a>, <a href="../../indices/a-tree/l/Lehman:Eric.html">Eric Lehman</a>, <a href="../../indices/a-tree/n/Newman:Ilan.html">Ilan Newman</a>, <a href="../../indices/a-tree/r/Raskhodnikova:Sofya.html">Sofya Raskhodnikova</a>, <a href="../../indices/a-tree/r/Rubinfeld:Ronitt.html">Ronitt Rubinfeld</a>, <a href="../../indices/a-tree/s/Samorodnitsky:Alex.html">Alex Samorodnitsky</a>: <br><b>Monotonicity testing over general poset domains. </b>474-483<br><a href="http://doi.acm.org/10.1145/509907.509977"><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/FischerLNRRS02">BibTeX</a></font> <li><a name="BarakL02" href="../../indices/a-tree/b/Barak:Boaz.html">Boaz Barak</a>, <a href="../../indices/a-tree/l/Lindell:Yehuda.html">Yehuda Lindell</a>: <br><b>Strict polynomial-time in simulation and extraction. </b>484-493<br><a href="http://doi.acm.org/10.1145/509907.509979"><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/BarakL02">BibTeX</a></font> <li><a name="CanettiLOS02" href="../../indices/a-tree/c/Canetti:Ran.html">Ran Canetti</a>, <a href="../../indices/a-tree/l/Lindell:Yehuda.html">Yehuda Lindell</a>, <a href="../../indices/a-tree/o/Ostrovsky:Rafail.html">Rafail Ostrovsky</a>, <a href="../../indices/a-tree/s/Sahai:Amit.html">Amit Sahai</a>: <br><b>Universally composable two-party and multi-party secure computation. </b>494-503<br><a href="http://doi.acm.org/10.1145/509907.509980"><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/CanettiLOS02">BibTeX</a></font> <li><a name="Ajtai02" href="../../indices/a-tree/a/Ajtai:Mikl=oacute=s.html">Miklós Ajtai</a>: <br><b>The invasiveness of off-line memory checking. </b>504-513<br><a href="http://doi.acm.org/10.1145/509907.509981"><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/Ajtai02">BibTeX</a></font> <li><a name="LindellLR02" href="../../indices/a-tree/l/Lindell:Yehuda.html">Yehuda Lindell</a>, <a href="../../indices/a-tree/l/Lysyanskaya:Anna.html">Anna Lysyanskaya</a>, <a href="../../indices/a-tree/r/Rabin:Tal.html">Tal Rabin</a>: <br><b>On the composition of authenticated byzantine agreement. </b>514-523<br><a href="http://doi.acm.org/10.1145/509907.509982"><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/LindellLR02">BibTeX</a></font> <li><a name="AspnesSS02" href="../../indices/a-tree/a/Aspnes:James.html">James Aspnes</a>, <a href="../../indices/a-tree/s/Shah:Gauri.html">Gauri Shah</a>, <a href="../../indices/a-tree/s/Shah:Jatin.html">Jatin Shah</a>: <br><b>Wait-free consensus with infinite arrivals. </b>524-533<br><a href="http://doi.acm.org/10.1145/509907.509983"><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/AspnesSS02">BibTeX</a></font> <li><a name="Feige02" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>: <br><b>Relations between average case complexity and approximation complexity. </b>534-543<br><a href="http://doi.acm.org/10.1145/509907.509985"><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/Feige02">BibTeX</a></font> <li><a name="Holmerin02" href="../../indices/a-tree/h/Holmerin:Jonas.html">Jonas Holmerin</a>: <br><b>Vertex cover on 4-regular hyper-graphs is hard to approximate within 2-epsilon. </b>544-552<br><a href="http://doi.acm.org/10.1145/509907.509986"><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/Holmerin02">BibTeX</a></font> <li><a name="Raz02a" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>: <br><b>Resolution lower bounds for the weak pigeonhole principle. </b>553-562<br><a href="http://doi.acm.org/10.1145/509907.509987"><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/Raz02a">BibTeX</a></font> <li><a name="Ben-Sasson02a" href="../../indices/a-tree/b/Ben=Sasson:Eli.html">Eli Ben-Sasson</a>: <br><b>Hard examples for bounded depth frege. </b>563-572<br><a href="http://doi.acm.org/10.1145/509907.509988"><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-Sasson02a">BibTeX</a></font> <li><a name="KaplanST02" href="../../indices/a-tree/k/Kaplan:Haim.html">Haim Kaplan</a>, <a href="../../indices/a-tree/s/Shafrir:Nira.html">Nira Shafrir</a>, <a href="../../indices/a-tree/t/Tarjan:Robert_Endre.html">Robert Endre Tarjan</a>: <br><b>Meldable heaps and boolean union-find. </b>573-582<br><a href="http://doi.acm.org/10.1145/509907.509990"><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/KaplanST02">BibTeX</a></font> <li><a name="BrodalLMTT02" href="../../indices/a-tree/b/Brodal:Gerth_St=oslash=lting.html">Gerth Stølting Brodal</a>, <a href="../../indices/a-tree/l/Lagogiannis:George.html">George Lagogiannis</a>, <a href="../../indices/a-tree/m/Makris:Christos.html">Christos Makris</a>, <a href="../../indices/a-tree/t/Tsakalidis:Athanasios_K=.html">Athanasios K. Tsakalidis</a>, <a href="../../indices/a-tree/t/Tsichlas:Kostas.html">Kostas Tsichlas</a>: <br><b>Optimal finger search trees in the pointer machine. </b>583-591<br><a href="http://doi.acm.org/10.1145/509907.509991"><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/BrodalLMTT02">BibTeX</a></font> <li><a name="ColeH02" 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>Verifying candidate matches in sparse and wildcard matching. </b>592-601<br><a href="http://doi.acm.org/10.1145/509907.509992"><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/ColeH02">BibTeX</a></font> <li><a name="Han02" href="../../indices/a-tree/h/Han:Yijie.html">Yijie Han</a>: <br><b>Deterministic sorting in O(nlog log n) time and linear space. </b>602-608<br><a href="http://doi.acm.org/10.1145/509907.509993"><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/Han02">BibTeX</a></font> <li><a name="Micciancio02" href="../../indices/a-tree/m/Micciancio:Daniele.html">Daniele Micciancio</a>: <br><b>Improved cryptographic hash functions with worst-case/average-case connection. </b>609-618<br><a href="http://doi.acm.org/10.1145/509907.509995"><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/Micciancio02">BibTeX</a></font> <li><a name="Sivakumar02" href="../../indices/a-tree/s/Sivakumar:D=.html">D. Sivakumar</a>: <br><b>Algorithmic derandomization via complexity theory. </b>619-626<br><a href="http://doi.acm.org/10.1145/509907.509996"><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/Sivakumar02">BibTeX</a></font> <li><a name="Umans02" href="../../indices/a-tree/u/Umans:Christopher.html">Christopher Umans</a>: <br><b>Pseudo-random generators for all hardnesses. </b>627-634<br><a href="http://doi.acm.org/10.1145/509907.509997"><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/Umans02">BibTeX</a></font> <li><a name="Aaronson02" href="../../indices/a-tree/a/Aaronson:Scott.html">Scott Aaronson</a>: <br><b>Quantum lower bound for the collision problem. </b>635-642<br><a href="http://doi.acm.org/10.1145/509907.509999"><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/Aaronson02">BibTeX</a></font> <li><a name="CrepeauGS02" href="../../indices/a-tree/c/Cr=eacute=peau:Claude.html">Claude Crépeau</a>, <a href="../../indices/a-tree/g/Gottesman:Daniel.html">Daniel Gottesman</a>, <a href="../../indices/a-tree/s/Smith:Adam.html">Adam Smith</a>: <br><b>Secure multi-party quantum computation. </b>643-652<br><a href="http://doi.acm.org/10.1145/509907.510000"><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/CrepeauGS02">BibTeX</a></font> <li><a name="Hallgren02" href="../../indices/a-tree/h/Hallgren:Sean.html">Sean Hallgren</a>: <br><b>Polynomial-time quantum algorithms for Pell's equation and the principal ideal problem. </b>653-658<br><a href="http://doi.acm.org/10.1145/509907.510001"><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/Hallgren02">BibTeX</a></font> <li><a name="CapalboRVW02" href="../../indices/a-tree/c/Capalbo:Michael_R=.html">Michael R. Capalbo</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>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>Randomness conductors and constant-degree lossless expanders. </b>659-668<br><a href="http://doi.acm.org/10.1145/509907.510003"><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/CapalboRVW02">BibTeX</a></font> <li><a name="MeshulamW02" href="../../indices/a-tree/m/Meshulam:Roy.html">Roy Meshulam</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>Expanders from symmetric codes. </b>669-677<br><a href="http://doi.acm.org/10.1145/509907.510004"><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/MeshulamW02">BibTeX</a></font> <li><a name="BatuDKR02" href="../../indices/a-tree/b/Batu:Tugkan.html">Tugkan Batu</a>, <a href="../../indices/a-tree/d/Dasgupta:Sanjoy.html">Sanjoy Dasgupta</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>The complexity of approximating entropy. </b>678-687<br><a href="http://doi.acm.org/10.1145/509907.510005"><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/BatuDKR02">BibTeX</a></font> <li><a name="BeameV02" href="../../indices/a-tree/b/Beame:Paul.html">Paul Beame</a>, <a href="../../indices/a-tree/v/Vee:Erik.html">Erik Vee</a>: <br><b>Time-space tradeoffs, multiparty communication complexity, and nearest-neighbor problems. </b>688-697<br><a href="http://doi.acm.org/10.1145/509907.510006"><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/BeameV02">BibTeX</a></font> <li><a name="NayakS02" href="../../indices/a-tree/n/Nayak:Ashwin.html">Ashwin Nayak</a>, <a href="../../indices/a-tree/s/Salzman:Julia.html">Julia Salzman</a>: <br><b>On communication over an entanglement-assisted quantum channel. </b>698-704<br><a href="http://doi.acm.org/10.1145/509907.510007"><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/NayakS02">BibTeX</a></font> <li><a name="LinialMN02" href="../../indices/a-tree/l/Linial:Nathan.html">Nathan Linial</a>, <a href="../../indices/a-tree/m/Magen:Avner.html">Avner Magen</a>, <a href="../../indices/a-tree/n/Naor:Assaf.html">Assaf Naor</a>: <br><b>Girth and euclidean distortion. </b>705-711<br><a href="http://doi.acm.org/10.1145/509907.510009"><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/LinialMN02">BibTeX</a></font> <li><a name="Bas02" href="../../indices/a-tree/b/Basu:Saugata.html">Saugata Basu</a>: <br><b>Computing the betti numbers of arrangements. </b>712-720<br><a href="http://doi.acm.org/10.1145/509907.510010"><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/Bas02">BibTeX</a></font> <li><a name="AryaMM02" href="../../indices/a-tree/a/Arya:Sunil.html">Sunil Arya</a>, <a href="../../indices/a-tree/m/Malamatos:Theocharis.html">Theocharis Malamatos</a>, <a href="../../indices/a-tree/m/Mount:David_M=.html">David M. Mount</a>: <br><b>Space-efficient approximate Voronoi diagrams. </b>721-730<br><a href="http://doi.acm.org/10.1145/509907.510011"><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/AryaMM02">BibTeX</a></font> <li><a name="JainMS02" href="../../indices/a-tree/j/Jain:Kamal.html">Kamal Jain</a>, <a href="../../indices/a-tree/m/Mahdian:Mohammad.html">Mohammad Mahdian</a>, <a href="../../indices/a-tree/s/Saberi:Amin.html">Amin Saberi</a>: <br><b>A new greedy approach for facility location problems. </b>731-740<br><a href="http://doi.acm.org/10.1145/509907.510012"><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/JainMS02">BibTeX</a></font> <li><a name="KargerR02" href="../../indices/a-tree/k/Karger:David_R=.html">David R. Karger</a>, <a href="../../indices/a-tree/r/Ruhl:Matthias.html">Matthias Ruhl</a>: <br><b>Finding nearest neighbors in growth-restricted metrics. </b>741-750<br><a href="http://doi.acm.org/10.1145/509907.510013"><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/KargerR02">BibTeX</a></font> <li><a name="ODonnell02" href="../../indices/a-tree/o/O=Donnell:Ryan.html">Ryan O'Donnell</a>: <br><b>Hardness amplification within NP. </b>751-760<br><a href="http://doi.acm.org/10.1145/509907.510015"><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/ODonnell02">BibTeX</a></font> <li><a name="AgolHT02" href="../../indices/a-tree/a/Agol:Ian.html">Ian Agol</a>, <a href="../../indices/a-tree/h/Hass:Joel.html">Joel Hass</a>, <a href="../../indices/a-tree/t/Thurston:William_P=.html">William P. Thurston</a>: <br><b>3-manifold knot genus is NP-complet. </b>761-766<br><a href="http://doi.acm.org/10.1145/509907.510016"><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/AgolHT02">BibTeX</a></font> <li><a name="Khot02a" href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>: <br><b>On the power of unique 2-prover 1-round games. </b>767-775<br><a href="http://doi.acm.org/10.1145/509907.510017"><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/Khot02a">BibTeX</a></font> <li><a name="JacksonKS02" href="../../indices/a-tree/j/Jackson:Jeffrey_C=.html">Jeffrey C. Jackson</a>, <a href="../../indices/a-tree/k/Klivans:Adam.html">Adam Klivans</a>, <a href="../../indices/a-tree/s/Servedio:Rocco_A=.html">Rocco A. Servedio</a>: <br><b>Learnability beyond AC0. </b>776-784<br><a href="http://doi.acm.org/10.1145/509907.510018"><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/JacksonKS02">BibTeX</a></font> <li><a name="GolinKY02" href="../../indices/a-tree/g/Golin:Mordecai_J=.html">Mordecai J. Golin</a>, <a href="../../indices/a-tree/k/Kenyon:Claire.html">Claire Kenyon</a>, <a href="../../indices/a-tree/y/Young:Neal_E=.html">Neal E. Young</a>: <br><b>Huffman coding with unequal letter costs. </b>785-791<br><a href="http://doi.acm.org/10.1145/509907.510020"><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/GolinKY02">BibTeX</a></font> <li><a name="CharikarLLPPRSS02" href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/l/Lehman:Eric.html">Eric Lehman</a>, <a href="../../indices/a-tree/l/Liu:Ding.html">Ding Liu</a>, <a href="../../indices/a-tree/p/Panigrahy:Rina.html">Rina Panigrahy</a>, <a href="../../indices/a-tree/p/Prabhakaran:Manoj.html">Manoj Prabhakaran</a>, <a href="../../indices/a-tree/r/Rasala:April.html">April Rasala</a>, <a href="../../indices/a-tree/s/Sahai:Amit.html">Amit Sahai</a>, <a href="../../indices/a-tree/s/Shelat:Abhi.html">Abhi Shelat</a>: <br><b>Approximating the smallest grammar: Kolmogorov complexity in natural models. </b>792-801<br><a href="http://doi.acm.org/10.1145/509907.510021"><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/CharikarLLPPRSS02">BibTeX</a></font> <li><a name="Guruswami02" href="../../indices/a-tree/g/Guruswami:Venkatesan.html">Venkatesan Guruswami</a>: <br><b>Limits to list decodability of linear codes. </b>802-811<br><a href="http://doi.acm.org/10.1145/509907.510022"><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/Guruswami02">BibTeX</a></font> <li><a name="GuruswamiI02" href="../../indices/a-tree/g/Guruswami:Venkatesan.html">Venkatesan Guruswami</a>, <a href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>: <br><b>Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets. </b>812-821<br><a href="http://doi.acm.org/10.1145/509907.510023"><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/GuruswamiI02">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
