stoc2008.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>STOC 2008</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>40. <a href="index.html">STOC</a> 2008: Victoria, British Columbia, Canada</h1> <a name="2008" href="../../indices/a-tree/l/Ladner:Richard_E=.html">Richard E. Ladner</a>, <a href="../../indices/a-tree/d/Dwork:Cynthia.html">Cynthia Dwork</a> (Eds.): Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008. ACM 2008, ISBN 978-1-60558-047-0 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/2008">BibTeX</a></font> <h2>1A</h2> <ul> <li><a name="Rao08" href="../../indices/a-tree/r/Rao:Anup.html">Anup Rao</a>: <br><b>Parallel repetition in projection games and a concentration bound. </b>1-10<br><a href="http://doi.acm.org/10.1145/1374376.1374378"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Rao08">BibTeX</a></font> <li><a name="ManokaranNRS08" href="../../indices/a-tree/m/Manokaran:Rajsekar.html">Rajsekar Manokaran</a>, <a href="../../indices/a-tree/n/Naor:Joseph.html">Joseph Naor</a>, <a href="../../indices/a-tree/r/Raghavendra:Prasad.html">Prasad Raghavendra</a>, <a href="../../indices/a-tree/s/Schwartz:Roy.html">Roy Schwartz</a>: <br><b>Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. </b>11-20<br><a href="http://doi.acm.org/10.1145/1374376.1374379"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ManokaranNRS08">BibTeX</a></font> <li><a name="AroraKKSTV08" href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>, <a href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>, <a href="../../indices/a-tree/k/Kolla:Alexandra.html">Alexandra Kolla</a>, <a href="../../indices/a-tree/s/Steurer:David.html">David Steurer</a>, <a href="../../indices/a-tree/t/Tulsiani:Madhur.html">Madhur Tulsiani</a>, <a href="../../indices/a-tree/v/Vishnoi:Nisheeth_K=.html">Nisheeth K. Vishnoi</a>: <br><b>Unique games on expanding constraint graphs are easy: extended abstract. </b>21-28<br><a href="http://doi.acm.org/10.1145/1374376.1374380"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AroraKKSTV08">BibTeX</a></font> </ul> <h2>1B</h2> <ul> <li><a name="BodirskyK08" href="../../indices/a-tree/b/Bodirsky:Manuel.html">Manuel Bodirsky</a>, <a href="../../indices/a-tree/k/K=aacute=ra:Jan.html">Jan Kára</a>: <br><b>The complexity of temporal constraint satisfaction problems. </b>29-38<br><a href="http://doi.acm.org/10.1145/1374376.1374382"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BodirskyK08">BibTeX</a></font> <li><a name="Nandakumar08" href="../../indices/a-tree/n/Nandakumar:Satyadev.html">Satyadev Nandakumar</a>: <br><b>An effective ergodic theorem and some applications. </b>39-44<br><a href="http://doi.acm.org/10.1145/1374376.1374383"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Nandakumar08">BibTeX</a></font> <li><a name="DasK08" href="../../indices/a-tree/d/Das:Abhimanyu.html">Abhimanyu Das</a>, <a href="../../indices/a-tree/k/Kempe:David.html">David Kempe</a>: <br><b>Algorithms for subset selection in linear regression. </b>45-54<br><a href="http://doi.acm.org/10.1145/1374376.1374384"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DasK08">BibTeX</a></font> </ul> <h2>Invited talk</h2> <ul> <li><a name="Rexford08" href="../../indices/a-tree/r/Rexford:Jennifer.html">Jennifer Rexford</a>: <br><b>Rethinking internet routing. </b>55-56<br><a href="http://doi.acm.org/10.1145/1374376.1374386"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Rexford08">BibTeX</a></font> </ul> <h2>3A</h2> <ul> <li><a name="LevinSZ08" href="../../indices/a-tree/l/Levin:Hagay.html">Hagay Levin</a>, <a href="../../indices/a-tree/s/Schapira:Michael.html">Michael Schapira</a>, <a href="../../indices/a-tree/z/Zohar:Aviv.html">Aviv Zohar</a>: <br><b>Interdomain routing and games. </b>57-66<br><a href="http://doi.acm.org/10.1145/1374376.1374388"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LevinSZ08">BibTeX</a></font> <li><a name="Vondrak08" href="../../indices/a-tree/v/Vondr=aacute=k:Jan.html">Jan Vondrák</a>: <br><b>Optimal approximation for the submodular welfare problem in the value oracle model. </b>67-74<br><a href="http://doi.acm.org/10.1145/1374376.1374389"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Vondrak08">BibTeX</a></font> <li><a name="HartlineR08" href="../../indices/a-tree/h/Hartline:Jason_D=.html">Jason D. Hartline</a>, <a href="../../indices/a-tree/r/Roughgarden:Tim.html">Tim Roughgarden</a>: <br><b>Optimal mechanism design and money burning. </b>75-84<br><a href="http://doi.acm.org/10.1145/1374376.1374390"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HartlineR08">BibTeX</a></font> </ul> <h2>3B</h2> <ul> <li><a name="Sherstov08" href="../../indices/a-tree/s/Sherstov:Alexander_A=.html">Alexander A. Sherstov</a>: <br><b>The pattern matrix method for lower bounds on quantum communication. </b>85-94<br><a href="http://doi.acm.org/10.1145/1374376.1374392"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Sherstov08">BibTeX</a></font> <li><a name="Gavinsky08" href="../../indices/a-tree/g/Gavinsky:Dmitry.html">Dmitry Gavinsky</a>: <br><b>Classical interaction cannot replace a quantum message. </b>95-102<br><a href="http://doi.acm.org/10.1145/1374376.1374393"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Gavinsky08">BibTeX</a></font> <li><a name="ReichardtS08" href="../../indices/a-tree/r/Reichardt:Ben.html">Ben Reichardt</a>, <a href="../../indices/a-tree/s/Spalek:Robert.html">Robert Spalek</a>: <br><b>Span-program-based quantum algorithm for evaluating formulas. </b>103-112<br><a href="http://doi.acm.org/10.1145/1374376.1374394"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ReichardtS08">BibTeX</a></font> </ul> <h2>4A</h2> <ul> <li><a name="GoldwasserKR08" href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/k/Kalai:Yael_Tauman.html">Yael Tauman Kalai</a>, <a href="../../indices/a-tree/r/Rothblum:Guy_N=.html">Guy N. Rothblum</a>: <br><b>Delegating computation: interactive proofs for muggles. </b>113-122<br><a href="http://doi.acm.org/10.1145/1374376.1374396"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldwasserKR08">BibTeX</a></font> <li><a name="JubaS08" href="../../indices/a-tree/j/Juba:Brendan.html">Brendan Juba</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: <br><b>Universal semantic communication I. </b>123-132<br><a href="http://doi.acm.org/10.1145/1374376.1374397"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/JubaS08">BibTeX</a></font> <li><a name="FortnowS08" href="../../indices/a-tree/f/Fortnow:Lance.html">Lance Fortnow</a>, <a href="../../indices/a-tree/s/Santhanam:Rahul.html">Rahul Santhanam</a>: <br><b>Infeasibility of instance compression and succinct PCPs for NP. </b>133-142<br><a href="http://doi.acm.org/10.1145/1374376.1374398"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FortnowS08">BibTeX</a></font> <li><a name="GoldwasserGHKR08" href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/g/Gutfreund:Dan.html">Dan Gutfreund</a>, <a href="../../indices/a-tree/h/Healy:Alexander.html">Alexander Healy</a>, <a href="../../indices/a-tree/k/Kaufman:Tali.html">Tali Kaufman</a>, <a href="../../indices/a-tree/r/Rothblum:Guy_N=.html">Guy N. Rothblum</a>: <br><b>A (de)constructive approach to program checking. </b>143-152<br><a href="http://doi.acm.org/10.1145/1374376.1374399"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoldwasserGHKR08">BibTeX</a></font> </ul> <h2>4B</h2> <ul> <li><a name="FakcharoenpholL08" href="../../indices/a-tree/f/Fakcharoenphol:Jittat.html">Jittat Fakcharoenphol</a>, <a href="../../indices/a-tree/l/Laekhanukit:Bundit.html">Bundit Laekhanukit</a>: <br><b>An o(log<sup>2</sup> k)-approximation algorithm for the k-vertex connected spanning subgraph problem. </b>153-158<br><a href="http://doi.acm.org/10.1145/1374376.1374401"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FakcharoenpholL08">BibTeX</a></font> <li><a name="Thorup08" href="../../indices/a-tree/t/Thorup:Mikkel.html">Mikkel Thorup</a>: <br><b>Minimum k-way cuts via deterministic greedy tree packing. </b>159-166<br><a href="http://doi.acm.org/10.1145/1374376.1374402"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Thorup08">BibTeX</a></font> <li><a name="ChakrabortyCK08" href="../../indices/a-tree/c/Chakraborty:Tanmoy.html">Tanmoy Chakraborty</a>, <a 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>Network design for vertex connectivity. </b>167-176<br><a href="http://doi.acm.org/10.1145/1374376.1374403"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChakrabortyCK08">BibTeX</a></font> <li><a name="ChenLL08" href="../../indices/a-tree/c/Chen:Jianer.html">Jianer Chen</a>, <a href="../../indices/a-tree/l/Liu_0002:Yang.html">Yang Liu</a>, <a href="../../indices/a-tree/l/Lu:Songjian.html">Songjian Lu</a>, <a href="../../indices/a-tree/o/O=Sullivan:Barry.html">Barry O'Sullivan</a>, <a href="../../indices/a-tree/r/Razgon:Igor.html">Igor Razgon</a>: <br><b>A fixed-parameter algorithm for the directed feedback vertex set problem. </b>177-186<br><a href="http://doi.acm.org/10.1145/1374376.1374404"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChenLL08">BibTeX</a></font> </ul> <h2>5A</h2> <ul> <li><a name="PeikertW08" href="../../indices/a-tree/p/Peikert:Chris.html">Chris Peikert</a>, <a href="../../indices/a-tree/w/Waters:Brent.html">Brent Waters</a>: <br><b>Lossy trapdoor functions and their applications. </b>187-196<br><a href="http://doi.acm.org/10.1145/1374376.1374406"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/PeikertW08">BibTeX</a></font> <li><a name="GentryPV08" href="../../indices/a-tree/g/Gentry:Craig.html">Craig Gentry</a>, <a href="../../indices/a-tree/p/Peikert:Chris.html">Chris Peikert</a>, <a href="../../indices/a-tree/v/Vaikuntanathan:Vinod.html">Vinod Vaikuntanathan</a>: <br><b>Trapdoors for hard lattices and new cryptographic constructions. </b>197-206<br><a href="http://doi.acm.org/10.1145/1374376.1374407"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GentryPV08">BibTeX</a></font> <li><a name="GamaN08" href="../../indices/a-tree/g/Gama:Nicolas.html">Nicolas Gama</a>, <a href="../../indices/a-tree/n/Nguyen:Phong_Q=.html">Phong Q. Nguyen</a>: <br><b>Finding short lattice vectors within mordell's inequality. </b>207-216<br><a href="http://doi.acm.org/10.1145/1374376.1374408"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GamaN08">BibTeX</a></font> </ul> <h2>5B</h2> <ul> <li><a name="AttiyaHW08" href="../../indices/a-tree/a/Attiya:Hagit.html">Hagit Attiya</a>, <a href="../../indices/a-tree/h/Hendler:Danny.html">Danny Hendler</a>, <a href="../../indices/a-tree/w/Woelfel:Philipp.html">Philipp Woelfel</a>: <br><b>Tight rmr lower bounds for mutual exclusion and other problems. </b>217-226<br><a href="http://doi.acm.org/10.1145/1374376.1374410"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AttiyaHW08">BibTeX</a></font> <li><a name="CoteMP08" href="../../indices/a-tree/c/Cote:Aaron.html">Aaron Cote</a>, <a href="../../indices/a-tree/m/Meyerson:Adam.html">Adam Meyerson</a>, <a href="../../indices/a-tree/p/Poplawski:Laura_J=.html">Laura J. Poplawski</a>: <br><b>Randomized k-server on hierarchical binary trees. </b>227-234<br><a href="http://doi.acm.org/10.1145/1374376.1374411"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CoteMP08">BibTeX</a></font> <li><a name="BansalBN08" href="../../indices/a-tree/b/Bansal:Nikhil.html">Nikhil Bansal</a>, <a href="../../indices/a-tree/b/Buchbinder:Niv.html">Niv Buchbinder</a>, <a href="../../indices/a-tree/n/Naor:Joseph.html">Joseph Naor</a>: <br><b>Randomized competitive algorithms for generalized caching. </b>235-244<br><a href="http://doi.acm.org/10.1145/1374376.1374412"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BansalBN08">BibTeX</a></font> </ul> <h2>6</h2> <ul> <li><a name="Raghavendra08" href="../../indices/a-tree/r/Raghavendra:Prasad.html">Prasad Raghavendra</a>: <br><b>Optimal algorithms and inapproximability results for every CSP? </b>245-254<br><a href="http://doi.acm.org/10.1145/1374376.1374414"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Raghavendra08">BibTeX</a></font> <li><a name="Racke08" href="../../indices/a-tree/r/R=auml=cke:Harald.html">Harald Räcke</a>: <br><b>Optimal hierarchical decompositions for congestion minimization in networks. </b>255-264<br><a href="http://doi.acm.org/10.1145/1374376.1374415"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Racke08">BibTeX</a></font> </ul> <h2>7A</h2> <ul> <li><a name="GopalanKZ08" href="../../indices/a-tree/g/Gopalan:Parikshit.html">Parikshit Gopalan</a>, <a href="../../indices/a-tree/k/Klivans:Adam_R=.html">Adam R. Klivans</a>, <a href="../../indices/a-tree/z/Zuckerman:David.html">David Zuckerman</a>: <br><b>List-decoding reed-muller codes over small fields. </b>265-274<br><a href="http://doi.acm.org/10.1145/1374376.1374417"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GopalanKZ08">BibTeX</a></font> <li><a name="DinurGKS08" href="../../indices/a-tree/d/Dinur:Irit.html">Irit Dinur</a>, <a href="../../indices/a-tree/g/Grigorescu:Elena.html">Elena Grigorescu</a>, <a href="../../indices/a-tree/k/Kopparty:Swastik.html">Swastik Kopparty</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: <br><b>Decodability of group homomorphisms beyond the johnson bound. </b>275-284<br><a href="http://doi.acm.org/10.1145/1374376.1374418"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DinurGKS08">BibTeX</a></font> <li><a name="Meir08" href="../../indices/a-tree/m/Meir:Or.html">Or Meir</a>: <br><b>Combinatorial construction of locally testable codes. </b>285-294<br><a href="http://doi.acm.org/10.1145/1374376.1374419"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Meir08">BibTeX</a></font> </ul> <h2>7B</h2> <ul> <li><a name="KleinbergT08" href="../../indices/a-tree/k/Kleinberg:Jon_M=.html">Jon M. Kleinberg</a>, <a href="../../indices/a-tree/t/Tardos:=Eacute=va.html">Éva Tardos</a>: <br><b>Balanced outcomes in social exchange networks. </b>295-304<br><a href="http://doi.acm.org/10.1145/1374376.1376994"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KleinbergT08">BibTeX</a></font> <li><a name="ChenGP08" href="../../indices/a-tree/c/Chen:Yiling.html">Yiling Chen</a>, <a href="../../indices/a-tree/g/Goel:Sharad.html">Sharad Goel</a>, <a href="../../indices/a-tree/p/Pennock:David_M=.html">David M. Pennock</a>: <br><b>Pricing combinatorial markets for tournaments. </b>305-314<br><a href="http://doi.acm.org/10.1145/1374376.1374421"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChenGP08">BibTeX</a></font> <li><a name="ColeF08" href="../../indices/a-tree/c/Cole:Richard.html">Richard Cole</a>, <a href="../../indices/a-tree/f/Fleischer:Lisa.html">Lisa Fleischer</a>: <br><b>Fast-converging tatonnement algorithms for one-time and ongoing market problems. </b>315-324<br><a href="http://doi.acm.org/10.1145/1374376.1374422"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ColeF08">BibTeX</a></font> </ul> <h2>8A</h2> <ul> <li><a name="Ben-AroyaT08" href="../../indices/a-tree/b/Ben=Aroya:Avraham.html">Avraham Ben-Aroya</a>, <a href="../../indices/a-tree/t/Ta=Shma:Amnon.html">Amnon Ta-Shma</a>: <br><b>A combinatorial construction of almost-ramanujan graphs using the zig-zag product. </b>325-334<br><a href="http://doi.acm.org/10.1145/1374376.1374424"><i>Electronic Edition</i></a> (<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-AroyaT08">BibTeX</a></font> <li><a name="ODonnellW08" href="../../indices/a-tree/o/O=Donnell:Ryan.html">Ryan O'Donnell</a>, <a href="../../indices/a-tree/w/Wu:Yi.html">Yi Wu</a>: <br><b>An optimal sdp algorithm for max-cut, and equally optimal long code tests. </b>335-344<br><a href="http://doi.acm.org/10.1145/1374376.1374425"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ODonnellW08">BibTeX</a></font> <li><a name="KhotS08" href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>, <a href="../../indices/a-tree/s/Saket:Rishi.html">Rishi Saket</a>: <br><b>On hardness of learning intersection of two halfspaces. </b>345-354<br><a href="http://doi.acm.org/10.1145/1374376.1374426"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KhotS08">BibTeX</a></font> </ul> <h2>8B</h2> <ul> <li><a name="SkopalikV08" href="../../indices/a-tree/s/Skopalik:Alexander.html">Alexander Skopalik</a>, <a href="../../indices/a-tree/v/V=ouml=cking:Berthold.html">Berthold Vöcking</a>: <br><b>Inapproximability of pure nash equilibria. </b>355-364<br><a href="http://doi.acm.org/10.1145/1374376.1374428"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/SkopalikV08">BibTeX</a></font> <li><a name="BorgsCIKMP08" 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/i/Immorlica:Nicole.html">Nicole Immorlica</a>, <a href="../../indices/a-tree/k/Kalai:Adam_Tauman.html">Adam Tauman Kalai</a>, <a href="../../indices/a-tree/m/Mirrokni:Vahab_S=.html">Vahab S. Mirrokni</a>, <a href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: <br><b>The myth of the folk theorem. </b>365-372<br><a href="http://doi.acm.org/10.1145/1374376.1374429"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BorgsCIKMP08">BibTeX</a></font> <li><a name="BlumHLR08" href="../../indices/a-tree/b/Blum:Avrim.html">Avrim Blum</a>, <a href="../../indices/a-tree/h/Hajiaghayi:MohammadTaghi.html">MohammadTaghi Hajiaghayi</a>, <a href="../../indices/a-tree/l/Ligett:Katrina.html">Katrina Ligett</a>, <a href="../../indices/a-tree/r/Roth:Aaron.html">Aaron Roth</a>: <br><b>Regret minimization and the price of total anarchy. </b>373-382<br><a href="http://doi.acm.org/10.1145/1374376.1374430"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BlumHLR08">BibTeX</a></font> </ul> <h2>9A</h2> <ul> <li><a name="Valiant08" href="../../indices/a-tree/v/Valiant:Paul.html">Paul Valiant</a>: <br><b>Testing symmetric properties of distributions. </b>383-392<br><a href="http://doi.acm.org/10.1145/1374376.1374432"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Valiant08">BibTeX</a></font> <li><a name="BenjaminiSS08" 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/s/Shapira:Asaf.html">Asaf Shapira</a>: <br><b>Every minor-closed property of sparse graphs is testable. </b>393-402<br><a href="http://doi.acm.org/10.1145/1374376.1374433"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BenjaminiSS08">BibTeX</a></font> <li><a name="KaufmanS08" href="../../indices/a-tree/k/Kaufman:Tali.html">Tali Kaufman</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: <br><b>Algebraic property testing: the role of invariance. </b>403-412<br><a href="http://doi.acm.org/10.1145/1374376.1374434"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KaufmanS08">BibTeX</a></font> </ul> <h2>9B</h2> <ul> <li><a name="GordonHKL08" href="../../indices/a-tree/g/Gordon:S=_Dov.html">S. Dov Gordon</a>, <a href="../../indices/a-tree/h/Hazay:Carmit.html">Carmit Hazay</a>, <a href="../../indices/a-tree/k/Katz:Jonathan.html">Jonathan Katz</a>, <a href="../../indices/a-tree/l/Lindell:Yehuda.html">Yehuda Lindell</a>: <br><b>Complete fairness in secure two-party computation. </b>413-422<br><a href="http://doi.acm.org/10.1145/1374376.1374436"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GordonHKL08">BibTeX</a></font> <li><a name="KolN08" href="../../indices/a-tree/k/Kol:Gillat.html">Gillat Kol</a>, <a href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>: <br><b>Games for exchanging information. </b>423-432<br><a href="http://doi.acm.org/10.1145/1374376.1374437"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KolN08">BibTeX</a></font> <li><a name="IshaiKOS08" 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/o/Ostrovsky:Rafail.html">Rafail Ostrovsky</a>, <a href="../../indices/a-tree/s/Sahai:Amit.html">Amit Sahai</a>: <br><b>Cryptography with constant computational overhead. </b>433-442<br><a href="http://doi.acm.org/10.1145/1374376.1374438"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/IshaiKOS08">BibTeX</a></font> </ul> <h2>10A</h2> <ul> <li><a name="GoyalOS08" href="../../indices/a-tree/g/Goyal:Navin.html">Navin Goyal</a>, <a href="../../indices/a-tree/o/Olver:Neil.html">Neil Olver</a>, <a href="../../indices/a-tree/s/Shepherd:F=_Bruce.html">F. Bruce Shepherd</a>: <br><b>The vpn conjecture is true. </b>443-450<br><a href="http://doi.acm.org/10.1145/1374376.1374440"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GoyalOS08">BibTeX</a></font> <li><a name="DaitchS08" href="../../indices/a-tree/d/Daitch:Samuel_I=.html">Samuel I. Daitch</a>, <a href="../../indices/a-tree/s/Spielman:Daniel_A=.html">Daniel A. Spielman</a>: <br><b>Faster approximate lossy generalized flow via interior point algorithms. </b>451-460<br><a href="http://doi.acm.org/10.1145/1374376.1374441"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DaitchS08">BibTeX</a></font> <li><a name="OrecchiaSVV08" href="../../indices/a-tree/o/Orecchia:Lorenzo.html">Lorenzo Orecchia</a>, <a href="../../indices/a-tree/s/Schulman:Leonard_J=.html">Leonard J. Schulman</a>, <a href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>, <a href="../../indices/a-tree/v/Vishnoi:Nisheeth_K=.html">Nisheeth K. Vishnoi</a>: <br><b>On partitioning graphs via single commodity flows. </b>461-470<br><a href="http://doi.acm.org/10.1145/1374376.1374442"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/OrecchiaSVV08">BibTeX</a></font> <li><a name="KawarabayashiM08" 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>Graph and map isomorphism and all polyhedral embeddings in linear time. </b>471-480<br><a href="http://doi.acm.org/10.1145/1374376.1374443"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KawarabayashiM08">BibTeX</a></font> </ul> <h2>10B</h2> <ul> <li><a name="Umans08" href="../../indices/a-tree/u/Umans:Christopher.html">Christopher Umans</a>: <br><b>Fast polynomial factorization and modular composition in small characteristic. </b>481-490<br><a href="http://doi.acm.org/10.1145/1374376.1374445"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Umans08">BibTeX</a></font> <li><a name="CaiCL08" href="../../indices/a-tree/c/Cai:Jin=yi.html">Jin-yi Cai</a>, <a href="../../indices/a-tree/c/Chen:Xi.html">Xi Chen</a>, <a href="../../indices/a-tree/l/Li:Dong.html">Dong Li</a>: <br><b>A quadratic lower bound for the permanent and determinant problem over any characteristic != 2. </b>491-498<br><a href="http://doi.acm.org/10.1145/1374376.1374446"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CaiCL08">BibTeX</a></font> <li><a name="DeKSS08" href="../../indices/a-tree/d/De:Anindya.html">Anindya De</a>, <a href="../../indices/a-tree/k/Kurur:Piyush_P=.html">Piyush P. Kurur</a>, <a href="../../indices/a-tree/s/Saha:Chandan.html">Chandan Saha</a>, <a href="../../indices/a-tree/s/Saptharishi:Ramprasad.html">Ramprasad Saptharishi</a>: <br><b>Fast integer multiplication using modular arithmetic. </b>499-506<br><a href="http://doi.acm.org/10.1145/1374376.1374447"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DeKSS08">BibTeX</a></font> <li><a name="ShpilkaV08" href="../../indices/a-tree/s/Shpilka:Amir.html">Amir Shpilka</a>, <a href="../../indices/a-tree/v/Volkovich:Ilya.html">Ilya Volkovich</a>: <br><b>Read-once polynomial identity testing. </b>507-516<br><a href="http://doi.acm.org/10.1145/1374376.1374448"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ShpilkaV08">BibTeX</a></font> </ul> <h2>11A</h2> <ul> <li><a name="ODonnellS08" href="../../indices/a-tree/o/O=Donnell:Ryan.html">Ryan O'Donnell</a>, <a href="../../indices/a-tree/s/Servedio:Rocco_A=.html">Rocco A. Servedio</a>: <br><b>The chow parameters problem. </b>517-526<br><a href="http://doi.acm.org/10.1145/1374376.1374450"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ODonnellS08">BibTeX</a></font> <li><a name="GopalanKK08" href="../../indices/a-tree/g/Gopalan:Parikshit.html">Parikshit Gopalan</a>, <a href="../../indices/a-tree/k/Kalai:Adam_Tauman.html">Adam Tauman Kalai</a>, <a href="../../indices/a-tree/k/Klivans:Adam_R=.html">Adam R. Klivans</a>: <br><b>Agnostically learning decision trees. </b>527-536<br><a href="http://doi.acm.org/10.1145/1374376.1374451"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GopalanKK08">BibTeX</a></font> <li><a name="DasguptaF08" href="../../indices/a-tree/d/Dasgupta:Sanjoy.html">Sanjoy Dasgupta</a>, <a href="../../indices/a-tree/f/Freund:Yoav.html">Yoav Freund</a>: <br><b>Random projection trees and low dimensional manifolds. </b>537-546<br><a href="http://doi.acm.org/10.1145/1374376.1374452"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DasguptaF08">BibTeX</a></font> </ul> <h2>11B</h2> <ul> <li><a name="LovettMS08" href="../../indices/a-tree/l/Lovett:Shachar.html">Shachar Lovett</a>, <a href="../../indices/a-tree/m/Meshulam:Roy.html">Roy Meshulam</a>, <a href="../../indices/a-tree/s/Samorodnitsky:Alex.html">Alex Samorodnitsky</a>: <br><b>Inverse conjecture for the gowers norm is false. </b>547-556<br><a href="http://doi.acm.org/10.1145/1374376.1374454"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LovettMS08">BibTeX</a></font> <li><a name="Lovett08" href="../../indices/a-tree/l/Lovett:Shachar.html">Shachar Lovett</a>: <br><b>Unconditional pseudorandom generators for low degree polynomials. </b>557-562<br><a href="http://doi.acm.org/10.1145/1374376.1374455"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Lovett08">BibTeX</a></font> <li><a name="SpielmanS08" href="../../indices/a-tree/s/Spielman:Daniel_A=.html">Daniel A. Spielman</a>, <a href="../../indices/a-tree/s/Srivastava:Nikhil.html">Nikhil Srivastava</a>: <br><b>Graph sparsification by effective resistances. </b>563-568<br><a href="http://doi.acm.org/10.1145/1374376.1374456"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/SpielmanS08">BibTeX</a></font> </ul> <h2>Tutorial</h2> <ul> <li><a name="ODonnell08" href="../../indices/a-tree/o/O=Donnell:Ryan.html">Ryan O'Donnell</a>: <br><b>Some topics in analysis of boolean functions. </b>569-578<br><a href="http://doi.acm.org/10.1145/1374376.1374458"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ODonnell08">BibTeX</a></font> </ul> <h2>13A</h2> <ul> <li><a name="ImpagliazzoJKW08" href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/j/Jaiswal:Ragesh.html">Ragesh Jaiswal</a>, <a href="../../indices/a-tree/k/Kabanets:Valentine.html">Valentine Kabanets</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>Uniform direct product theorems: simplified, optimized, and derandomized. </b>579-588<br><a href="http://doi.acm.org/10.1145/1374376.1374460"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ImpagliazzoJKW08">BibTeX</a></font> <li><a name="ShaltielV08" href="../../indices/a-tree/s/Shaltiel:Ronen.html">Ronen Shaltiel</a>, <a href="../../indices/a-tree/v/Viola:Emanuele.html">Emanuele Viola</a>: <br><b>Hardness amplification proofs require majority. </b>589-598<br><a href="http://doi.acm.org/10.1145/1374376.1374461"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ShaltielV08">BibTeX</a></font> <li><a name="JainKN08" href="../../indices/a-tree/j/Jain:Rahul.html">Rahul Jain</a>, <a href="../../indices/a-tree/k/Klauck:Hartmut.html">Hartmut Klauck</a>, <a href="../../indices/a-tree/n/Nayak:Ashwin.html">Ashwin Nayak</a>: <br><b>Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract. </b>599-608<br><a href="http://doi.acm.org/10.1145/1374376.1374462"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/JainKN08">BibTeX</a></font> </ul> <h2>13B</h2> <ul> <li><a name="BlumLR08" href="../../indices/a-tree/b/Blum:Avrim.html">Avrim Blum</a>, <a href="../../indices/a-tree/l/Ligett:Katrina.html">Katrina Ligett</a>, <a href="../../indices/a-tree/r/Roth:Aaron.html">Aaron Roth</a>: <br><b>A learning theory approach to non-interactive database privacy. </b>609-618<br><a href="http://doi.acm.org/10.1145/1374376.1374464"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BlumLR08">BibTeX</a></font> <li><a name="Feldman08" href="../../indices/a-tree/f/Feldman:Vitaly.html">Vitaly Feldman</a>: <br><b>Evolvability from learning algorithms. </b>619-628<br><a href="http://doi.acm.org/10.1145/1374376.1374465"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Feldman08">BibTeX</a></font> <li><a name="KalaiMV08" href="../../indices/a-tree/k/Kalai:Adam_Tauman.html">Adam Tauman Kalai</a>, <a href="../../indices/a-tree/m/Mansour:Yishay.html">Yishay Mansour</a>, <a href="../../indices/a-tree/v/Verbin:Elad.html">Elad Verbin</a>: <br><b>On agnostic boosting and parity learning. </b>629-638<br><a href="http://doi.acm.org/10.1145/1374376.1374466"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KalaiMV08">BibTeX</a></font> </ul> <h2>Invited talk</h2> <ul> <li><a name="Haussler08" href="../../indices/a-tree/h/Haussler:David.html">David Haussler</a>: <br><b>Computing how we became human. </b>639-640<br><a href="http://doi.acm.org/10.1145/1374376.1374468"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Haussler08">BibTeX</a></font> </ul> <h2>15A</h2> <ul> <li><a name="ChakrabartiCM08" href="../../indices/a-tree/c/Chakrabarti:Amit.html">Amit Chakrabarti</a>, <a href="../../indices/a-tree/c/Cormode:Graham.html">Graham Cormode</a>, <a href="../../indices/a-tree/m/McGregor:Andrew.html">Andrew McGregor</a>: <br><b>Robust lower bounds for communication and stream computation. </b>641-650<br><a href="http://doi.acm.org/10.1145/1374376.1374470"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChakrabartiCM08">BibTeX</a></font> <li><a name="MironovNS08" href="../../indices/a-tree/m/Mironov:Ilya.html">Ilya Mironov</a>, <a href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>, <a href="../../indices/a-tree/s/Segev:Gil.html">Gil Segev</a>: <br><b>Sketching in adversarial environments. </b>651-660<br><a href="http://doi.acm.org/10.1145/1374376.1374471"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MironovNS08">BibTeX</a></font> <li><a name="BarkolIW08" href="../../indices/a-tree/b/Barkol:Omer.html">Omer Barkol</a>, <a href="../../indices/a-tree/i/Ishai:Yuval.html">Yuval Ishai</a>, <a href="../../indices/a-tree/w/Weinreb:Enav.html">Enav Weinreb</a>: <br><b>Communication in the presence of replication. </b>661-670<br><a href="http://doi.acm.org/10.1145/1374376.1374472"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BarkolIW08">BibTeX</a></font> </ul> <h2>15B</h2> <ul> <li><a name="BalcanBV08" href="../../indices/a-tree/b/Balcan:Maria=Florina.html">Maria-Florina Balcan</a>, <a href="../../indices/a-tree/b/Blum:Avrim.html">Avrim Blum</a>, <a href="../../indices/a-tree/v/Vempala:Santosh.html">Santosh Vempala</a>: <br><b>A discriminative framework for clustering via similarity functions. </b>671-680<br><a href="http://doi.acm.org/10.1145/1374376.1374474"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BalcanBV08">BibTeX</a></font> <li><a name="KleinbergSU08" href="../../indices/a-tree/k/Kleinberg:Robert.html">Robert Kleinberg</a>, <a href="../../indices/a-tree/s/Slivkins:Aleksandrs.html">Aleksandrs Slivkins</a>, <a href="../../indices/a-tree/u/Upfal:Eli.html">Eli Upfal</a>: <br><b>Multi-armed bandits in metric spaces. </b>681-690<br><a href="http://doi.acm.org/10.1145/1374376.1374475"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KleinbergSU08">BibTeX</a></font> <li><a name="AwerbuchK08" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/k/Khandekar:Rohit.html">Rohit Khandekar</a>: <br><b>Stateless distributed gradient descent for positive linear programs. </b>691-700<br><a href="http://doi.acm.org/10.1145/1374376.1374476"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AwerbuchK08">BibTeX</a></font> </ul> <h2>16A</h2> <ul> <li><a name="NordstromH08" href="../../indices/a-tree/n/Nordstr=ouml=m:Jakob.html">Jakob Nordström</a>, <a href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>: <br><b>Towards an optimal separation of space and length in resolution. </b>701-710<br><a href="http://doi.acm.org/10.1145/1374376.1374478"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/NordstromH08">BibTeX</a></font> <li><a name="Raz08" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>: <br><b>Elusive functions and lower bounds for arithmetic circuits. </b>711-720<br><a href="http://doi.acm.org/10.1145/1374376.1374479"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Raz08">BibTeX</a></font> <li><a name="Rossman08" href="../../indices/a-tree/r/Rossman:Benjamin.html">Benjamin Rossman</a>: <br><b>On the constant-depth complexity of k-clique. </b>721-730<br><a href="http://doi.acm.org/10.1145/1374376.1374480"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Rossman08">BibTeX</a></font> <li><a name="AaronsonW08" href="../../indices/a-tree/a/Aaronson:Scott.html">Scott Aaronson</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>Algebrization: a new barrier in complexity theory. </b>731-740<br><a href="http://doi.acm.org/10.1145/1374376.1374481"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AaronsonW08">BibTeX</a></font> <li><a name="DvirSY08" href="../../indices/a-tree/d/Dvir:Zeev.html">Zeev Dvir</a>, <a href="../../indices/a-tree/s/Shpilka:Amir.html">Amir Shpilka</a>, <a href="../../indices/a-tree/y/Yehudayoff:Amir.html">Amir Yehudayoff</a>: <br><b>Hardness-randomness tradeoffs for bounded depth arithmetic circuits. </b>741-748<br><a href="http://doi.acm.org/10.1145/1374376.1374482"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DvirSY08">BibTeX</a></font> </ul> <h2>16B</h2> <ul> <li><a name="ChoiK08" href="../../indices/a-tree/c/Choi:Sung=Soon.html">Sung-Soon Choi</a>, <a href="../../indices/a-tree/k/Kim:Jeong_Han.html">Jeong Han Kim</a>: <br><b>Optimal query complexity bounds for finding graphs. </b>749-758<br><a href="http://doi.acm.org/10.1145/1374376.1374484"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChoiK08">BibTeX</a></font> <li><a name="LauS08" href="../../indices/a-tree/l/Lau:Lap_Chi.html">Lap Chi Lau</a>, <a href="../../indices/a-tree/s/Singh:Mohit.html">Mohit Singh</a>: <br><b>Additive approximation for bounded degree survivable network design. </b>759-768<br><a href="http://doi.acm.org/10.1145/1374376.1374485"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LauS08">BibTeX</a></font> <li><a name="BansalKN08" href="../../indices/a-tree/b/Bansal:Nikhil.html">Nikhil Bansal</a>, <a href="../../indices/a-tree/k/Khandekar:Rohit.html">Rohit Khandekar</a>, <a href="../../indices/a-tree/n/Nagarajan:Viswanath.html">Viswanath Nagarajan</a>: <br><b>Additive guarantees for degree bounded directed network design. </b>769-778<br><a href="http://doi.acm.org/10.1145/1374376.1374486"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BansalKN08">BibTeX</a></font> <li><a name="FriezeVV08" href="../../indices/a-tree/f/Frieze:Alan_M=.html">Alan M. Frieze</a>, <a href="../../indices/a-tree/v/Vempala:Santosh.html">Santosh Vempala</a>, <a href="../../indices/a-tree/v/Vera:Juan.html">Juan Vera</a>: <br><b>Logconcave random graphs. </b>779-788<br><a href="http://doi.acm.org/10.1145/1374376.1374487"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FriezeVV08">BibTeX</a></font> <li><a name="BartoKN08" href="../../indices/a-tree/b/Barto:Libor.html">Libor Barto</a>, <a href="../../indices/a-tree/k/Kozik:Marcin.html">Marcin Kozik</a>, <a href="../../indices/a-tree/n/Niven:Todd.html">Todd Niven</a>: <br><b>Graphs, polymorphisms and the complexity of homomorphism problems. </b>789-796<br><a href="http://doi.acm.org/10.1145/1374376.1374488"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BartoKN08">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:13 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
