stoc2006.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>STOC 2006</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>38. <a href="index.html">STOC</a> 2006: Seattle, WA, USA</h1> <a name="2006" href="../../indices/a-tree/k/Kleinberg:Jon_M=.html">Jon M. Kleinberg</a> (Ed.): Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006. ACM 2006, ISBN 1-59593-134-1 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/2006">BibTeX</a></font> <h2>Session 1A</h2> <ul> <li><a name="GuruswamiR06" 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>Explicit capacity-achieving list-decodable codes. </b>1-10<br><a href="http://doi.acm.org/10.1145/1132516.1132518"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GuruswamiR06">BibTeX</a></font> <li><a name="SamorodnitskyT06" href="../../indices/a-tree/s/Samorodnitsky:Alex.html">Alex Samorodnitsky</a>, <a href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>: <br><b>Gowers uniformity, influence of variables, and PCPs. </b>11-20<br><a href="http://doi.acm.org/10.1145/1132516.1132519"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/SamorodnitskyT06">BibTeX</a></font> <li><a name="MoshkovitzR06" href="../../indices/a-tree/m/Moshkovitz:Dana.html">Dana Moshkovitz</a>, <a href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>: <br><b>Sub-constant error low degree test of almost-linear size. </b>21-30<br><a href="http://doi.acm.org/10.1145/1132516.1132520"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MoshkovitzR06">BibTeX</a></font> </ul> <h2>Session 1B</h2> <ul> <li><a name="BansalS06" href="../../indices/a-tree/b/Bansal:Nikhil.html">Nikhil Bansal</a>, <a href="../../indices/a-tree/s/Sviridenko:Maxim.html">Maxim Sviridenko</a>: <br><b>The Santa Claus problem. </b>31-40<br><a href="http://doi.acm.org/10.1145/1132516.1132522"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BansalS06">BibTeX</a></font> <li><a name="Feige06" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>: <br><b>On maximizing welfare when utility functions are subadditive. </b>41-50<br><a href="http://doi.acm.org/10.1145/1132516.1132523"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Feige06">BibTeX</a></font> <li><a name="KelnerS06" href="../../indices/a-tree/k/Kelner:Jonathan_A=.html">Jonathan A. Kelner</a>, <a href="../../indices/a-tree/s/Spielman:Daniel_A=.html">Daniel A. Spielman</a>: <br><b>A randomized polynomial-time simplex algorithm for linear programming. </b>51-60<br><a href="http://doi.acm.org/10.1145/1132516.1132524"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KelnerS06">BibTeX</a></font> </ul> <h2>Session 2A</h2> <ul> <li><a name="GoldbergP06" href="../../indices/a-tree/g/Goldberg:Paul_W=.html">Paul W. Goldberg</a>, <a href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: <br><b>Reducibility among equilibrium problems. </b>61-70<br><a href="http://doi.acm.org/10.1145/1132516.1132526"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldbergP06">BibTeX</a></font> <li><a name="DaskalakisGP06" href="../../indices/a-tree/d/Daskalakis:Constantinos.html">Constantinos Daskalakis</a>, <a href="../../indices/a-tree/g/Goldberg:Paul_W=.html">Paul W. Goldberg</a>, <a href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: <br><b>The complexity of computing a Nash equilibrium. </b>71-78<br><a href="http://doi.acm.org/10.1145/1132516.1132527"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DaskalakisGP06">BibTeX</a></font> <li><a name="RoughgardenS06" href="../../indices/a-tree/r/Roughgarden:Tim.html">Tim Roughgarden</a>, <a href="../../indices/a-tree/s/Sundararajan:Mukund.html">Mukund Sundararajan</a>: <br><b>New trade-offs in cost-sharing mechanisms. </b>79-88<br><a href="http://doi.acm.org/10.1145/1132516.1132528"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/RoughgardenS06">BibTeX</a></font> <li><a name="HayrapetyanTW06" href="../../indices/a-tree/h/Hayrapetyan:Ara.html">Ara Hayrapetyan</a>, <a href="../../indices/a-tree/t/Tardos:=Eacute=va.html">Éva Tardos</a>, <a href="../../indices/a-tree/w/Wexler:Tom.html">Tom Wexler</a>: <br><b>The effect of collusion in congestion games. </b>89-98<br><a href="http://doi.acm.org/10.1145/1132516.1132529"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HayrapetyanTW06">BibTeX</a></font> </ul> <h2>Session 2B</h2> <ul> <li><a name="IshaiKLP06" href="../../indices/a-tree/i/Ishai:Yuval.html">Yuval Ishai</a>, <a href="../../indices/a-tree/k/Kushilevitz:Eyal.html">Eyal Kushilevitz</a>, <a href="../../indices/a-tree/l/Lindell:Yehuda.html">Yehuda Lindell</a>, <a href="../../indices/a-tree/p/Petrank:Erez.html">Erez Petrank</a>: <br><b>Black-box constructions for secure computation. </b>99-108<br><a href="http://doi.acm.org/10.1145/1132516.1132531"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/IshaiKLP06">BibTeX</a></font> <li><a name="KushilevitzLR06" href="../../indices/a-tree/k/Kushilevitz:Eyal.html">Eyal Kushilevitz</a>, <a href="../../indices/a-tree/l/Lindell:Yehuda.html">Yehuda Lindell</a>, <a href="../../indices/a-tree/r/Rabin:Tal.html">Tal Rabin</a>: <br><b>Information-theoretically secure protocols and security under composition. </b>109-118<br><a href="http://doi.acm.org/10.1145/1132516.1132532"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KushilevitzLR06">BibTeX</a></font> <li><a name="BeimelCNW06" href="../../indices/a-tree/b/Beimel:Amos.html">Amos Beimel</a>, <a href="../../indices/a-tree/c/Carmi:Paz.html">Paz Carmi</a>, <a href="../../indices/a-tree/n/Nissim:Kobbi.html">Kobbi Nissim</a>, <a href="../../indices/a-tree/w/Weinreb:Enav.html">Enav Weinreb</a>: <br><b>Private approximation of search problems. </b>119-128<br><a href="http://doi.acm.org/10.1145/1132516.1132533"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BeimelCNW06">BibTeX</a></font> </ul> <h2>Session 3</h2> <ul> <li><a name="Raghavan06" href="../../indices/a-tree/r/Raghavan:Prabhakar.html">Prabhakar Raghavan</a>: <br><b>The changing face of web search: algorithms, auctions and advertising. </b>129<br><a href="http://doi.acm.org/10.1145/1132516.1132535"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Raghavan06">BibTeX</a></font> </ul> <h2>Session 4A</h2> <ul> <li><a name="AchlioptasR06" href="../../indices/a-tree/a/Achlioptas:Dimitris.html">Dimitris Achlioptas</a>, <a href="../../indices/a-tree/r/Ricci=Tersenghi:Federico.html">Federico Ricci-Tersenghi</a>: <br><b>On the solution-space geometry of random constraint satisfaction problems. </b>130-139<br><a href="http://doi.acm.org/10.1145/1132516.1132537"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AchlioptasR06">BibTeX</a></font> <li><a name="Weitz06" href="../../indices/a-tree/w/Weitz:Dror.html">Dror Weitz</a>: <br><b>Counting independent sets up to the tree threshold. </b>140-149<br><a href="http://doi.acm.org/10.1145/1132516.1132538"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Weitz06">BibTeX</a></font> <li><a name="Szegedy06" href="../../indices/a-tree/s/Szegedy:Mario.html">Mario Szegedy</a>: <br><b>The DLT priority sampling is essentially optimal. </b>150-158<br><a href="http://doi.acm.org/10.1145/1132516.1132539"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Szegedy06">BibTeX</a></font> <li><a name="DaskalakisMR06" href="../../indices/a-tree/d/Daskalakis:Constantinos.html">Constantinos Daskalakis</a>, <a 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>Optimal phylogenetic reconstruction. </b>159-168<br><a href="http://doi.acm.org/10.1145/1132516.1132540"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DaskalakisMR06">BibTeX</a></font> </ul> <h2>Session 4B</h2> <ul> <li><a name="FatourouFR06" href="../../indices/a-tree/f/Fatourou:Panagiota.html">Panagiota Fatourou</a>, <a href="../../indices/a-tree/f/Fich:Faith_Ellen.html">Faith Ellen Fich</a>, <a href="../../indices/a-tree/r/Ruppert:Eric.html">Eric Ruppert</a>: <br><b>Time-space tradeoffs for implementations of snapshots. </b>169-178<br><a href="http://doi.acm.org/10.1145/1132516.1132542"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FatourouFR06">BibTeX</a></font> <li><a name="Ben-OrPV06" href="../../indices/a-tree/b/Ben=Or:Michael.html">Michael Ben-Or</a>, <a href="../../indices/a-tree/p/Pavlov:Elan.html">Elan Pavlov</a>, <a href="../../indices/a-tree/v/Vaikuntanathan:Vinod.html">Vinod Vaikuntanathan</a>: <br><b>Byzantine agreement in the full-information model in O(log n) rounds. </b>179-186<br><a href="http://doi.acm.org/10.1145/1132516.1132543"><i>Electronic Edition</i></a> (<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-OrPV06">BibTeX</a></font> <li><a name="Antonakopoulos06" href="../../indices/a-tree/a/Antonakopoulos:Spyridon.html">Spyridon Antonakopoulos</a>: <br><b>Fast leader-election protocols with bounded cheaters' edge. </b>187-196<br><a href="http://doi.acm.org/10.1145/1132516.1132544"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Antonakopoulos06">BibTeX</a></font> <li><a name="ChoG06" href="../../indices/a-tree/c/Cho:Sung=woo.html">Sung-woo Cho</a>, <a href="../../indices/a-tree/g/Goel:Ashish.html">Ashish Goel</a>: <br><b>Pricing for fairness: distributed resource allocation for multiple objectives. </b>197-204<br><a href="http://doi.acm.org/10.1145/1132516.1132545"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChoG06">BibTeX</a></font> </ul> <h2>Session 5A</h2> <ul> <li><a name="CharikarMM06" 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>Near-optimal algorithms for unique games. </b>205-214<br><a href="http://doi.acm.org/10.1145/1132516.1132547"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CharikarMM06">BibTeX</a></font> <li><a name="AroraC06" href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>, <a href="../../indices/a-tree/c/Chlamtac:Eden.html">Eden Chlamtac</a>: <br><b>New approximation guarantee for chromatic number. </b>215-224<br><a href="http://doi.acm.org/10.1145/1132516.1132548"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AroraC06">BibTeX</a></font> </ul> <h2>Session 5B</h2> <ul> <li><a name="VassilevskaW06" href="../../indices/a-tree/v/Vassilevska:Virginia.html">Virginia Vassilevska</a>, <a href="../../indices/a-tree/w/Williams:Ryan.html">Ryan Williams</a>: <br><b>Finding a maximum weight triangle in n<sup>3-Delta</sup> time, with applications. </b>225-231<br><a href="http://doi.acm.org/10.1145/1132516.1132550"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/VassilevskaW06">BibTeX</a></font> <li><a name="PatrascuT06" href="../../indices/a-tree/p/Patrascu:Mihai.html">Mihai Patrascu</a>, <a href="../../indices/a-tree/t/Thorup:Mikkel.html">Mikkel Thorup</a>: <br><b>Time-space trade-offs for predecessor search. </b>232-240<br><a href="http://doi.acm.org/10.1145/1132516.1132551"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/PatrascuT06">BibTeX</a></font> </ul> <h2>Session 6</h2> <ul> <li><a name="Dinur06" href="../../indices/a-tree/d/Dinur:Irit.html">Irit Dinur</a>: <br><b>The PCP theorem by gap amplification. </b>241-250<br><a href="http://doi.acm.org/10.1145/1132516.1132553"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Dinur06">BibTeX</a></font> </ul> <h2>Session 7A</h2> <ul> <li><a name="Shapira06" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/f/Fischer:Eldar.html">Eldar Fischer</a>, <a href="../../indices/a-tree/n/Newman:Ilan.html">Ilan Newman</a>, <a href="../../indices/a-tree/s/Shapira:Asaf.html">Asaf Shapira</a>: <br><b>A combinatorial characterization of the testable graph properties: it's all about regularity. </b>251-260<br><a href="http://doi.acm.org/10.1145/1132516.1132555"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Shapira06">BibTeX</a></font> <li><a name="BorgsCLSSV06" href="../../indices/a-tree/b/Borgs:Christian.html">Christian Borgs</a>, <a href="../../indices/a-tree/c/Chayes:Jennifer_T=.html">Jennifer T. Chayes</a>, <a href="../../indices/a-tree/l/Lov=aacute=sz:L=aacute=szl=oacute=.html">László Lovász</a>, <a href="../../indices/a-tree/s/S=oacute=s:Vera_T=.html">Vera T. Sós</a>, <a href="../../indices/a-tree/s/Szegedy:Bal=aacute=zs.html">Balázs Szegedy</a>, <a href="../../indices/a-tree/v/Vesztergombi:Katalin.html">Katalin Vesztergombi</a>: <br><b>Graph limits and parameter testing. </b>261-270<br><a href="http://doi.acm.org/10.1145/1132516.1132556"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BorgsCLSSV06">BibTeX</a></font> <li><a name="AbrahamBN06" href="../../indices/a-tree/a/Abraham:Ittai.html">Ittai Abraham</a>, <a href="../../indices/a-tree/b/Bartal:Yair.html">Yair Bartal</a>, <a href="../../indices/a-tree/n/Neiman:Ofer.html">Ofer Neiman</a>: <br><b>Advances in metric embedding theory. </b>271-286<br><a href="http://doi.acm.org/10.1145/1132516.1132557"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AbrahamBN06">BibTeX</a></font> </ul> <h2>Session 7B</h2> <ul> <li><a name="NguyenV06" href="../../indices/a-tree/n/Nguyen:Minh=Huyen.html">Minh-Huyen Nguyen</a>, <a href="../../indices/a-tree/v/Vadhan:Salil_P=.html">Salil P. Vadhan</a>: <br><b>Zero knowledge with efficient provers. </b>287-295<br><a href="http://doi.acm.org/10.1145/1132516.1132559"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/NguyenV06">BibTeX</a></font> <li><a name="Watrous06" href="../../indices/a-tree/w/Watrous:John.html">John Watrous</a>: <br><b>Zero-knowledge against quantum attacks. </b>296-305<br><a href="http://doi.acm.org/10.1145/1132516.1132560"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Watrous06">BibTeX</a></font> <li><a name="MicaliP06" href="../../indices/a-tree/m/Micali:Silvio.html">Silvio Micali</a>, <a href="../../indices/a-tree/p/Pass:Rafael.html">Rafael Pass</a>: <br><b>Local zero knowledge. </b>306-315<br><a href="http://doi.acm.org/10.1145/1132516.1132561"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MicaliP06">BibTeX</a></font> </ul> <h2>Session 8A</h2> <ul> <li><a name="RemyS06" href="../../indices/a-tree/r/Remy:Jan.html">Jan Remy</a>, <a href="../../indices/a-tree/s/Steger:Angelika.html">Angelika Steger</a>: <br><b>A quasi-polynomial time approximation scheme for minimum weight triangulation. </b>316-325<br><a href="http://doi.acm.org/10.1145/1132516.1132563"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/RemyS06">BibTeX</a></font> <li><a name="Clarkson06" href="../../indices/a-tree/c/Clarkson:Kenneth_L=.html">Kenneth L. Clarkson</a>: <br><b>Building triangulations using epsilon-nets. </b>326-335<br><a href="http://doi.acm.org/10.1145/1132516.1132564"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Clarkson06">BibTeX</a></font> <li><a name="AsanoMT06" href="../../indices/a-tree/a/Asano:Tetsuo.html">Tetsuo Asano</a>, <a href="../../indices/a-tree/m/Matousek:Jir=iacute=.html">Jirí Matousek</a>, <a href="../../indices/a-tree/t/Tokuyama:Takeshi.html">Takeshi Tokuyama</a>: <br><b>The distance trisector curve. </b>336-343<br><a href="http://doi.acm.org/10.1145/1132516.1132565"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AsanoMT06">BibTeX</a></font> </ul> <h2>Session 8B</h2> <ul> <li><a name="DinurMR06" href="../../indices/a-tree/d/Dinur:Irit.html">Irit Dinur</a>, <a href="../../indices/a-tree/m/Mossel:Elchanan.html">Elchanan Mossel</a>, <a href="../../indices/a-tree/r/Regev:Oded.html">Oded Regev</a>: <br><b>Conditional hardness for approximate coloring. </b>344-353<br><a href="http://doi.acm.org/10.1145/1132516.1132567"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DinurMR06">BibTeX</a></font> <li><a name="FellowsRRS06" href="../../indices/a-tree/f/Fellows:Michael_R=.html">Michael R. Fellows</a>, <a href="../../indices/a-tree/r/Rosamond:Frances_A=.html">Frances A. Rosamond</a>, <a href="../../indices/a-tree/r/Rotics:Udi.html">Udi Rotics</a>, <a href="../../indices/a-tree/s/Szeider:Stefan.html">Stefan Szeider</a>: <br><b>Clique-width minimization is NP-hard. </b>354-362<br><a href="http://doi.acm.org/10.1145/1132516.1132568"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FellowsRRS06">BibTeX</a></font> <li><a name="Feldman06" href="../../indices/a-tree/f/Feldman:Vitaly.html">Vitaly Feldman</a>: <br><b>Hardness of approximate two-level logic minimization and PAC learning with membership queries. </b>363-372<br><a href="http://doi.acm.org/10.1145/1132516.1132569"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Feldman06">BibTeX</a></font> </ul> <h2>Session 9</h2> <ul> <li><a name="Impagliazzo06" href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>: <br><b>Can every randomized algorithm be derandomized? </b>373-374<br><a href="http://doi.acm.org/10.1145/1132516.1132571"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Impagliazzo06">BibTeX</a></font> </ul> <h2>Session 10A</h2> <ul> <li><a name="FeigeM06" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>, <a href="../../indices/a-tree/m/Mahdian:Mohammad.html">Mohammad Mahdian</a>: <br><b>Finding small balanced separators. </b>375-384<br><a href="http://doi.acm.org/10.1145/1132516.1132573"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FeigeM06">BibTeX</a></font> <li><a name="KhandekarRV06" href="../../indices/a-tree/k/Khandekar:Rohit.html">Rohit Khandekar</a>, <a href="../../indices/a-tree/r/Rao:Satish.html">Satish Rao</a>, <a href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>: <br><b>Graph partitioning using single commodity flows. </b>385-390<br><a href="http://doi.acm.org/10.1145/1132516.1132574"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KhandekarRV06">BibTeX</a></font> <li><a name="NesetrilM06" href="../../indices/a-tree/n/Nesetril:Jaroslav.html">Jaroslav Nesetril</a>, <a href="../../indices/a-tree/m/Mendez:Patrice_Ossona_de.html">Patrice Ossona de Mendez</a>: <br><b>Linear time low tree-width partitions and algorithmic consequences. </b>391-400<br><a href="http://doi.acm.org/10.1145/1132516.1132575"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/NesetrilM06">BibTeX</a></font> <li><a name="KawarabayashiM06" href="../../indices/a-tree/k/Kawarabayashi:Ken=ichi.html">Ken-ichi Kawarabayashi</a>, <a href="../../indices/a-tree/m/Mohar:Bojan.html">Bojan Mohar</a>: <br><b>Approximating the list-chromatic number and the chromatic number in minor-closed and odd-minor-closed classes of graphs. </b>401-416<br><a href="http://doi.acm.org/10.1145/1132516.1132576"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KawarabayashiM06">BibTeX</a></font> </ul> <h2>Session 10B</h2> <ul> <li><a name="Gurvits06" href="../../indices/a-tree/g/Gurvits:Leonid.html">Leonid Gurvits</a>: <br><b>Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures: sharper bounds, simpler proofs and algorithmic applications. </b>417-426<br><a href="http://doi.acm.org/10.1145/1132516.1132578"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Gurvits06">BibTeX</a></font> <li><a name="AharonovJL06" href="../../indices/a-tree/a/Aharonov:Dorit.html">Dorit Aharonov</a>, <a href="../../indices/a-tree/j/Jones:Vaughan.html">Vaughan Jones</a>, <a href="../../indices/a-tree/l/Landau:Zeph.html">Zeph Landau</a>: <br><b>A polynomial quantum algorithm for approximating the Jones polynomial. </b>427-436<br><a href="http://doi.acm.org/10.1145/1132516.1132579"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AharonovJL06">BibTeX</a></font> <li><a name="DinurFKO06" href="../../indices/a-tree/d/Dinur:Irit.html">Irit Dinur</a>, <a href="../../indices/a-tree/f/Friedgut:Ehud.html">Ehud Friedgut</a>, <a href="../../indices/a-tree/k/Kindler:Guy.html">Guy Kindler</a>, <a href="../../indices/a-tree/o/O=Donnell:Ryan.html">Ryan O'Donnell</a>: <br><b>On the fourier tails of bounded functions over the discrete cube. </b>437-446<br><a href="http://doi.acm.org/10.1145/1132516.1132580"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DinurFKO06">BibTeX</a></font> <li><a name="RegevR06" href="../../indices/a-tree/r/Regev:Oded.html">Oded Regev</a>, <a href="../../indices/a-tree/r/Rosen:Ricky.html">Ricky Rosen</a>: <br><b>Lattice problems and norm embeddings. </b>447-456<br><a href="http://doi.acm.org/10.1145/1132516.1132581"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/RegevR06">BibTeX</a></font> </ul> <h2>Session 11A</h2> <ul> <li><a name="ReingoldTV06" href="../../indices/a-tree/r/Reingold:Omer.html">Omer Reingold</a>, <a href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>, <a href="../../indices/a-tree/v/Vadhan:Salil_P=.html">Salil P. Vadhan</a>: <br><b>Pseudorandom walks on regular digraphs and the RL vs. L problem. </b>457-466<br><a href="http://doi.acm.org/10.1145/1132516.1132583"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ReingoldTV06">BibTeX</a></font> <li><a name="Plandowski06" href="../../indices/a-tree/p/Plandowski:Wojciech.html">Wojciech Plandowski</a>: <br><b>An efficient algorithm for solving word equations. </b>467-476<br><a href="http://doi.acm.org/10.1145/1132516.1132584"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Plandowski06">BibTeX</a></font> </ul> <h2>Session 11B</h2> <ul> <li><a name="DeMarzoKM06" href="../../indices/a-tree/d/DeMarzo:Peter.html">Peter DeMarzo</a>, <a href="../../indices/a-tree/k/Kremer:Ilan.html">Ilan Kremer</a>, <a href="../../indices/a-tree/m/Mansour:Yishay.html">Yishay Mansour</a>: <br><b>Online trading algorithms and robust option pricing. </b>477-486<br><a href="http://doi.acm.org/10.1145/1132516.1132586"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DeMarzoKM06">BibTeX</a></font> <li><a name="PanagiotouS06" href="../../indices/a-tree/p/Panagiotou:Konstantinos.html">Konstantinos Panagiotou</a>, <a href="../../indices/a-tree/s/Souza:Alexander.html">Alexander Souza</a>: <br><b>On adequate performance measures for paging. </b>487-496<br><a href="http://doi.acm.org/10.1145/1132516.1132587"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/PanagiotouS06">BibTeX</a></font> </ul> <h2>Session 12</h2> <ul> <li><a name="Rao06" href="../../indices/a-tree/r/Rao:Anup.html">Anup Rao</a>: <br><b>Extractors for a constant number of polynomially small min-entropy independent sources. </b>497-506<br><a href="http://doi.acm.org/10.1145/1132516.1132589"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Rao06">BibTeX</a></font> <li><a name="Nordstrom06" href="../../indices/a-tree/n/Nordstr=ouml=m:Jakob.html">Jakob Nordström</a>: <br><b>Narrow proofs may be spacious: separating space and width in resolution. </b>507-516<br><a href="http://doi.acm.org/10.1145/1132516.1132590"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Nordstrom06">BibTeX</a></font> </ul> <h2>Session 13A</h2> <ul> <li><a name="AndrewsZ06" 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>Logarithmic hardness of the directed congestion minimization problem. </b>517-526<br><a href="http://doi.acm.org/10.1145/1132516.1132592"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AndrewsZ06">BibTeX</a></font> <li><a name="ChuzhoyK06" href="../../indices/a-tree/c/Chuzhoy:Julia.html">Julia Chuzhoy</a>, <a href="../../indices/a-tree/k/Khanna:Sanjeev.html">Sanjeev Khanna</a>: <br><b>Hardness of cut problems in directed graphs. </b>527-536<br><a href="http://doi.acm.org/10.1145/1132516.1132593"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChuzhoyK06">BibTeX</a></font> <li><a name="DevanurKSV06" href="../../indices/a-tree/d/Devanur:Nikhil_R=.html">Nikhil R. Devanur</a>, <a href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>, <a href="../../indices/a-tree/s/Saket:Rishi.html">Rishi Saket</a>, <a href="../../indices/a-tree/v/Vishnoi:Nisheeth_K=.html">Nisheeth K. Vishnoi</a>: <br><b>Integrality gaps for sparsest cut and minimum linear arrangement problems. </b>537-546<br><a href="http://doi.acm.org/10.1145/1132516.1132594"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DevanurKSV06">BibTeX</a></font> <li><a name="KarloffKMR06" href="../../indices/a-tree/k/Karloff:Howard_J=.html">Howard J. Karloff</a>, <a href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>, <a href="../../indices/a-tree/m/Mehta:Aranyak.html">Aranyak Mehta</a>, <a href="../../indices/a-tree/r/Rabani:Yuval.html">Yuval Rabani</a>: <br><b>On earthmover distance, metric labeling, and 0-extension. </b>547-556<br><a href="http://doi.acm.org/10.1145/1132516.1132595"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KarloffKMR06">BibTeX</a></font> </ul> <h2>Session 13B</h2> <ul> <li><a name="AilonC06" href="../../indices/a-tree/a/Ailon:Nir.html">Nir Ailon</a>, <a href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>: <br><b>Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. </b>557-563<br><a href="http://doi.acm.org/10.1145/1132516.1132597"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AilonC06">BibTeX</a></font> <li><a name="AryaMM06" 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>On the importance of idempotence. </b>564-573<br><a href="http://doi.acm.org/10.1145/1132516.1132598"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AryaMM06">BibTeX</a></font> <li><a name="ColeG06" href="../../indices/a-tree/c/Cole:Richard.html">Richard Cole</a>, <a href="../../indices/a-tree/g/Gottlieb:Lee=Ad.html">Lee-Ad Gottlieb</a>: <br><b>Searching dynamic point sets in spaces with bounded doubling dimension. </b>574-583<br><a href="http://doi.acm.org/10.1145/1132516.1132599"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ColeG06">BibTeX</a></font> <li><a name="AngluinACW06" href="../../indices/a-tree/a/Angluin:Dana.html">Dana Angluin</a>, <a href="../../indices/a-tree/a/Aspnes:James.html">James Aspnes</a>, <a href="../../indices/a-tree/c/Chen:Jiang.html">Jiang Chen</a>, <a href="../../indices/a-tree/w/Wu:Yinghua.html">Yinghua Wu</a>: <br><b>Learning a circuit by injecting values. </b>584-593<br><a href="http://doi.acm.org/10.1145/1132516.1132600"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AngluinACW06">BibTeX</a></font> </ul> <h2>Session 14A</h2> <ul> <li><a name="GavinskyKRW06" href="../../indices/a-tree/g/Gavinsky:Dmitry.html">Dmitry Gavinsky</a>, <a href="../../indices/a-tree/k/Kempe:Julia.html">Julia Kempe</a>, <a href="../../indices/a-tree/r/Regev:Oded.html">Oded Regev</a>, <a href="../../indices/a-tree/w/Wolf:Ronald_de.html">Ronald de Wolf</a>: <br><b>Bounded-error quantum state identification and exponential separations in communication complexity. </b>594-603<br><a href="http://doi.acm.org/10.1145/1132516.1132602"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GavinskyKRW06">BibTeX</a></font> <li><a name="HallgrenMRRS06" href="../../indices/a-tree/h/Hallgren:Sean.html">Sean Hallgren</a>, <a href="../../indices/a-tree/m/Moore:Cristopher.html">Cristopher Moore</a>, <a href="../../indices/a-tree/r/R=ouml=tteler:Martin.html">Martin Rötteler</a>, <a href="../../indices/a-tree/r/Russell:Alexander.html">Alexander Russell</a>, <a href="../../indices/a-tree/s/Sen:Pranab.html">Pranab Sen</a>: <br><b>Limitations of quantum coset states for graph isomorphism. </b>604-617<br><a href="http://doi.acm.org/10.1145/1132516.1132603"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HallgrenMRRS06">BibTeX</a></font> <li><a name="AmbainisSW06" href="../../indices/a-tree/a/Ambainis:Andris.html">Andris Ambainis</a>, <a href="../../indices/a-tree/s/Spalek:Robert.html">Robert Spalek</a>, <a href="../../indices/a-tree/w/Wolf:Ronald_de.html">Ronald de Wolf</a>: <br><b>A new quantum lower bound method, : with applications to direct product theorems and time-space tradeoffs. </b>618-633<br><a href="http://doi.acm.org/10.1145/1132516.1132604"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AmbainisSW06">BibTeX</a></font> <li><a name="Zhang06" href="../../indices/a-tree/z/Zhang:Shengyu.html">Shengyu Zhang</a>: <br><b>New upper and lower bounds for randomized and quantum local search. </b>634-643<br><a href="http://doi.acm.org/10.1145/1132516.1132605"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Zhang06">BibTeX</a></font> </ul> <h2>Session 14B</h2> <ul> <li><a name="DobzinskiNS06" 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>Truthful randomized mechanisms for combinatorial auctions. </b>644-652<br><a href="http://doi.acm.org/10.1145/1132516.1132607"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DobzinskiNS06">BibTeX</a></font> <li><a name="FischerRV06" href="../../indices/a-tree/f/Fischer:Simon.html">Simon Fischer</a>, <a href="../../indices/a-tree/r/R=auml=cke:Harald.html">Harald Räcke</a>, <a href="../../indices/a-tree/v/V=ouml=cking:Berthold.html">Berthold Vöcking</a>: <br><b>Fast convergence to Wardrop equilibria by adaptive sampling methods. </b>653-662<br><a href="http://doi.acm.org/10.1145/1132516.1132608"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FischerRV06">BibTeX</a></font> <li><a name="FleischerKLS06" href="../../indices/a-tree/f/Fleischer:Lisa.html">Lisa Fleischer</a>, <a href="../../indices/a-tree/k/K=ouml=nemann:Jochen.html">Jochen Könemann</a>, <a href="../../indices/a-tree/l/Leonardi:Stefano.html">Stefano Leonardi</a>, <a href="../../indices/a-tree/s/Sch=auml=fer:Guido.html">Guido Schäfer</a>: <br><b>Simple cost sharing schemes for multicommodity rent-or-buy and stochastic Steiner tree. </b>663-670<br><a href="http://doi.acm.org/10.1145/1132516.1132609"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FleischerKLS06">BibTeX</a></font> </ul> <h2>Session 15A</h2> <ul> <li><a name="BarakRSW06" href="../../indices/a-tree/b/Barak:Boaz.html">Boaz Barak</a>, <a href="../../indices/a-tree/r/Rao:Anup.html">Anup Rao</a>, <a href="../../indices/a-tree/s/Shaltiel:Ronen.html">Ronen Shaltiel</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction. </b>671-680<br><a href="http://doi.acm.org/10.1145/1132516.1132611"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BarakRSW06">BibTeX</a></font> <li><a name="Zuckerman06" href="../../indices/a-tree/z/Zuckerman:David.html">David Zuckerman</a>: <br><b>Linear degree extractors and the inapproximability of max clique and chromatic number. </b>681-690<br><a href="http://doi.acm.org/10.1145/1132516.1132612"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Zuckerman06">BibTeX</a></font> <li><a name="KampRVZ06" href="../../indices/a-tree/k/Kamp:Jesse.html">Jesse Kamp</a>, <a href="../../indices/a-tree/r/Rao:Anup.html">Anup Rao</a>, <a href="../../indices/a-tree/v/Vadhan:Salil_P=.html">Salil P. Vadhan</a>, <a href="../../indices/a-tree/z/Zuckerman:David.html">David Zuckerman</a>: <br><b>Deterministic extractors for small-space sources. </b>691-700<br><a href="http://doi.acm.org/10.1145/1132516.1132613"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KampRVZ06">BibTeX</a></font> <li><a name="AkaviaGGM06" href="../../indices/a-tree/a/Akavia:Adi.html">Adi Akavia</a>, <a href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/m/Moshkovitz:Dana.html">Dana Moshkovitz</a>: <br><b>On basing one-way functions on NP-hardness. </b>701-710<br><a href="http://doi.acm.org/10.1145/1132516.1132614"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AkaviaGGM06">BibTeX</a></font> <li><a name="DubrovI06" href="../../indices/a-tree/d/Dubrov:Bella.html">Bella Dubrov</a>, <a href="../../indices/a-tree/i/Ishai:Yuval.html">Yuval Ishai</a>: <br><b>On the randomness complexity of efficient sampling. </b>711-720<br><a href="http://doi.acm.org/10.1145/1132516.1132615"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DubrovI06">BibTeX</a></font> </ul> <h2>Session 15B</h2> <ul> <li><a name="BansalCES06" href="../../indices/a-tree/b/Bansal:Nikhil.html">Nikhil Bansal</a>, <a href="../../indices/a-tree/c/Chakrabarti:Amit.html">Amit Chakrabarti</a>, <a href="../../indices/a-tree/e/Epstein:Amir.html">Amir Epstein</a>, <a href="../../indices/a-tree/s/Schieber:Baruch.html">Baruch Schieber</a>: <br><b>A quasi-PTAS for unsplittable flow on line graphs. </b>721-729<br><a href="http://doi.acm.org/10.1145/1132516.1132617"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BansalCES06">BibTeX</a></font> <li><a name="GargK06" href="../../indices/a-tree/g/Garg:Naveen.html">Naveen Garg</a>, <a href="../../indices/a-tree/k/Kumar:Amit.html">Amit Kumar</a>: <br><b>Minimizing average flow time on related machines. </b>730-738<br><a href="http://doi.acm.org/10.1145/1132516.1132618"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GargK06">BibTeX</a></font> <li><a name="LeviRS06" href="../../indices/a-tree/l/Levi:Retsef.html">Retsef Levi</a>, <a href="../../indices/a-tree/r/Roundy:Robin.html">Robin Roundy</a>, <a href="../../indices/a-tree/s/Shmoys:David_B=.html">David B. Shmoys</a>: <br><b>Provably near-optimal sampling-based algorithms for Stochastic inventory control models. </b>739-748<br><a href="http://doi.acm.org/10.1145/1132516.1132619"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LeviRS06">BibTeX</a></font> <li><a name="Klein06" href="../../indices/a-tree/k/Klein:Philip_N=.html">Philip N. Klein</a>: <br><b>A subset spanner for Planar graphs, : with application to subset TSP. </b>749-756<br><a href="http://doi.acm.org/10.1145/1132516.1132620"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Klein06">BibTeX</a></font> <li><a name="ChekuriKS06" 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>Edge-disjoint paths in Planar graphs with constant congestion. </b>757-766<br><a href="http://doi.acm.org/10.1145/1132516.1132621"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChekuriKS06">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
