stoc2005.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>STOC 2005</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>37. <a href="index.html">STOC</a> 2005: Baltimore, MD, USA</h1> <a name="2005" href="../../indices/a-tree/g/Gabow:Harold_N=.html">Harold N. Gabow</a>, <a href="../../indices/a-tree/f/Fagin:Ronald.html">Ronald Fagin</a> (Eds.): Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005. ACM 2005, ISBN 1-58113-960-8 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/2005">BibTeX</a></font> <h2>Session 1A</h2> <ul> <li><a name="BarakKSSW05" href="../../indices/a-tree/b/Barak:Boaz.html">Boaz Barak</a>, <a href="../../indices/a-tree/k/Kindler:Guy.html">Guy Kindler</a>, <a href="../../indices/a-tree/s/Shaltiel:Ronen.html">Ronen Shaltiel</a>, <a href="../../indices/a-tree/s/Sudakov:Benny.html">Benny Sudakov</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. </b>1-10<br><a href="http://doi.acm.org/10.1145/1060590.1060592"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BarakKSSW05">BibTeX</a></font> <li><a name="Raz05" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>: <br><b>Extractors with weak random seeds. </b>11-20<br><a href="http://doi.acm.org/10.1145/1060590.1060593"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Raz05">BibTeX</a></font> <li><a name="Bogdanov05" href="../../indices/a-tree/b/Bogdanov:Andrej.html">Andrej Bogdanov</a>: <br><b>Pseudorandom generators for low degree polynomials. </b>21-30<br><a href="http://doi.acm.org/10.1145/1060590.1060594"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Bogdanov05">BibTeX</a></font> <li><a name="Trevisan05" href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>: <br><b>On uniform amplification of hardness in NP. </b>31-38<br><a href="http://doi.acm.org/10.1145/1060590.1060595"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Trevisan05">BibTeX</a></font> </ul> <h2>Session 1B</h2> <ul> <li><a name="BriestKV05" href="../../indices/a-tree/b/Briest:Patrick.html">Patrick Briest</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>Approximation techniques for utilitarian mechanism design. </b>39-48<br><a href="http://doi.acm.org/10.1145/1060590.1060597"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BriestKV05">BibTeX</a></font> <li><a name="Papadimitriou05" href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: <br><b>Computing correlated equilibria in multi-player games. </b>49-56<br><a href="http://doi.acm.org/10.1145/1060590.1060598"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Papadimitriou05">BibTeX</a></font> <li><a name="AwerbuchAE05" 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/e/Epstein:Amir.html">Amir Epstein</a>: <br><b>Large the price of routing unsplittable flow. </b>57-66<br><a href="http://doi.acm.org/10.1145/1060590.1060599"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AwerbuchAE05">BibTeX</a></font> <li><a name="ChristodoulouK05" href="../../indices/a-tree/c/Christodoulou:George.html">George Christodoulou</a>, <a href="../../indices/a-tree/k/Koutsoupias:Elias.html">Elias Koutsoupias</a>: <br><b>The price of anarchy of finite congestion games. </b>67-73<br><a href="http://doi.acm.org/10.1145/1060590.1060600"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChristodoulouK05">BibTeX</a></font> <li><a name="CodenottiMV05" href="../../indices/a-tree/c/Codenotti:Bruno.html">Bruno Codenotti</a>, <a href="../../indices/a-tree/m/McCune:Benton.html">Benton McCune</a>, <a href="../../indices/a-tree/v/Varadarajan:Kasturi_R=.html">Kasturi R. Varadarajan</a>: <br><b>Market equilibrium via the excess demand function. </b>74-83<br><a href="http://doi.acm.org/10.1145/1060590.1060601"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CodenottiMV05">BibTeX</a></font> </ul> <h2>Session 2A</h2> <ul> <li><a name="Regev05" href="../../indices/a-tree/r/Regev:Oded.html">Oded Regev</a>: <br><b>On lattices, learning with errors, random linear codes, and cryptography. </b>84-93<br><a href="http://doi.acm.org/10.1145/1060590.1060603"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Regev05">BibTeX</a></font> <li><a name="Ajtai05" href="../../indices/a-tree/a/Ajtai:Mikl=oacute=s.html">Miklós Ajtai</a>: <br><b>Representing hard lattices with O(n log n) bits. </b>94-103<br><a href="http://doi.acm.org/10.1145/1060590.1060604"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Ajtai05">BibTeX</a></font> </ul> <h2>Session 2B</h2> <ul> <li><a name="MortensenPP05" href="../../indices/a-tree/m/Mortensen:Christian_Worm.html">Christian Worm Mortensen</a>, <a href="../../indices/a-tree/p/Pagh:Rasmus.html">Rasmus Pagh</a>, <a href="../../indices/a-tree/p/Patrascu:Mihai.html">Mihai Patrascu</a>: <br><b>On dynamic range reporting in one dimension. </b>104-111<br><a href="http://doi.acm.org/10.1145/1060590.1060606"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MortensenPP05">BibTeX</a></font> <li><a name="Thorup05" href="../../indices/a-tree/t/Thorup:Mikkel.html">Mikkel Thorup</a>: <br><b>Worst-case update times for fully-dynamic all-pairs shortest paths. </b>112-119<br><a href="http://doi.acm.org/10.1145/1060590.1060607"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Thorup05">BibTeX</a></font> </ul> <h2>Keynote</h2> <ul> <li><a name="Fortnow05" href="../../indices/a-tree/f/Fortnow:Lance.html">Lance Fortnow</a>: <br><b>Beyond NP: the work and legacy of Larry Stockmeyer. </b>120-127<br><a href="http://doi.acm.org/10.1145/1060590.1060609"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Fortnow05">BibTeX</a></font> </ul> <h2>Session 4A</h2> <ul> <li><a name="AlonS05" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/s/Shapira:Asaf.html">Asaf Shapira</a>: <br><b>Every monotone graph property is testable. </b>128-137<br><a href="http://doi.acm.org/10.1145/1060590.1060611"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AlonS05">BibTeX</a></font> <li><a name="FischerN05" href="../../indices/a-tree/f/Fischer:Eldar.html">Eldar Fischer</a>, <a href="../../indices/a-tree/n/Newman:Ilan.html">Ilan Newman</a>: <br><b>Testing versus estimation of graph properties. </b>138-146<br><a href="http://doi.acm.org/10.1145/1060590.1060612"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FischerN05">BibTeX</a></font> <li><a name="RubinfeldS05" href="../../indices/a-tree/r/Rubinfeld:Ronitt.html">Ronitt Rubinfeld</a>, <a href="../../indices/a-tree/s/Servedio:Rocco_A=.html">Rocco A. Servedio</a>: <br><b>Testing monotone high-dimensional distributions. </b>147-156<br><a href="http://doi.acm.org/10.1145/1060590.1060613"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/RubinfeldS05">BibTeX</a></font> <li><a name="FriedlIS05" href="../../indices/a-tree/f/Friedl:Katalin.html">Katalin Friedl</a>, <a href="../../indices/a-tree/i/Ivanyos:G=aacute=bor.html">Gábor Ivanyos</a>, <a href="../../indices/a-tree/s/Santha:Miklos.html">Miklos Santha</a>: <br><b>Efficient testing of groups. </b>157-166<br><a href="http://doi.acm.org/10.1145/1060590.1060614"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FriedlIS05">BibTeX</a></font> </ul> <h2>Session 4B</h2> <ul> <li><a name="CheriyanV05" href="../../indices/a-tree/c/Cheriyan:Joseph.html">Joseph Cheriyan</a>, <a href="../../indices/a-tree/v/Vetta:Adrian.html">Adrian Vetta</a>: <br><b>Approximation algorithms for network design with metric costs. </b>167-175<br><a href="http://doi.acm.org/10.1145/1060590.1060616"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CheriyanV05">BibTeX</a></font> <li><a name="CharikarK05" href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/k/Karagiozova:Adriana.html">Adriana Karagiozova</a>: <br><b>On non-uniform multicommodity buy-at-bulk network design. </b>176-182<br><a href="http://doi.acm.org/10.1145/1060590.1060617"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CharikarK05">BibTeX</a></font> <li><a name="ChekuriKS05" href="../../indices/a-tree/c/Chekuri:Chandra.html">Chandra Chekuri</a>, <a href="../../indices/a-tree/k/Khanna:Sanjeev.html">Sanjeev Khanna</a>, <a href="../../indices/a-tree/s/Shepherd:F=_Bruce.html">F. Bruce Shepherd</a>: <br><b>Multicommodity flow, well-linked terminals, and routing problems. </b>183-192<br><a href="http://doi.acm.org/10.1145/1060590.1060618"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChekuriKS05">BibTeX</a></font> <li><a name="HajiaghayiKLR05" href="../../indices/a-tree/h/Hajiaghayi:Mohammad_Taghi.html">Mohammad Taghi Hajiaghayi</a>, <a href="../../indices/a-tree/k/Kim:Jeong_Han.html">Jeong Han Kim</a>, <a href="../../indices/a-tree/l/Leighton:Tom.html">Tom Leighton</a>, <a href="../../indices/a-tree/r/R=auml=cke:Harald.html">Harald Räcke</a>: <br><b>Oblivious routing in directed graphs with random demands. </b>193-201<br><a href="http://doi.acm.org/10.1145/1060590.1060619"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HajiaghayiKLR05">BibTeX</a></font> </ul> <h2>Session 5A</h2> <ul> <li><a name="IndykW05" href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>, <a href="../../indices/a-tree/w/Woodruff:David_P=.html">David P. Woodruff</a>: <br><b>Optimal approximations of the frequency moments of data streams. </b>202-208<br><a href="http://doi.acm.org/10.1145/1060590.1060621"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/IndykW05">BibTeX</a></font> <li><a name="FrahlingS05" href="../../indices/a-tree/f/Frahling:Gereon.html">Gereon Frahling</a>, <a href="../../indices/a-tree/s/Sohler:Christian.html">Christian Sohler</a>: <br><b>Coresets in dynamic geometric data streams. </b>209-217<br><a href="http://doi.acm.org/10.1145/1060590.1060622"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FrahlingS05">BibTeX</a></font> <li><a name="OstrovskyR05" 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>Low distortion embeddings for edit distance. </b>218-224<br><a href="http://doi.acm.org/10.1145/1060590.1060623"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/OstrovskyR05">BibTeX</a></font> <li><a name="BadoiuCIS05" href="../../indices/a-tree/b/Badoiu:Mihai.html">Mihai Badoiu</a>, <a href="../../indices/a-tree/c/Chuzhoy:Julia.html">Julia Chuzhoy</a>, <a href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>, <a href="../../indices/a-tree/s/Sidiropoulos:Anastasios.html">Anastasios Sidiropoulos</a>: <br><b>Low-distortion embeddings of general metrics into the line. </b>225-233<br><a href="http://doi.acm.org/10.1145/1060590.1060624"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BadoiuCIS05">BibTeX</a></font> </ul> <h2>Session 5B</h2> <ul> <li><a name="BojanczykC05" href="../../indices/a-tree/b/Bojanczyk:Mikolaj.html">Mikolaj Bojanczyk</a>, <a href="../../indices/a-tree/c/Colcombet:Thomas.html">Thomas Colcombet</a>: <br><b>Tree-walking automata do not recognize all regular languages. </b>234-243<br><a href="http://doi.acm.org/10.1145/1060590.1060626"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BojanczykC05">BibTeX</a></font> <li><a name="BenjaminiSW05" href="../../indices/a-tree/b/Benjamini:Itai.html">Itai Benjamini</a>, <a href="../../indices/a-tree/s/Schramm:Oded.html">Oded Schramm</a>, <a href="../../indices/a-tree/w/Wilson:David_Bruce.html">David Bruce Wilson</a>: <br><b>Balanced boolean functions that can be evaluated so that every input bit is unlikely to be read. </b>244-250<br><a href="http://doi.acm.org/10.1145/1060590.1060627"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BenjaminiSW05">BibTeX</a></font> <li><a name="Alekhnovich05" href="../../indices/a-tree/a/Alekhnovich:Michael.html">Michael Alekhnovich</a>: <br><b>Lower bounds for k-DNF resolution on random 3-CNFs. </b>251-256<br><a href="http://doi.acm.org/10.1145/1060590.1060628"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Alekhnovich05">BibTeX</a></font> <li><a name="KouckyPT05" href="../../indices/a-tree/k/Kouck=yacute=:Michal.html">Michal Koucký</a>, <a href="../../indices/a-tree/p/Pudl=aacute=k:Pavel.html">Pavel Pudlák</a>, <a href="../../indices/a-tree/t/Th=eacute=rien:Denis.html">Denis Thérien</a>: <br><b>Bounded-depth circuits: separating wires from gates. </b>257-265<br><a href="http://doi.acm.org/10.1145/1060590.1060629"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KouckyPT05">BibTeX</a></font> </ul> <h2>Session 6A</h2> <ul> <li><a name="Ben-SassonS05" href="../../indices/a-tree/b/Ben=Sasson:Eli.html">Eli Ben-Sasson</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: <br><b>Simple PCPs with poly-log rate and query complexity. </b>266-275<br><a href="http://doi.acm.org/10.1145/1060590.1060631"><i>Electronic Edition</i></a> (<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-SassonS05">BibTeX</a></font> <li><a name="AndrewsZ05" 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>Hardness of the undirected edge-disjoint paths problem. </b>276-283<br><a href="http://doi.acm.org/10.1145/1060590.1060632"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AndrewsZ05">BibTeX</a></font> <li><a name="AndrewsZ05a" 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>Hardness of the undirected congestion minimization problem. </b>284-293<br><a href="http://doi.acm.org/10.1145/1060590.1060633"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AndrewsZ05a">BibTeX</a></font> <li><a name="AlekhnovichAT05" href="../../indices/a-tree/a/Alekhnovich:Michael.html">Michael Alekhnovich</a>, <a href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>, <a href="../../indices/a-tree/t/Tourlakis:Iannis.html">Iannis Tourlakis</a>: <br><b>Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. </b>294-303<br><a href="http://doi.acm.org/10.1145/1060590.1060634"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AlekhnovichAT05">BibTeX</a></font> </ul> <h2>Session 6B</h2> <ul> <li><a name="BasuPR05" href="../../indices/a-tree/b/Basu:Saugata.html">Saugata Basu</a>, <a href="../../indices/a-tree/p/Pollack:Richard.html">Richard Pollack</a>, <a href="../../indices/a-tree/r/Roy:Marie=Fran=ccedil=oise.html">Marie-Françoise Roy</a>: <br><b>Computing the first Betti number and the connected components of semi-algebraic sets. </b>304-312<br><a href="http://doi.acm.org/10.1145/1060590.1060636"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BasuPR05">BibTeX</a></font> <li><a name="Basu05" href="../../indices/a-tree/b/Basu:Saugata.html">Saugata Basu</a>: <br><b>Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities. </b>313-322<br><a href="http://doi.acm.org/10.1145/1060590.1060637"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Basu05">BibTeX</a></font> <li><a name="ChenD05" href="../../indices/a-tree/c/Chen:Xi.html">Xi Chen</a>, <a href="../../indices/a-tree/d/Deng:Xiaotie.html">Xiaotie Deng</a>: <br><b>On algorithms for discrete and approximate brouwer fixed points. </b>323-330<br><a href="http://doi.acm.org/10.1145/1060590.1060638"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChenD05">BibTeX</a></font> <li><a name="AzarE05" href="../../indices/a-tree/a/Azar:Yossi.html">Yossi Azar</a>, <a href="../../indices/a-tree/e/Epstein:Amir.html">Amir Epstein</a>: <br><b>Convex programming for scheduling unrelated parallel machines. </b>331-337<br><a href="http://doi.acm.org/10.1145/1060590.1060639"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AzarE05">BibTeX</a></font> </ul> <h2>Session 7A</h2> <ul> <li><a name="SanghviV05" href="../../indices/a-tree/s/Sanghvi:Saurabh.html">Saurabh Sanghvi</a>, <a href="../../indices/a-tree/v/Vadhan:Salil_P=.html">Salil P. Vadhan</a>: <br><b>The round complexity of two-party random selection. </b>338-347<br><a href="http://doi.acm.org/10.1145/1060590.1060641"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/SanghviV05">BibTeX</a></font> <li><a name="FortnowST05" href="../../indices/a-tree/f/Fortnow:Lance.html">Lance Fortnow</a>, <a href="../../indices/a-tree/s/Santhanam:Rahul.html">Rahul Santhanam</a>, <a href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>: <br><b>Hierarchies for semantic classes. </b>348-355<br><a href="http://doi.acm.org/10.1145/1060590.1060642"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FortnowST05">BibTeX</a></font> </ul> <h2>Session 7B</h2> <ul> <li><a name="KaplanKM05" href="../../indices/a-tree/k/Kaplan:Haim.html">Haim Kaplan</a>, <a href="../../indices/a-tree/k/Kushilevitz:Eyal.html">Eyal Kushilevitz</a>, <a href="../../indices/a-tree/m/Mansour:Yishay.html">Yishay Mansour</a>: <br><b>Learning with attribute costs. </b>356-365<br><a href="http://doi.acm.org/10.1145/1060590.1060644"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KaplanKM05">BibTeX</a></font> <li><a name="MosselR05" href="../../indices/a-tree/m/Mossel:Elchanan.html">Elchanan Mossel</a>, <a href="../../indices/a-tree/r/Roch:S=eacute=bastien.html">Sébastien Roch</a>: <br><b>Learning nonsingular phylogenies and hidden Markov models. </b>366-375<br><a href="http://doi.acm.org/10.1145/1060590.1060645"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MosselR05">BibTeX</a></font> </ul> <h2>Best Paper</h2> <ul> <li><a name="Reingold05" href="../../indices/a-tree/r/Reingold:Omer.html">Omer Reingold</a>: <br><b>Undirected ST-connectivity in log-space. </b>376-385<br><a href="http://doi.acm.org/10.1145/1060590.1060647"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Reingold05">BibTeX</a></font> </ul> <h2>Session 9A</h2> <ul> <li><a name="JiaLNRS05" href="../../indices/a-tree/j/Jia:Lujun.html">Lujun Jia</a>, <a href="../../indices/a-tree/l/Lin:Guolong.html">Guolong Lin</a>, <a href="../../indices/a-tree/n/Noubir:Guevara.html">Guevara Noubir</a>, <a href="../../indices/a-tree/r/Rajaraman:Rajmohan.html">Rajmohan Rajaraman</a>, <a href="../../indices/a-tree/s/Sundaram:Ravi.html">Ravi Sundaram</a>: <br><b>Universal approximations for TSP, Steiner tree, and set cover. </b>386-395<br><a href="http://doi.acm.org/10.1145/1060590.1060649"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/JiaLNRS05">BibTeX</a></font> <li><a name="Garg05" href="../../indices/a-tree/g/Garg:Naveen.html">Naveen Garg</a>: <br><b>Saving an epsilon: a 2-approximation for the k-MST problem in graphs. </b>396-402<br><a href="http://doi.acm.org/10.1145/1060590.1060650"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Garg05">BibTeX</a></font> <li><a name="Morris05" href="../../indices/a-tree/m/Morris:Ben.html">Ben Morris</a>: <br><b>The mixing time of the Thorp shuffle. </b>403-412<br><a href="http://doi.acm.org/10.1145/1060590.1060651"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Morris05">BibTeX</a></font> <li><a name="CryanDR05" 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>, <a href="../../indices/a-tree/r/Randall:Dana.html">Dana Randall</a>: <br><b>Approximately counting integral flows and cell-bounded contingency tables. </b>413-422<br><a href="http://doi.acm.org/10.1145/1060590.1060652"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CryanDR05">BibTeX</a></font> </ul> <h2>Session 9B</h2> <ul> <li><a name="Vu05" href="../../indices/a-tree/v/Vu:Van_H=.html">Van H. Vu</a>: <br><b>Spectral norm of random matrices. </b>423-430<br><a href="http://doi.acm.org/10.1145/1060590.1060654"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Vu05">BibTeX</a></font> <li><a name="TaoV05" href="../../indices/a-tree/t/Tao:Terence.html">Terence Tao</a>, <a href="../../indices/a-tree/v/Vu:Van_H=.html">Van H. Vu</a>: <br><b>On random pm 1 matrices: singularity and determinant. </b>431-440<br><a href="http://doi.acm.org/10.1145/1060590.1060655"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/TaoV05">BibTeX</a></font> <li><a name="FlaxmanFV05" href="../../indices/a-tree/f/Flaxman:Abraham.html">Abraham Flaxman</a>, <a href="../../indices/a-tree/f/Frieze:Alan_M=.html">Alan M. Frieze</a>, <a href="../../indices/a-tree/v/Vera:Juan_Carlos.html">Juan Carlos Vera</a>: <br><b>On the average case performance of some greedy approximation algorithms for the uncapacitated facility location problem. </b>441-449<br><a href="http://doi.acm.org/10.1145/1060590.1060656"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FlaxmanFV05">BibTeX</a></font> <li><a name="AdlerEM05" href="../../indices/a-tree/a/Adler:Micah.html">Micah Adler</a>, <a href="../../indices/a-tree/e/Edmonds:Jeff.html">Jeff Edmonds</a>, <a href="../../indices/a-tree/m/Matousek:Jir=iacute=.html">Jirí Matousek</a>: <br><b>Towards asymptotic optimality in probabilistic packet marking. </b>450-459<br><a href="http://doi.acm.org/10.1145/1060590.1060657"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AdlerEM05">BibTeX</a></font> </ul> <h2>Session 10A</h2> <ul> <li><a name="Shi05" href="../../indices/a-tree/s/Shi:Yaoyun.html">Yaoyun Shi</a>: <br><b>Tensor norms and the classical communication complexity of nonlocal quantum measurement. </b>460-467<br><a href="http://doi.acm.org/10.1145/1060590.1060659"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Shi05">BibTeX</a></font> <li><a name="Hallgren05" href="../../indices/a-tree/h/Hallgren:Sean.html">Sean Hallgren</a>: <br><b>Fast quantum algorithms for computing the unit group and class group of a number field. </b>468-474<br><a href="http://doi.acm.org/10.1145/1060590.1060660"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Hallgren05">BibTeX</a></font> <li><a name="SchmidtV05" href="../../indices/a-tree/s/Schmidt:Arthur.html">Arthur Schmidt</a>, <a href="../../indices/a-tree/v/Vollmer:Ulrich.html">Ulrich Vollmer</a>: <br><b>Polynomial time quantum algorithm for the computation of the unit group of a number field. </b>475-480<br><a href="http://doi.acm.org/10.1145/1060590.1060661"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/SchmidtV05">BibTeX</a></font> <li><a name="Ben-OrH05" href="../../indices/a-tree/b/Ben=Or:Michael.html">Michael Ben-Or</a>, <a href="../../indices/a-tree/h/Hassidim:Avinatan.html">Avinatan Hassidim</a>: <br><b>Fast quantum byzantine agreement. </b>481-485<br><a href="http://doi.acm.org/10.1145/1060590.1060662"><i>Electronic Edition</i></a> (<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-OrH05">BibTeX</a></font> </ul> <h2>Session 10B</h2> <ul> <li><a name="AlonMMN05" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/m/Makarychev:Konstantin.html">Konstantin Makarychev</a>, <a href="../../indices/a-tree/m/Makarychev:Yury.html">Yury Makarychev</a>, <a href="../../indices/a-tree/n/Naor:Assaf.html">Assaf Naor</a>: <br><b>Quadratic forms on graphs. </b>486-493<br><a href="http://doi.acm.org/10.1145/1060590.1060664"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AlonMMN05">BibTeX</a></font> <li><a name="ElkinEST05" href="../../indices/a-tree/e/Elkin:Michael.html">Michael Elkin</a>, <a href="../../indices/a-tree/e/Emek:Yuval.html">Yuval Emek</a>, <a href="../../indices/a-tree/s/Spielman:Daniel_A=.html">Daniel A. Spielman</a>, <a href="../../indices/a-tree/t/Teng:Shang=Hua.html">Shang-Hua Teng</a>: <br><b>Lower-stretch spanning trees. </b>494-503<br><a href="http://doi.acm.org/10.1145/1060590.1060665"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ElkinEST05">BibTeX</a></font> <li><a name="Goncalves05" href="../../indices/a-tree/g/Gon=ccedil=alves:Daniel.html">Daniel Gonçalves</a>: <br><b>Edge partition of planar sraphs into two outerplanar graphs. </b>504-512<br><a href="http://doi.acm.org/10.1145/1060590.1060666"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Goncalves05">BibTeX</a></font> </ul> <h2>Session 11A</h2> <ul> <li><a name="AhnHL05" href="../../indices/a-tree/a/Ahn:Luis_von.html">Luis von Ahn</a>, <a href="../../indices/a-tree/h/Hopper:Nicholas_J=.html">Nicholas J. Hopper</a>, <a href="../../indices/a-tree/l/Langford:John.html">John Langford</a>: <br><b>Covert two-party computation. </b>513-522<br><a href="http://doi.acm.org/10.1145/1060590.1060668"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AhnHL05">BibTeX</a></font> <li><a name="Wee05" href="../../indices/a-tree/w/Wee:Hoeteck.html">Hoeteck Wee</a>: <br><b>On obfuscating point functions. </b>523-532<br><a href="http://doi.acm.org/10.1145/1060590.1060669"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Wee05">BibTeX</a></font> <li><a name="PassR05" href="../../indices/a-tree/p/Pass:Rafael.html">Rafael Pass</a>, <a href="../../indices/a-tree/r/Rosen:Alon.html">Alon Rosen</a>: <br><b>New and improved constructions of non-malleable cryptographic protocols. </b>533-542<br><a href="http://doi.acm.org/10.1145/1060590.1060670"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/PassR05">BibTeX</a></font> <li><a name="LepinksiMS05" href="../../indices/a-tree/l/Lepinski:Matt.html">Matt Lepinski</a>, <a href="../../indices/a-tree/m/Micali:Silvio.html">Silvio Micali</a>, <a href="../../indices/a-tree/s/Shelat:Abhi.html">Abhi Shelat</a>: <br><b>Collusion-free protocols. </b>543-552<br><a href="http://doi.acm.org/10.1145/1060590.1060671"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LepinksiMS05">BibTeX</a></font> </ul> <h2>Session 11B</h2> <ul> <li><a name="AroraLN05" href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>, <a href="../../indices/a-tree/l/Lee:James_R=.html">James R. Lee</a>, <a href="../../indices/a-tree/n/Naor:Assaf.html">Assaf Naor</a>: <br><b>Euclidean distortion and the sparsest cut. </b>553-562<br><a href="http://doi.acm.org/10.1145/1060590.1060673"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AroraLN05">BibTeX</a></font> <li><a name="FeigeHL05" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>, <a href="../../indices/a-tree/h/Hajiaghayi:Mohammad_Taghi.html">Mohammad Taghi Hajiaghayi</a>, <a href="../../indices/a-tree/l/Lee:James_R=.html">James R. Lee</a>: <br><b>Improved approximation algorithms for minimum-weight vertex separators. </b>563-572<br><a href="http://doi.acm.org/10.1145/1060590.1060674"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FeigeHL05">BibTeX</a></font> <li><a name="AgarwalCMM05" href="../../indices/a-tree/a/Agarwal:Amit.html">Amit Agarwal</a>, <a href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/m/Makarychev:Konstantin.html">Konstantin Makarychev</a>, <a href="../../indices/a-tree/m/Makarychev:Yury.html">Yury Makarychev</a>: <br><b>O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. </b>573-581<br><a href="http://doi.acm.org/10.1145/1060590.1060675"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AgarwalCMM05">BibTeX</a></font> <li><a name="NaorS05" href="../../indices/a-tree/n/Naor:Joseph.html">Joseph Naor</a>, <a href="../../indices/a-tree/s/Schwartz:Roy.html">Roy Schwartz</a>: <br><b>Balanced metric labeling. </b>582-591<br><a href="http://doi.acm.org/10.1145/1060590.1060676"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/NaorS05">BibTeX</a></font> </ul> <h2>Session 12A</h2> <ul> <li><a name="DvirS05" href="../../indices/a-tree/d/Dvir:Zeev.html">Zeev Dvir</a>, <a href="../../indices/a-tree/s/Shpilka:Amir.html">Amir Shpilka</a>: <br><b>Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. </b>592-601<br><a href="http://doi.acm.org/10.1145/1060590.1060678"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DvirS05">BibTeX</a></font> <li><a name="GuruswamiR05" href="../../indices/a-tree/g/Guruswami:Venkatesan.html">Venkatesan Guruswami</a>, <a href="../../indices/a-tree/r/Rudra:Atri.html">Atri Rudra</a>: <br><b>Limits to list decoding Reed-Solomon codes. </b>602-609<br><a href="http://doi.acm.org/10.1145/1060590.1060679"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GuruswamiR05">BibTeX</a></font> </ul> <h2>Session 12B</h2> <ul> <li><a name="DobzinskiNS05" href="../../indices/a-tree/d/Dobzinski:Shahar.html">Shahar Dobzinski</a>, <a href="../../indices/a-tree/n/Nisan:Noam.html">Noam Nisan</a>, <a href="../../indices/a-tree/s/Schapira:Michael.html">Michael Schapira</a>: <br><b>Approximation algorithms for combinatorial auctions with complement-free bidders. </b>610-618<br><a href="http://doi.acm.org/10.1145/1060590.1060681"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DobzinskiNS05">BibTeX</a></font> <li><a name="AggarwalFGHIS05" href="../../indices/a-tree/a/Aggarwal:Gagan.html">Gagan Aggarwal</a>, <a 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/i/Immorlica:Nicole.html">Nicole Immorlica</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: <br><b>Derandomization of auctions. </b>619-625<br><a href="http://doi.acm.org/10.1145/1060590.1060682"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AggarwalFGHIS05">BibTeX</a></font> </ul> <h2>Best Student Paper</h2> <ul> <li><a name="Trifonov05" href="../../indices/a-tree/t/Trifonov:Vladimir.html">Vladimir Trifonov</a>: <br><b>An O(log n log log n) space algorithm for undirected st-connectivity. </b>626-633<br><a href="http://doi.acm.org/10.1145/1060590.1060684"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Trifonov05">BibTeX</a></font> </ul> <h2>Session 14A</h2> <ul> <li><a name="Aaronson05" href="../../indices/a-tree/a/Aaronson:Scott.html">Scott Aaronson</a>: <br><b>The complexity of agreement. </b>634-643<br><a href="http://doi.acm.org/10.1145/1060590.1060686"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Aaronson05">BibTeX</a></font> <li><a name="KalaiLP05" href="../../indices/a-tree/k/Kalai:Yael_Tauman.html">Yael Tauman Kalai</a>, <a href="../../indices/a-tree/l/Lindell:Yehuda.html">Yehuda Lindell</a>, <a href="../../indices/a-tree/p/Prabhakaran:Manoj.html">Manoj Prabhakaran</a>: <br><b>Concurrent general composition of secure protocols in the timing model. </b>644-653<br><a href="http://doi.acm.org/10.1145/1060590.1060687"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KalaiLP05">BibTeX</a></font> <li><a name="DodisS05" href="../../indices/a-tree/d/Dodis:Yevgeniy.html">Yevgeniy Dodis</a>, <a href="../../indices/a-tree/s/Smith:Adam.html">Adam Smith</a>: <br><b>Correcting errors without leaking partial information. </b>654-663<br><a href="http://doi.acm.org/10.1145/1060590.1060688"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DodisS05">BibTeX</a></font> <li><a name="Holenstein05" href="../../indices/a-tree/h/Holenstein:Thomas.html">Thomas Holenstein</a>: <br><b>Key agreement from weak bit agreement. </b>664-673<br><a href="http://doi.acm.org/10.1145/1060590.1060689"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Holenstein05">BibTeX</a></font> </ul> <h2>Session 14B</h2> <ul> <li><a name="CicaleseL05" href="../../indices/a-tree/c/Cicalese:Ferdinando.html">Ferdinando Cicalese</a>, <a href="../../indices/a-tree/l/Laber:Eduardo_Sany.html">Eduardo Sany Laber</a>: <br><b>A new strategy for querying priced information. </b>674-683<br><a href="http://doi.acm.org/10.1145/1060590.1060691"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CicaleseL05">BibTeX</a></font> <li><a name="AilonCN05" href="../../indices/a-tree/a/Ailon:Nir.html">Nir Ailon</a>, <a href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/n/Newman:Alantha.html">Alantha Newman</a>: <br><b>Aggregating inconsistent information: ranking and clustering. </b>684-693<br><a href="http://doi.acm.org/10.1145/1060590.1060692"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AilonCN05">BibTeX</a></font> <li><a name="AchlioptasCKM05" href="../../indices/a-tree/a/Achlioptas:Dimitris.html">Dimitris Achlioptas</a>, <a href="../../indices/a-tree/c/Clauset:Aaron.html">Aaron Clauset</a>, <a href="../../indices/a-tree/k/Kempe:David.html">David Kempe</a>, <a href="../../indices/a-tree/m/Moore:Cristopher.html">Cristopher Moore</a>: <br><b>On the bias of traceroute sampling: or, power-law degree distributions in regular graphs. </b>694-703<br><a href="http://doi.acm.org/10.1145/1060590.1060693"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AchlioptasCKM05">BibTeX</a></font> <li><a name="Scheideler05" href="../../indices/a-tree/s/Scheideler:Christian.html">Christian Scheideler</a>: <br><b>How to spread adversarial nodes?: rotate! </b>704-713<br><a href="http://doi.acm.org/10.1145/1060590.1060694"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Scheideler05">BibTeX</a></font> </ul> <h2>Session 15A</h2> <ul> <li><a name="GafniGP05" href="../../indices/a-tree/g/Gafni:Eli.html">Eli Gafni</a>, <a href="../../indices/a-tree/g/Guerraoui:Rachid.html">Rachid Guerraoui</a>, <a href="../../indices/a-tree/p/Pochon:Bastian.html">Bastian Pochon</a>: <br><b>From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement. </b>714-722<br><a href="http://doi.acm.org/10.1145/1060590.1060696"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GafniGP05">BibTeX</a></font> <li><a name="Jayanti05" href="../../indices/a-tree/j/Jayanti:Prasad.html">Prasad Jayanti</a>: <br><b>An optimal multi-writer snapshot algorithm. </b>723-732<br><a href="http://doi.acm.org/10.1145/1060590.1060697"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Jayanti05">BibTeX</a></font> <li><a name="ChlebusK05" href="../../indices/a-tree/c/Chlebus:Bogdan_S=.html">Bogdan S. Chlebus</a>, <a href="../../indices/a-tree/k/Kowalski:Dariusz_R=.html">Dariusz R. Kowalski</a>: <br><b>Cooperative asynchronous update of shared memory. </b>733-739<br><a href="http://doi.acm.org/10.1145/1060590.1060698"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChlebusK05">BibTeX</a></font> </ul> <h2>Session 15B</h2> <ul> <li><a name="Hastad05" href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>: <br><b>Every 2-CSP allows nontrivial approximation. </b>740-746<br><a href="http://doi.acm.org/10.1145/1060590.1060700"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Hastad05">BibTeX</a></font> <li><a name="VegaKKV05" href="../../indices/a-tree/v/Vega:Wenceslas_Fernandez_de_la.html">Wenceslas Fernandez de la Vega</a>, <a href="../../indices/a-tree/k/Karpinski:Marek.html">Marek Karpinski</a>, <a href="../../indices/a-tree/k/Kannan:Ravi.html">Ravi Kannan</a>, <a href="../../indices/a-tree/v/Vempala:Santosh.html">Santosh Vempala</a>: <br><b>Tensor decomposition and approximation schemes for constraint satisfaction problems. </b>747-754<br><a href="http://doi.acm.org/10.1145/1060590.1060701"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/VegaKKV05">BibTeX</a></font> <li><a name="JansenS05" href="../../indices/a-tree/j/Jansen:Klaus.html">Klaus Jansen</a>, <a href="../../indices/a-tree/s/Stee:Rob_van.html">Rob van Stee</a>: <br><b>On strip packing With rotations. </b>755-761<br><a href="http://doi.acm.org/10.1145/1060590.1060702"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/JansenS05">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
