focs2008.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>FOCS 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>49. <a href="index.html">FOCS</a> 2008: Philadelphia, Pennsylvania, USA</h1> 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA. IEEE Computer Society 2008 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/2008">BibTeX</a></font> <h2>Tutorials</h2> <ul> <li><a name="Aaronson08" href="../../indices/a-tree/a/Aaronson:Scott.html">Scott Aaronson</a>: <br><b>The Polynomial Method in Quantum and Classical Computing. </b>3<br><a href="http://dx.doi.org/10.1109/FOCS.2008.91"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Aaronson08">BibTeX</a></font> <li><a name="AggarwalM08" href="../../indices/a-tree/a/Aggarwal:Gagan.html">Gagan Aggarwal</a>, <a href="../../indices/a-tree/m/Muthukrishnan:S=.html">S. Muthukrishnan</a>: <br><b>Theory of Sponsored Search Auctions. </b>7<br><a href="http://dx.doi.org/10.1109/FOCS.2008.88"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AggarwalM08">BibTeX</a></font> <li><a name="Trevisan08" href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>: <br><b>Average-case Complexity. </b>11<br><a href="http://dx.doi.org/10.1109/FOCS.2008.90"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Trevisan08">BibTeX</a></font> </ul> <h2>Regular Papers</h2> <ul> <li><a name="DhangwatnotaiDDR08" href="../../indices/a-tree/d/Dhangwatnotai:Peerapong.html">Peerapong Dhangwatnotai</a>, <a href="../../indices/a-tree/d/Dobzinski:Shahar.html">Shahar Dobzinski</a>, <a href="../../indices/a-tree/d/Dughmi:Shaddin.html">Shaddin Dughmi</a>, <a href="../../indices/a-tree/r/Roughgarden:Tim.html">Tim Roughgarden</a>: <br><b>Truthful Approximation Schemes for Single-Parameter Agents. </b>15-24<br><a href="http://dx.doi.org/10.1109/FOCS.2008.71"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DhangwatnotaiDDR08">BibTeX</a></font> <li><a name="DaskalakisP08" href="../../indices/a-tree/d/Daskalakis:Constantinos.html">Constantinos Daskalakis</a>, <a href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: <br><b>Discretized Multinomial Distributions and Nash Equilibria in Anonymous Games. </b>25-34<br><a href="http://dx.doi.org/10.1109/FOCS.2008.84"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DaskalakisP08">BibTeX</a></font> <li><a name="CheungS08" href="../../indices/a-tree/c/Cheung:Maurice.html">Maurice Cheung</a>, <a href="../../indices/a-tree/s/Swamy:Chaitanya.html">Chaitanya Swamy</a>: <br><b>Approximation Algorithms for Single-minded Envy-free Profit-maximization Problems with Limited Supply. </b>35-44<br><a href="http://dx.doi.org/10.1109/FOCS.2008.15"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CheungS08">BibTeX</a></font> <li><a name="DevanurK08" href="../../indices/a-tree/d/Devanur:Nikhil_R=.html">Nikhil R. Devanur</a>, <a href="../../indices/a-tree/k/Kannan:Ravi.html">Ravi Kannan</a>: <br><b>Market Equilibria in Polynomial Time for Fixed Number of Goods or Agents. </b>45-53<br><a href="http://dx.doi.org/10.1109/FOCS.2008.30"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DevanurK08">BibTeX</a></font> <li><a name="RazborovS08" href="../../indices/a-tree/r/Razborov:Alexander_A=.html">Alexander A. Razborov</a>, <a href="../../indices/a-tree/s/Sherstov:Alexander_A=.html">Alexander A. Sherstov</a>: <br><b>The Sign-Rank of AC^O. </b>57-66<br><a href="http://dx.doi.org/10.1109/FOCS.2008.19"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RazborovS08">BibTeX</a></font> <li><a name="AgrawalV08" href="../../indices/a-tree/a/Agrawal:Manindra.html">Manindra Agrawal</a>, <a href="../../indices/a-tree/v/Vinay:V=.html">V. Vinay</a>: <br><b>Arithmetic Circuits: A Chasm at Depth Four. </b>67-75<br><a href="http://dx.doi.org/10.1109/FOCS.2008.32"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AgrawalV08">BibTeX</a></font> <li><a name="ReingoldTTV08" 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/t/Tulsiani:Madhur.html">Madhur Tulsiani</a>, <a href="../../indices/a-tree/v/Vadhan:Salil_P=.html">Salil P. Vadhan</a>: <br><b>Dense Subsets of Pseudorandom Sets. </b>76-85<br><a href="http://dx.doi.org/10.1109/FOCS.2008.38"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ReingoldTTV08">BibTeX</a></font> <li><a name="Chow08" href="../../indices/a-tree/c/Chow:Timothy_Y=.html">Timothy Y. Chow</a>: <br><b>Almost-Natural Proofs. </b>86-91<br><a href="http://dx.doi.org/10.1109/FOCS.2008.16"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Chow08">BibTeX</a></font> <li><a name="ChanPR08" href="../../indices/a-tree/c/Chan:Timothy_M=.html">Timothy M. Chan</a>, <a href="../../indices/a-tree/p/Patrascu:Mihai.html">Mihai Patrascu</a>, <a href="../../indices/a-tree/r/Roditty:Liam.html">Liam Roditty</a>: <br><b>Dynamic Connectivity: Connecting to Networks and Geometry. </b>95-104<br><a href="http://dx.doi.org/10.1109/FOCS.2008.29"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChanPR08">BibTeX</a></font> <li><a name="ChuzhoyK08" 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>Algorithms for Single-Source Vertex Connectivity. </b>105-114<br><a href="http://dx.doi.org/10.1109/FOCS.2008.63"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChuzhoyK08">BibTeX</a></font> <li><a name="BorradaileKM08" href="../../indices/a-tree/b/Borradaile:Glencora.html">Glencora Borradaile</a>, <a href="../../indices/a-tree/k/Klein:Philip_N=.html">Philip N. Klein</a>, <a href="../../indices/a-tree/m/Mathieu:Claire.html">Claire Mathieu</a>: <br><b>A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest. </b>115-124<br><a href="http://dx.doi.org/10.1109/FOCS.2008.59"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BorradaileKM08">BibTeX</a></font> <li><a name="ChanFLY08" href="../../indices/a-tree/c/Chan:Yuk_Hei.html">Yuk Hei Chan</a>, <a href="../../indices/a-tree/f/Fung:Wai_Shing.html">Wai Shing Fung</a>, <a href="../../indices/a-tree/l/Lau:Lap_Chi.html">Lap Chi Lau</a>, <a href="../../indices/a-tree/y/Yung:Chun_Kong.html">Chun Kong Yung</a>: <br><b>Degree Bounded Network Design with Metric Costs. </b>125-134<br><a href="http://dx.doi.org/10.1109/FOCS.2008.28"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChanFLY08">BibTeX</a></font> <li><a name="Yuster08" href="../../indices/a-tree/y/Yuster:Raphael.html">Raphael Yuster</a>: <br><b>Matrix Sparsification for Rank and Determinant Computations via Nested Dissection. </b>137-145<br><a href="http://dx.doi.org/10.1109/FOCS.2008.14"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Yuster08">BibTeX</a></font> <li><a name="KedlayaU08" href="../../indices/a-tree/k/Kedlaya:Kiran_S=.html">Kiran S. Kedlaya</a>, <a href="../../indices/a-tree/u/Umans:Christopher.html">Christopher Umans</a>: <br><b>Fast Modular Composition in any Characteristic. </b>146-155<br><a href="http://dx.doi.org/10.1109/FOCS.2008.13"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KedlayaU08">BibTeX</a></font> <li><a name="Mossel08" href="../../indices/a-tree/m/Mossel:Elchanan.html">Elchanan Mossel</a>: <br><b>Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes. </b>156-165<br><a href="http://dx.doi.org/10.1109/FOCS.2008.44"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Mossel08">BibTeX</a></font> <li><a name="KaufmanL08" href="../../indices/a-tree/k/Kaufman:Tali.html">Tali Kaufman</a>, <a href="../../indices/a-tree/l/Lovett:Shachar.html">Shachar Lovett</a>: <br><b>Worst Case to Average Case Reductions for Polynomials. </b>166-175<br><a href="http://dx.doi.org/10.1109/FOCS.2008.17"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KaufmanL08">BibTeX</a></font> <li><a name="Ezra08" href="../../indices/a-tree/e/Ezra:Esther.html">Esther Ezra</a>: <br><b>On the Union of Cylinders in Three Dimensions. </b>179-188<br><a href="http://dx.doi.org/10.1109/FOCS.2008.25"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ezra08">BibTeX</a></font> <li><a name="KindlerORW08" 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>, <a href="../../indices/a-tree/r/Rao:Anup.html">Anup Rao</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>Spherical Cubes and Rounding in High Dimensions. </b>189-198<br><a href="http://dx.doi.org/10.1109/FOCS.2008.50"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KindlerORW08">BibTeX</a></font> <li><a name="IndykR08" href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>, <a href="../../indices/a-tree/r/Ruzic:Milan.html">Milan Ruzic</a>: <br><b>Near-Optimal Sparse Recovery in the L1 Norm. </b>199-207<br><a href="http://dx.doi.org/10.1109/FOCS.2008.82"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/IndykR08">BibTeX</a></font> <li><a name="ApplebaumBX08" href="../../indices/a-tree/a/Applebaum:Benny.html">Benny Applebaum</a>, <a href="../../indices/a-tree/b/Barak:Boaz.html">Boaz Barak</a>, <a href="../../indices/a-tree/x/Xiao:David.html">David Xiao</a>: <br><b>On Basing Lower-Bounds for Learning on Worst-Case Assumptions. </b>211-220<br><a href="http://dx.doi.org/10.1109/FOCS.2008.35"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ApplebaumBX08">BibTeX</a></font> <li><a name="Ben-OrH08" 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>The Bayesian Learner is Optimal for Noisy Binary Search (and Pretty Good for Quantum as Well). </b>221-230<br><a href="http://dx.doi.org/10.1109/FOCS.2008.58"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ben-OrH08">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>Hardness of Minimizing and Learning DNF Expressions. </b>231-240<br><a href="http://dx.doi.org/10.1109/FOCS.2008.37"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KhotS08">BibTeX</a></font> <li><a name="FriedgutKN08" href="../../indices/a-tree/f/Friedgut:Ehud.html">Ehud Friedgut</a>, <a href="../../indices/a-tree/k/Kalai:Gil.html">Gil Kalai</a>, <a href="../../indices/a-tree/n/Nisan:Noam.html">Noam Nisan</a>: <br><b>Elections Can be Manipulated Often. </b>243-249<br><a href="http://dx.doi.org/10.1109/FOCS.2008.87"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FriedgutKN08">BibTeX</a></font> <li><a name="PapadimitriouSS08" href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>, <a href="../../indices/a-tree/s/Schapira:Michael.html">Michael Schapira</a>, <a href="../../indices/a-tree/s/Singer:Yaron.html">Yaron Singer</a>: <br><b>On the Hardness of Being Truthful. </b>250-259<br><a href="http://dx.doi.org/10.1109/FOCS.2008.54"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PapadimitriouSS08">BibTeX</a></font> <li><a name="DobzinskiLN08" href="../../indices/a-tree/d/Dobzinski:Shahar.html">Shahar Dobzinski</a>, <a href="../../indices/a-tree/l/Lavi:Ron.html">Ron Lavi</a>, <a href="../../indices/a-tree/n/Nisan:Noam.html">Noam Nisan</a>: <br><b>Multi-unit Auctions with Budget Limits. </b>260-269<br><a href="http://dx.doi.org/10.1109/FOCS.2008.39"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DobzinskiLN08">BibTeX</a></font> <li><a name="RazY08" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>, <a href="../../indices/a-tree/y/Yehudayoff:Amir.html">Amir Yehudayoff</a>: <br><b>Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors. </b>273-282<br><a href="http://dx.doi.org/10.1109/FOCS.2008.22"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RazY08">BibTeX</a></font> <li><a name="BonehPRVW08" href="../../indices/a-tree/b/Boneh:Dan.html">Dan Boneh</a>, <a href="../../indices/a-tree/p/Papakonstantinou:Periklis_A=.html">Periklis A. Papakonstantinou</a>, <a href="../../indices/a-tree/r/Rackoff:Charles.html">Charles Rackoff</a>, <a href="../../indices/a-tree/v/Vahlis:Yevgeniy.html">Yevgeniy Vahlis</a>, <a href="../../indices/a-tree/w/Waters:Brent.html">Brent Waters</a>: <br><b>On the Impossibility of Basing Identity Based Encryption on Trapdoor Permutations. </b>283-292<br><a href="http://dx.doi.org/10.1109/FOCS.2008.67"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BonehPRVW08">BibTeX</a></font> <li><a name="DziembowskiP08" href="../../indices/a-tree/d/Dziembowski:Stefan.html">Stefan Dziembowski</a>, <a href="../../indices/a-tree/p/Pietrzak:Krzysztof.html">Krzysztof Pietrzak</a>: <br><b>Leakage-Resilient Cryptography. </b>293-302<br><a href="http://dx.doi.org/10.1109/FOCS.2008.56"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DziembowskiP08">BibTeX</a></font> <li><a name="Patrascu08" href="../../indices/a-tree/p/Patrascu:Mihai.html">Mihai Patrascu</a>: <br><b>Succincter. </b>305-313<br><a href="http://dx.doi.org/10.1109/FOCS.2008.83"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Patrascu08">BibTeX</a></font> <li><a name="MoshkovitzR08" 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>Two Query PCP with Sub-Constant Error. </b>314-323<br><a href="http://dx.doi.org/10.1109/FOCS.2008.60"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MoshkovitzR08">BibTeX</a></font> <li><a name="NguyenO08" href="../../indices/a-tree/n/Nguyen:Huy_N=.html">Huy N. Nguyen</a>, <a href="../../indices/a-tree/o/Onak:Krzysztof.html">Krzysztof Onak</a>: <br><b>Constant-Time Approximation Algorithms via Local Improvements. </b>327-336<br><a href="http://dx.doi.org/10.1109/FOCS.2008.81"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NguyenO08">BibTeX</a></font> <li><a name="MoitraL08" href="../../indices/a-tree/m/Moitra:Ankur.html">Ankur Moitra</a>, <a href="../../indices/a-tree/l/Leighton:Tom.html">Tom Leighton</a>: <br><b>Some Results on Greedy Embeddings in Metric Spaces. </b>337-346<br><a href="http://dx.doi.org/10.1109/FOCS.2008.18"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MoitraL08">BibTeX</a></font> <li><a name="GrandoniGLMSS08" href="../../indices/a-tree/g/Grandoni:Fabrizio.html">Fabrizio Grandoni</a>, <a href="../../indices/a-tree/g/Gupta:Anupam.html">Anupam Gupta</a>, <a href="../../indices/a-tree/l/Leonardi:Stefano.html">Stefano Leonardi</a>, <a href="../../indices/a-tree/m/Miettinen:Pauli.html">Pauli Miettinen</a>, <a href="../../indices/a-tree/s/Sankowski:Piotr.html">Piotr Sankowski</a>, <a href="../../indices/a-tree/s/Singh:Mohit.html">Mohit Singh</a>: <br><b>Set Covering with our Eyes Closed. </b>347-356<br><a href="http://dx.doi.org/10.1109/FOCS.2008.31"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GrandoniGLMSS08">BibTeX</a></font> <li><a name="FriggstadS08" href="../../indices/a-tree/f/Friggstad:Zachary.html">Zachary Friggstad</a>, <a href="../../indices/a-tree/s/Salavatipour:Mohammad_R=.html">Mohammad R. Salavatipour</a>: <br><b>Minimizing Movement in Mobile Facility Location Problems. </b>357-366<br><a href="http://dx.doi.org/10.1109/FOCS.2008.12"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FriggstadS08">BibTeX</a></font> <li><a name="Raz08" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>: <br><b>A Counterexample to Strong Parallel Repetition. </b>369-373<br><a href="http://dx.doi.org/10.1109/FOCS.2008.49"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Raz08">BibTeX</a></font> <li><a name="BarakHHRRS08" href="../../indices/a-tree/b/Barak:Boaz.html">Boaz Barak</a>, <a href="../../indices/a-tree/h/Hardt:Moritz.html">Moritz Hardt</a>, <a href="../../indices/a-tree/h/Haviv:Ishay.html">Ishay Haviv</a>, <a href="../../indices/a-tree/r/Rao:Anup.html">Anup Rao</a>, <a href="../../indices/a-tree/r/Regev:Oded.html">Oded Regev</a>, <a href="../../indices/a-tree/s/Steurer:David.html">David Steurer</a>: <br><b>Rounding Parallel Repetitions of Unique Games. </b>374-383<br><a href="http://dx.doi.org/10.1109/FOCS.2008.55"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BarakHHRRS08">BibTeX</a></font> <li><a name="Sherstov08" href="../../indices/a-tree/s/Sherstov:Alexander_A=.html">Alexander A. Sherstov</a>: <br><b>The Unbounded-Error Communication Complexity of Symmetric Functions. </b>384-393<br><a href="http://dx.doi.org/10.1109/FOCS.2008.20"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Sherstov08">BibTeX</a></font> <li><a name="DuttaR08" href="../../indices/a-tree/d/Dutta:Chinmoy.html">Chinmoy Dutta</a>, <a href="../../indices/a-tree/r/Radhakrishnan:Jaikumar.html">Jaikumar Radhakrishnan</a>: <br><b>Lower Bounds for Noisy Wireless Networks using Sampling Algorithms. </b>394-402<br><a href="http://dx.doi.org/10.1109/FOCS.2008.72"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DuttaR08">BibTeX</a></font> <li><a name="MatousekS08" href="../../indices/a-tree/m/Matousek:Jir=iacute=.html">Jirí Matousek</a>, <a href="../../indices/a-tree/s/Sidiropoulos:Anastasios.html">Anastasios Sidiropoulos</a>: <br><b>Inapproximability for Metric Embeddings into R^d. </b>405-413<br><a href="http://dx.doi.org/10.1109/FOCS.2008.21"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MatousekS08">BibTeX</a></font> <li><a name="PanigrahyTW08" href="../../indices/a-tree/p/Panigrahy:Rina.html">Rina Panigrahy</a>, <a href="../../indices/a-tree/t/Talwar:Kunal.html">Kunal Talwar</a>, <a href="../../indices/a-tree/w/Wieder:Udi.html">Udi Wieder</a>: <br><b>A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match. </b>414-423<br><a href="http://dx.doi.org/10.1109/FOCS.2008.68"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PanigrahyTW08">BibTeX</a></font> <li><a name="AndoniCP08" href="../../indices/a-tree/a/Andoni:Alexandr.html">Alexandr Andoni</a>, <a href="../../indices/a-tree/c/Croitoru:Dorian.html">Dorian Croitoru</a>, <a href="../../indices/a-tree/p/Patrascu:Mihai.html">Mihai Patrascu</a>: <br><b>Hardness of Nearest Neighbor under L-infinity. </b>424-433<br><a href="http://dx.doi.org/10.1109/FOCS.2008.89"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AndoniCP08">BibTeX</a></font> <li><a name="Patrascu08a" href="../../indices/a-tree/p/Patrascu:Mihai.html">Mihai Patrascu</a>: <br><b>(Data) STRUCTURES. </b>434-443<br><a href="http://dx.doi.org/10.1109/FOCS.2008.69"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Patrascu08a">BibTeX</a></font> <li><a name="KempeKMTV08" href="../../indices/a-tree/k/Kempe:Julia.html">Julia Kempe</a>, <a href="../../indices/a-tree/k/Kobayashi:Hirotada.html">Hirotada Kobayashi</a>, <a href="../../indices/a-tree/m/Matsumoto:Keiji.html">Keiji Matsumoto</a>, <a href="../../indices/a-tree/t/Toner:Ben.html">Ben Toner</a>, <a href="../../indices/a-tree/v/Vidick:Thomas.html">Thomas Vidick</a>: <br><b>Entangled Games are Hard to Approximate. </b>447-456<br><a href="http://dx.doi.org/10.1109/FOCS.2008.8"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KempeKMTV08">BibTeX</a></font> <li><a name="KempeRT08" 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/t/Toner:Ben.html">Ben Toner</a>: <br><b>Unique Games with Entangled Provers are Easy. </b>457-466<br><a href="http://dx.doi.org/10.1109/FOCS.2008.9"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KempeRT08">BibTeX</a></font> <li><a name="Ben-OrHP08" 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>, <a href="../../indices/a-tree/p/Pilpel:Haran.html">Haran Pilpel</a>: <br><b>Quantum Multi Prover Interactive Proofs with Communicating Provers. </b>467-476<br><a href="http://dx.doi.org/10.1109/FOCS.2008.57"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ben-OrHP08">BibTeX</a></font> <li><a name="Ben-AroyaRW08" href="../../indices/a-tree/b/Ben=Aroya:Avraham.html">Avraham Ben-Aroya</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>A Hypercontractive Inequality for Matrix-Valued Functions with Applications to Quantum Computing and LDCs. </b>477-486<br><a href="http://dx.doi.org/10.1109/FOCS.2008.45"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ben-AroyaRW08">BibTeX</a></font> <li><a name="HarveyNO08" href="../../indices/a-tree/h/Harvey:Nicholas_J=_A=.html">Nicholas J. A. Harvey</a>, <a href="../../indices/a-tree/n/Nelson:Jelani.html">Jelani Nelson</a>, <a href="../../indices/a-tree/o/Onak:Krzysztof.html">Krzysztof Onak</a>: <br><b>Sketching and Streaming Entropy via Approximation Theory. </b>489-498<br><a href="http://dx.doi.org/10.1109/FOCS.2008.76"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HarveyNO08">BibTeX</a></font> <li><a name="BeameH08" href="../../indices/a-tree/b/Beame:Paul.html">Paul Beame</a>, <a href="../../indices/a-tree/h/Huynh=Ngoc:Dang=Trinh.html">Dang-Trinh Huynh-Ngoc</a>: <br><b>On the Value of Multiple Read/Write Streams for Approximating Frequency Moments. </b>499-508<br><a href="http://dx.doi.org/10.1109/FOCS.2008.52"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BeameH08">BibTeX</a></font> <li><a name="LenzenLW08" href="../../indices/a-tree/l/Lenzen:Christoph.html">Christoph Lenzen</a>, <a href="../../indices/a-tree/l/Locher:Thomas.html">Thomas Locher</a>, <a href="../../indices/a-tree/w/Wattenhofer:Roger.html">Roger Wattenhofer</a>: <br><b>Clock Synchronization with Bounded Global and Local Skew. </b>509-518<br><a href="http://dx.doi.org/10.1109/FOCS.2008.10"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LenzenLW08">BibTeX</a></font> <li><a name="DinitzES08" href="../../indices/a-tree/d/Dinitz:Yefim.html">Yefim Dinitz</a>, <a href="../../indices/a-tree/e/Elkin:Michael.html">Michael Elkin</a>, <a href="../../indices/a-tree/s/Solomon:Shay.html">Shay Solomon</a>: <br><b>Shallow-Low-Light Trees, and Tight Lower Bounds for Euclidean Spanners. </b>519-528<br><a href="http://dx.doi.org/10.1109/FOCS.2008.24"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DinitzES08">BibTeX</a></font> <li><a name="KasiviswanathanLNRS08" href="../../indices/a-tree/k/Kasiviswanathan:Shiva_Prasad.html">Shiva Prasad Kasiviswanathan</a>, <a href="../../indices/a-tree/l/Lee:Homin_K=.html">Homin K. Lee</a>, <a href="../../indices/a-tree/n/Nissim:Kobbi.html">Kobbi Nissim</a>, <a href="../../indices/a-tree/r/Raskhodnikova:Sofya.html">Sofya Raskhodnikova</a>, <a href="../../indices/a-tree/s/Smith:Adam.html">Adam Smith</a>: <br><b>What Can We Learn Privately? </b>531-540<br><a href="http://dx.doi.org/10.1109/FOCS.2008.27"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KasiviswanathanLNRS08">BibTeX</a></font> <li><a name="KlivansOS08" href="../../indices/a-tree/k/Klivans:Adam_R=.html">Adam R. Klivans</a>, <a 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>Learning Geometric Concepts via Gaussian Surface Area. </b>541-550<br><a href="http://dx.doi.org/10.1109/FOCS.2008.64"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KlivansOS08">BibTeX</a></font> <li><a name="BrubakerV08" href="../../indices/a-tree/b/Brubaker:S=_Charles.html">S. Charles Brubaker</a>, <a href="../../indices/a-tree/v/Vempala:Santosh.html">Santosh Vempala</a>: <br><b>Isotropic PCA and Affine-Invariant Clustering. </b>551-560<br><a href="http://dx.doi.org/10.1109/FOCS.2008.48"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BrubakerV08">BibTeX</a></font> <li><a name="KhotN08" href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>, <a href="../../indices/a-tree/n/Naor:Assaf.html">Assaf Naor</a>: <br><b>Approximate Kernel Clustering. </b>561-570<br><a href="http://dx.doi.org/10.1109/FOCS.2008.33"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KhotN08">BibTeX</a></font> <li><a name="GuruswamiMR08" href="../../indices/a-tree/g/Guruswami:Venkatesan.html">Venkatesan Guruswami</a>, <a href="../../indices/a-tree/m/Manokaran:Rajsekar.html">Rajsekar Manokaran</a>, <a href="../../indices/a-tree/r/Raghavendra:Prasad.html">Prasad Raghavendra</a>: <br><b>Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph. </b>573-582<br><a href="http://dx.doi.org/10.1109/FOCS.2008.51"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GuruswamiMR08">BibTeX</a></font> <li><a name="MastrolilliS08" href="../../indices/a-tree/m/Mastrolilli:Monaldo.html">Monaldo Mastrolilli</a>, <a href="../../indices/a-tree/s/Svensson:Ola.html">Ola Svensson</a>: <br><b>(Acyclic) JobShops are Hard to Approximate. </b>583-592<br><a href="http://dx.doi.org/10.1109/FOCS.2008.36"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MastrolilliS08">BibTeX</a></font> <li><a name="Schoenebeck08" href="../../indices/a-tree/s/Schoenebeck:Grant.html">Grant Schoenebeck</a>: <br><b>Linear Level Lasserre Lower Bounds for Certain k-CSPs. </b>593-602<br><a href="http://dx.doi.org/10.1109/FOCS.2008.74"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Schoenebeck08">BibTeX</a></font> <li><a name="EnglertOW08" href="../../indices/a-tree/e/Englert:Matthias.html">Matthias Englert</a>, <a href="../../indices/a-tree/=/=Ouml=zmen:Deniz.html">Deniz Özmen</a>, <a href="../../indices/a-tree/w/Westermann:Matthias.html">Matthias Westermann</a>: <br><b>The Power of Reordering for Online Minimum Makespan Scheduling. </b>603-612<br><a href="http://dx.doi.org/10.1109/FOCS.2008.46"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/EnglertOW08">BibTeX</a></font> <li><a name="DinurG08" href="../../indices/a-tree/d/Dinur:Irit.html">Irit Dinur</a>, <a href="../../indices/a-tree/g/Goldenberg:Elazar.html">Elazar Goldenberg</a>: <br><b>Locally Testing Direct Product in the Low Error Range. </b>613-622<br><a href="http://dx.doi.org/10.1109/FOCS.2008.26"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DinurG08">BibTeX</a></font> <li><a name="DvirW08" href="../../indices/a-tree/d/Dvir:Zeev.html">Zeev Dvir</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>Kakeya Sets, New Mergers and Old Extractors. </b>625-633<br><a href="http://dx.doi.org/10.1109/FOCS.2008.23"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DvirW08">BibTeX</a></font> <li><a name="ChanM08" href="../../indices/a-tree/c/Chan:Siu_On.html">Siu On Chan</a>, <a href="../../indices/a-tree/m/Molloy:Michael.html">Michael Molloy</a>: <br><b>A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems. </b>634-643<br><a href="http://dx.doi.org/10.1109/FOCS.2008.70"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChanM08">BibTeX</a></font> <li><a name="CaiLX08" href="../../indices/a-tree/c/Cai:Jin=yi.html">Jin-yi Cai</a>, <a href="../../indices/a-tree/l/Lu:Pinyan.html">Pinyan Lu</a>, <a href="../../indices/a-tree/x/Xia:Mingji.html">Mingji Xia</a>: <br><b>Holographic Algorithms by Fibonacci Gates and Holographic Reductions for Hardness. </b>644-653<br><a href="http://dx.doi.org/10.1109/FOCS.2008.34"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CaiLX08">BibTeX</a></font> <li><a name="KalaiLRZ08" href="../../indices/a-tree/k/Kalai:Yael_Tauman.html">Yael Tauman Kalai</a>, <a href="../../indices/a-tree/l/Li:Xin.html">Xin Li</a>, <a href="../../indices/a-tree/r/Rao:Anup.html">Anup Rao</a>, <a href="../../indices/a-tree/z/Zuckerman:David.html">David Zuckerman</a>: <br><b>Network Extractor Protocols. </b>654-663<br><a href="http://dx.doi.org/10.1109/FOCS.2008.73"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KalaiLRZ08">BibTeX</a></font> <li><a name="BabaiC08" href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>, <a href="../../indices/a-tree/c/Codenotti:Paolo.html">Paolo Codenotti</a>: <br><b>Isomorhism of Hypergraphs of Low Rank in Moderately Exponential Time. </b>667-676<br><a href="http://dx.doi.org/10.1109/FOCS.2008.80"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BabaiC08">BibTeX</a></font> <li><a name="BjorklundHKK08" href="../../indices/a-tree/b/Bj=ouml=rklund:Andreas.html">Andreas Björklund</a>, <a href="../../indices/a-tree/h/Husfeldt:Thore.html">Thore Husfeldt</a>, <a href="../../indices/a-tree/k/Kaski:Petteri.html">Petteri Kaski</a>, <a href="../../indices/a-tree/k/Koivisto:Mikko.html">Mikko Koivisto</a>: <br><b>Computing the Tutte Polynomial in Vertex-Exponential Time. </b>677-686<br><a href="http://dx.doi.org/10.1109/FOCS.2008.40"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BjorklundHKK08">BibTeX</a></font> <li><a name="ChakrabartyG08" href="../../indices/a-tree/c/Chakrabarty:Deeparnab.html">Deeparnab Chakrabarty</a>, <a href="../../indices/a-tree/g/Goel:Gagan.html">Gagan Goel</a>: <br><b>On the Approximability of Budgeted Allocations and Improved Lower Bounds for Submodular Welfare Maximization and GAP. </b>687-696<br><a href="http://dx.doi.org/10.1109/FOCS.2008.47"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChakrabartyG08">BibTeX</a></font> <li><a name="SvitkinaF08" href="../../indices/a-tree/s/Svitkina:Zoya.html">Zoya Svitkina</a>, <a href="../../indices/a-tree/f/Fleischer:Lisa.html">Lisa Fleischer</a>: <br><b>Submodular Approximation: Sampling-based Algorithms and Lower Bounds. </b>697-706<br><a href="http://dx.doi.org/10.1109/FOCS.2008.66"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SvitkinaF08">BibTeX</a></font> <li><a name="Ben-SassonN08" href="../../indices/a-tree/b/Ben=Sasson:Eli.html">Eli Ben-Sasson</a>, <a href="../../indices/a-tree/n/Nordstr=ouml=m:Jakob.html">Jakob Nordström</a>: <br><b>Short Proofs May Be Spacious: An Optimal Separation of Space and Length in Resolution. </b>709-718<br><a href="http://dx.doi.org/10.1109/FOCS.2008.42"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ben-SassonN08">BibTeX</a></font> <li><a name="KalePS08" href="../../indices/a-tree/k/Kale:Satyen.html">Satyen Kale</a>, <a href="../../indices/a-tree/p/Peres:Yuval.html">Yuval Peres</a>, <a href="../../indices/a-tree/s/Seshadhri:C=.html">C. Seshadhri</a>: <br><b>Noise Tolerance of Expanders and Sublinear Expander Reconstruction. </b>719-728<br><a href="http://dx.doi.org/10.1109/FOCS.2008.65"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KalePS08">BibTeX</a></font> <li><a name="Roch08" href="../../indices/a-tree/r/Roch:S=eacute=bastien.html">Sébastien Roch</a>: <br><b>Sequence Length Requirement of Distance-Based Phylogeny Reconstruction: Breaking the Polynomial Barrier. </b>729-738<br><a href="http://dx.doi.org/10.1109/FOCS.2008.77"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Roch08">BibTeX</a></font> <li><a name="AtseriasGM08" href="../../indices/a-tree/a/Atserias:Albert.html">Albert Atserias</a>, <a href="../../indices/a-tree/g/Grohe:Martin.html">Martin Grohe</a>, <a href="../../indices/a-tree/m/Marx:D=aacute=niel.html">Dániel Marx</a>: <br><b>Size Bounds and Query Plans for Relational Joins. </b>739-748<br><a href="http://dx.doi.org/10.1109/FOCS.2008.43"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AtseriasGM08">BibTeX</a></font> <li><a name="BiswalLR08" href="../../indices/a-tree/b/Biswal:Punyashloka.html">Punyashloka Biswal</a>, <a href="../../indices/a-tree/l/Lee:James_R=.html">James R. Lee</a>, <a href="../../indices/a-tree/r/Rao:Satish.html">Satish Rao</a>: <br><b>Eigenvalue Bounds, Spectral Partitioning, and Metrical Deformations via Flows. </b>751-760<br><a href="http://dx.doi.org/10.1109/FOCS.2008.78"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BiswalLR08">BibTeX</a></font> <li><a name="ChakrabartiJLV08" href="../../indices/a-tree/c/Chakrabarti:Amit.html">Amit Chakrabarti</a>, <a href="../../indices/a-tree/j/Jaffe:Alexander.html">Alexander Jaffe</a>, <a href="../../indices/a-tree/l/Lee:James_R=.html">James R. Lee</a>, <a href="../../indices/a-tree/v/Vincent:Justin.html">Justin Vincent</a>: <br><b>Embeddings of Topological Graphs: Lossy Invariants, Linearization, and 2-Sums. </b>761-770<br><a href="http://dx.doi.org/10.1109/FOCS.2008.79"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChakrabartiJLV08">BibTeX</a></font> <li><a name="KawarabayashiMR08" 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>, <a href="../../indices/a-tree/r/Reed:Bruce_A=.html">Bruce A. Reed</a>: <br><b>A Simpler Linear Time Algorithm for Embedding Graphs into an Arbitrary Surface and the Genus of Graphs of Bounded Tree-Width. </b>771-780<br><a href="http://dx.doi.org/10.1109/FOCS.2008.53"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KawarabayashiMR08">BibTeX</a></font> <li><a name="AbrahamBN08" 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>Nearly Tight Low Stretch Spanning Trees. </b>781-790<br><a href="http://dx.doi.org/10.1109/FOCS.2008.62"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AbrahamBN08">BibTeX</a></font> <li><a name="AchlioptasC08" href="../../indices/a-tree/a/Achlioptas:Dimitris.html">Dimitris Achlioptas</a>, <a href="../../indices/a-tree/c/Coja=Oghlan:Amin.html">Amin Coja-Oghlan</a>: <br><b>Algorithmic Barriers from Phase Transitions. </b>793-802<br><a href="http://dx.doi.org/10.1109/FOCS.2008.11"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AchlioptasC08">BibTeX</a></font> <li><a name="BhamidiBS08" href="../../indices/a-tree/b/Bhamidi:Shankar.html">Shankar Bhamidi</a>, <a href="../../indices/a-tree/b/Bresler:Guy.html">Guy Bresler</a>, <a href="../../indices/a-tree/s/Sly:Allan.html">Allan Sly</a>: <br><b>Mixing Time of Exponential Random Graphs. </b>803-812<br><a href="http://dx.doi.org/10.1109/FOCS.2008.75"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BhamidiBS08">BibTeX</a></font> <li><a name="AlonN08" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/n/Nussboim:Asaf.html">Asaf Nussboim</a>: <br><b>k-Wise Independent Random Graphs. </b>813-822<br><a href="http://dx.doi.org/10.1109/FOCS.2008.61"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonN08">BibTeX</a></font> <li><a name="AlonLSWH08" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/l/Lubetzky:Eyal.html">Eyal Lubetzky</a>, <a href="../../indices/a-tree/s/Stav:Uri.html">Uri Stav</a>, <a href="../../indices/a-tree/w/Weinstein:Amit.html">Amit Weinstein</a>, <a href="../../indices/a-tree/h/Hassidim:Avinatan.html">Avinatan Hassidim</a>: <br><b>Broadcasting with Side Information. </b>823-832<br><a href="http://dx.doi.org/10.1109/FOCS.2008.41"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonLSWH08">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:12:28 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
