focs2005.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>FOCS 2005</title><link href="../../../dblp.css" rel="stylesheet" type="text/css" /></head><body> <table width="100%"><tr><td align="left"><a href="../../index.html"><img alt="dblp.uni-trier.de" src="../../Logo.gif" border=0 height=60 width=170></a></td> <td align="right"><a href="http://www.uni-trier.de"><img alt="www.uni-trier.de" src="../../logo_universitaet-trier.gif" border=0 height=48 width=215></a></td></tr></table> <h1>46. <a href="index.html">FOCS</a> 2005: Pittsburgh, PA, USA</h1> 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings. IEEE Computer Society 2005, ISBN 0-7695-2468-0 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/2005">BibTeX</a></font> <h2>Cover</h2> <ul> <li><b>FOCS 2005 - Title Page. </b><br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.3"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/X05">BibTeX</a></font> <li><b>FOCS 2005 - Copyright. </b><br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.4"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/X105">BibTeX</a></font> </ul> <h2>Introduction</h2> <ul> <li><b>Foreword. </b><br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.37"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/X05a">BibTeX</a></font> <li><b>Committees. </b><br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.26"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/X05b">BibTeX</a></font> <li><b>Best Paper Awards. </b><br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.24"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/X05c">BibTeX</a></font> <li><b>Machtey Award. </b><br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.49"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/X05d">BibTeX</a></font> <li><b>Knuth Prize. </b><br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.45"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/X05e">BibTeX</a></font> <li><b>Reviewers. </b><br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.65"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/X05f">BibTeX</a></font> <li><b>Corporate Sponsors. </b><br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.28"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/X05g">BibTeX</a></font> </ul> <h2>Tutorial 1</h2> <ul> <li><a name="Khot05" href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>: <br><b>On the Unique Games Conjecture. </b>3<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.61"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Khot05">BibTeX</a></font> </ul> <h2>Tutorial 2</h2> <ul> <li><a name="Chazelle05" href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>: <br><b>Algorithmic Techniques and Tools from Computational Geometry. </b>7<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.15"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Chazelle05">BibTeX</a></font> </ul> <h2>Session 1</h2> <ul> <li><a name="KalaiKMS05" 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>, <a href="../../indices/a-tree/m/Mansour:Yishay.html">Yishay Mansour</a>, <a href="../../indices/a-tree/s/Servedio:Rocco_A=.html">Rocco A. Servedio</a>: <br><b>Agnostically Learning Halfspaces. </b>11-20<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.13"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KalaiKMS05">BibTeX</a></font> <li><a name="MosselOO05" href="../../indices/a-tree/m/Mossel:Elchanan.html">Elchanan Mossel</a>, <a href="../../indices/a-tree/o/O=Donnell:Ryan.html">Ryan O'Donnell</a>, <a href="../../indices/a-tree/o/Oleszkiewicz:Krzysztof.html">Krzysztof Oleszkiewicz</a>: <br><b>Noise stability of functions with low in.uences invariance and optimality. </b>21-30<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.53"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MosselOO05">BibTeX</a></font> <li><a name="ODonnellSS05" href="../../indices/a-tree/o/O=Donnell:Ryan.html">Ryan O'Donnell</a>, <a href="../../indices/a-tree/s/Saks:Michael_E=.html">Michael E. Saks</a>, <a href="../../indices/a-tree/s/Schramm:Oded.html">Oded Schramm</a>, <a href="../../indices/a-tree/s/Servedio:Rocco_A=.html">Rocco A. Servedio</a>: <br><b>Every decision tree has an in.uential variable. </b>31-39<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.34"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ODonnellSS05">BibTeX</a></font> <li><a name="GoyalKS05" href="../../indices/a-tree/g/Goyal:Navin.html">Navin Goyal</a>, <a href="../../indices/a-tree/k/Kindler:Guy.html">Guy Kindler</a>, <a href="../../indices/a-tree/s/Saks:Michael_E=.html">Michael E. Saks</a>: <br><b>Lower Bounds for the Noisy Broadcast Problem. </b>40-52<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.48"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoyalKS05">BibTeX</a></font> </ul> <h2>Session 2: Best Paper Award</h2> <ul> <li><a name="KhotV05" href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>, <a href="../../indices/a-tree/v/Vishnoi:Nisheeth_K=.html">Nisheeth K. Vishnoi</a>: <br><b>The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into l<sub>1</sub>. </b>53-62<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.74"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KhotV05">BibTeX</a></font> <li><a name="Marx05" href="../../indices/a-tree/m/Marx:D=aacute=niel.html">Dániel Marx</a>: <br><b>The Closest Substring problem with small distances. </b>63-72<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.70"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Marx05">BibTeX</a></font> <li><a name="AilonC05" href="../../indices/a-tree/a/Ailon:Nir.html">Nir Ailon</a>, <a href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>: <br><b>Fitting tree metrics: Hierarchical clustering and Phylogeny. </b>73-82<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.36"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AilonC05">BibTeX</a></font> <li><a name="AbrahamBCDGKNS05" 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/c/Chan:Hubert_T==H=.html">Hubert T.-H. Chan</a>, <a href="../../indices/a-tree/d/Dhamdhere:Kedar.html">Kedar Dhamdhere</a>, <a href="../../indices/a-tree/g/Gupta:Anupam.html">Anupam Gupta</a>, <a href="../../indices/a-tree/k/Kleinberg:Jon_M=.html">Jon M. Kleinberg</a>, <a href="../../indices/a-tree/n/Neiman:Ofer.html">Ofer Neiman</a>, <a href="../../indices/a-tree/s/Slivkins:Aleksandrs.html">Aleksandrs Slivkins</a>: <br><b>Metric Embeddings with Relaxed Guarantees. </b>83-100<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.51"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AbrahamBCDGKNS05">BibTeX</a></font> <li><a name="KhotN05" 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>Nonembeddability theorems via Fourier analysis. </b>101-112<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.54"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KhotN05">BibTeX</a></font> </ul> <h2>Session 3 Machtey Award</h2> <ul> <li><a name="AbbottKV05" href="../../indices/a-tree/a/Abbott:Timothy_G=.html">Timothy G. Abbott</a>, <a href="../../indices/a-tree/k/Kane:Daniel.html">Daniel Kane</a>, <a href="../../indices/a-tree/v/Valiant:Paul.html">Paul Valiant</a>: <br><b>On the Complexity of Two-PlayerWin-Lose Games. </b>113-122<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.59"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AbbottKV05">BibTeX</a></font> <li><a name="BaranyVV05" href="../../indices/a-tree/b/B=aacute=r=aacute=ny:Imre.html">Imre Bárány</a>, <a href="../../indices/a-tree/v/Vempala:Santosh.html">Santosh Vempala</a>, <a href="../../indices/a-tree/v/Vetta:Adrian.html">Adrian Vetta</a>: <br><b>Nash Equilibria in Random Games. </b>123-131<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.52"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BaranyVV05">BibTeX</a></font> <li><a name="KleinbergR05" href="../../indices/a-tree/k/Kleinberg:Jon_M=.html">Jon M. Kleinberg</a>, <a href="../../indices/a-tree/r/Raghavan:Prabhakar.html">Prabhakar Raghavan</a>: <br><b>Query Incentive Networks. </b>132-141<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.63"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KleinbergR05">BibTeX</a></font> <li><a name="GoemansMV05" href="../../indices/a-tree/g/Goemans:Michel_X=.html">Michel X. Goemans</a>, <a href="../../indices/a-tree/m/Mirrokni:Vahab_S=.html">Vahab S. Mirrokni</a>, <a href="../../indices/a-tree/v/Vetta:Adrian.html">Adrian Vetta</a>: <br><b>Sink Equilibria and Convergence. </b>142-154<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.68"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoemansMV05">BibTeX</a></font> </ul> <h2>Session 4 Machtey Award Paper</h2> <ul> <li><a name="Braverman05" href="../../indices/a-tree/b/Braverman:Mark.html">Mark Braverman</a>: <br><b>On the Complexity of Real Functions. </b>155-164<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.58"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Braverman05">BibTeX</a></font> <li><a name="FichHS05" href="../../indices/a-tree/f/Fich:Faith_Ellen.html">Faith Ellen Fich</a>, <a href="../../indices/a-tree/h/Hendler:Danny.html">Danny Hendler</a>, <a href="../../indices/a-tree/s/Shavit:Nir.html">Nir Shavit</a>: <br><b>Linear Lower Bounds on Real-World Implementations of Concurrent Objects. </b>165-173<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.47"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FichHS05">BibTeX</a></font> <li><a name="Pettie05" href="../../indices/a-tree/p/Pettie:Seth.html">Seth Pettie</a>: <br><b>Towards a Final Analysis of Pairing Heaps. </b>174-183<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.75"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Pettie05">BibTeX</a></font> <li><a name="FerraginaLMM05" href="../../indices/a-tree/f/Ferragina:Paolo.html">Paolo Ferragina</a>, <a href="../../indices/a-tree/l/Luccio:Fabrizio.html">Fabrizio Luccio</a>, <a href="../../indices/a-tree/m/Manzini:Giovanni.html">Giovanni Manzini</a>, <a href="../../indices/a-tree/m/Muthukrishnan:S=.html">S. Muthukrishnan</a>: <br><b>Structuring labeled trees for optimal succinctness, and beyond. </b>184-196<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.69"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FerraginaLMM05">BibTeX</a></font> </ul> <h2>Session 5</h2> <ul> <li><a name="Trevisan05" href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>: <br><b>Approximation Algorithms for Unique Games. </b>197-205<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.22"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Trevisan05">BibTeX</a></font> <li><a name="AroraBKSH05" href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>, <a href="../../indices/a-tree/b/Berger:Eli.html">Eli Berger</a>, <a href="../../indices/a-tree/h/Hazan:Elad.html">Elad Hazan</a>, <a href="../../indices/a-tree/k/Kindler:Guy.html">Guy Kindler</a>, <a href="../../indices/a-tree/s/Safra:Muli.html">Muli Safra</a>: <br><b>On Non-Approximability for Quadratic Programs. </b>206-215<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.57"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AroraBKSH05">BibTeX</a></font> <li><a name="AlekhnovichKKV05" href="../../indices/a-tree/a/Alekhnovich:Mikhail.html">Mikhail Alekhnovich</a>, <a href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>, <a href="../../indices/a-tree/k/Kindler:Guy.html">Guy Kindler</a>, <a href="../../indices/a-tree/v/Vishnoi:Nisheeth_K=.html">Nisheeth K. Vishnoi</a>: <br><b>Hardness of Approximating the Closest Vector Problem with Pre-Processing. </b>216-225<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.40"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlekhnovichKKV05">BibTeX</a></font> <li><a name="AndrewsCZ05" href="../../indices/a-tree/a/Andrews:Matthew.html">Matthew Andrews</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>, <a href="../../indices/a-tree/z/Zhang:Lisa.html">Lisa Zhang</a>: <br><b>Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. </b>226-244<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.41"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AndrewsCZ05">BibTeX</a></font> </ul> <h2>Session 6</h2> <ul> <li><a name="ChekuriP05" href="../../indices/a-tree/c/Chekuri:Chandra.html">Chandra Chekuri</a>, <a href="../../indices/a-tree/p/P=aacute=l:Martin.html">Martin Pál</a>: <br><b>A Recursive Greedy Algorithm for Walks in Directed Graphs. </b>245-253<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.9"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChekuriP05">BibTeX</a></font> <li><a name="KumarMPS05" href="../../indices/a-tree/k/Kumar:V=_S=_Anil.html">V. S. Anil Kumar</a>, <a href="../../indices/a-tree/m/Marathe:Madhav_V=.html">Madhav V. Marathe</a>, <a href="../../indices/a-tree/p/Parthasarathy_0002:Srinivasan.html">Srinivasan Parthasarathy</a>, <a href="../../indices/a-tree/s/Srinivasan:Aravind.html">Aravind Srinivasan</a>: <br><b>Approximation Algorithms for Scheduling on Multiple Machines. </b>254-263<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.21"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KumarMPS05">BibTeX</a></font> <li><a name="MehtaSVV05" href="../../indices/a-tree/m/Mehta:Aranyak.html">Aranyak Mehta</a>, <a href="../../indices/a-tree/s/Saberi:Amin.html">Amin Saberi</a>, <a href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>, <a href="../../indices/a-tree/v/Vazirani:Vijay_V=.html">Vijay V. Vazirani</a>: <br><b>AdWords and Generalized On-line Matching. </b>264-273<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.12"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MehtaSVV05">BibTeX</a></font> <li><a name="Meyerson05" href="../../indices/a-tree/m/Meyerson:Adam.html">Adam Meyerson</a>: <br><b>The Parking Permit Problem. </b>274-284<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.72"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Meyerson05">BibTeX</a></font> </ul> <h2>Session 7 Best Paper Award</h2> <ul> <li><a name="ParvareshV05" href="../../indices/a-tree/p/Parvaresh:Farzad.html">Farzad Parvaresh</a>, <a href="../../indices/a-tree/v/Vardy:Alexander.html">Alexander Vardy</a>: <br><b>Correcting Errors Beyond the Guruswami-Sudan Radius in Polynomial Time. </b>285-294<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.29"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ParvareshV05">BibTeX</a></font> <li><a name="CandesRTV05" href="../../indices/a-tree/c/Cand=egrave=s:Emmanuel_J=.html">Emmanuel J. Candès</a>, <a href="../../indices/a-tree/r/Rudelson:Mark.html">Mark Rudelson</a>, <a href="../../indices/a-tree/t/Tao:Terence.html">Terence Tao</a>, <a href="../../indices/a-tree/v/Vershynin:Roman.html">Roman Vershynin</a>: <br><b>Error Correction via Linear Programming. </b>295-308<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.32"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CandesRTV05">BibTeX</a></font> <li><a name="OstrovskyRS05" href="../../indices/a-tree/o/Ostrovsky:Rafail.html">Rafail Ostrovsky</a>, <a href="../../indices/a-tree/r/Rabani:Yuval.html">Yuval Rabani</a>, <a href="../../indices/a-tree/s/Schulman:Leonard_J=.html">Leonard J. Schulman</a>: <br><b>Error-Correcting Codes for Automatic Control. </b>309-316<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.33"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/OstrovskyRS05">BibTeX</a></font> <li><a name="KaufmanL05" href="../../indices/a-tree/k/Kaufman:Tali.html">Tali Kaufman</a>, <a href="../../indices/a-tree/l/Litsyn:Simon.html">Simon Litsyn</a>: <br><b>Almost Orthogonal Linear Codes are Locally Testable. </b>317-326<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.16"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KaufmanL05">BibTeX</a></font> <li><a name="NavonS05" href="../../indices/a-tree/n/Navon:Michael.html">Michael Navon</a>, <a href="../../indices/a-tree/s/Samorodnitsky:Alex.html">Alex Samorodnitsky</a>: <br><b>On Delsarte's Linear Programming Bounds for Binary Codes. </b>327-338<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.55"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NavonS05">BibTeX</a></font> </ul> <h2>Session 8</h2> <ul> <li><a name="AroraHK05" href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>, <a href="../../indices/a-tree/h/Hazan:Elad.html">Elad Hazan</a>, <a href="../../indices/a-tree/k/Kale:Satyen.html">Satyen Kale</a>: <br><b>Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method. </b>339-348<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.35"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AroraHK05">BibTeX</a></font> <li><a name="DeshpandeS05" href="../../indices/a-tree/d/Deshpande:Amit.html">Amit Deshpande</a>, <a href="../../indices/a-tree/s/Spielman:Daniel_A=.html">Daniel A. Spielman</a>: <br><b>Improved Smoothed Analysis of the Shadow Vertex Simplex Method. </b>349-356<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.44"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DeshpandeS05">BibTeX</a></font> <li><a name="SwamyS05" href="../../indices/a-tree/s/Swamy:Chaitanya.html">Chaitanya Swamy</a>, <a href="../../indices/a-tree/s/Shmoys:David_B=.html">David B. Shmoys</a>: <br><b>Sampling-based Approximation Algorithms for Multi-stage Stochastic. </b>357-366<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.67"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SwamyS05">BibTeX</a></font> <li><a name="DhamdhereGRS05" href="../../indices/a-tree/d/Dhamdhere:Kedar.html">Kedar Dhamdhere</a>, <a href="../../indices/a-tree/g/Goyal:Vineet.html">Vineet Goyal</a>, <a href="../../indices/a-tree/r/Ravi:R=.html">R. Ravi</a>, <a href="../../indices/a-tree/s/Singh:Mohit.html">Mohit Singh</a>: <br><b>How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems. </b>367-378<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.42"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DhamdhereGRS05">BibTeX</a></font> </ul> <h2>Session 9</h2> <ul> <li><a name="CohnKSU05" href="../../indices/a-tree/c/Cohn:Henry.html">Henry Cohn</a>, <a href="../../indices/a-tree/k/Kleinberg:Robert_D=.html">Robert D. Kleinberg</a>, <a href="../../indices/a-tree/s/Szegedy:Bal=aacute=zs.html">Balázs Szegedy</a>, <a href="../../indices/a-tree/u/Umans:Christopher.html">Christopher Umans</a>: <br><b>Group-theoretic Algorithms for Matrix Multiplication. </b>379-388<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.39"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CohnKSU05">BibTeX</a></font> <li><a name="YusterZ05" href="../../indices/a-tree/y/Yuster:Raphael.html">Raphael Yuster</a>, <a href="../../indices/a-tree/z/Zwick:Uri.html">Uri Zwick</a>: <br><b>Answering distance queries in directed graphs using fast matrix multiplication. </b>389-396<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.20"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/YusterZ05">BibTeX</a></font> <li><a name="WigdersonX05" href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>, <a href="../../indices/a-tree/x/Xiao:David.html">David Xiao</a>: <br><b>A Randomness-Efficient Sampler for Matrix-valued Functions and Applications. </b>397-406<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.8"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/WigdersonX05">BibTeX</a></font> <li><a name="GabizonR05" href="../../indices/a-tree/g/Gabizon:Ariel.html">Ariel Gabizon</a>, <a href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>: <br><b>Deterministic Extractors for Affine Sources over Large Fields. </b>407-418<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.31"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GabizonR05">BibTeX</a></font> </ul> <h2>Session 10</h2> <ul> <li><a name="AlonSS05" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/s/Shapira:Asaf.html">Asaf Shapira</a>, <a href="../../indices/a-tree/s/Sudakov:Benny.html">Benny Sudakov</a>: <br><b>Additive Approximation for Edge-Deletion Problems. </b>419-428<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.11"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonSS05">BibTeX</a></font> <li><a name="AlonS05" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/s/Shapira:Asaf.html">Asaf Shapira</a>: <br><b>A Characterization of the (natural) Graph Properties Testable with One-Sided Error. </b>429-438<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.5"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonS05">BibTeX</a></font> <li><a name="HaxellNR05" href="../../indices/a-tree/h/Haxell:Penny_E=.html">Penny E. Haxell</a>, <a href="../../indices/a-tree/n/Nagle:Brendan.html">Brendan Nagle</a>, <a href="../../indices/a-tree/r/R=ouml=dl:Vojtech.html">Vojtech Rödl</a>: <br><b>An Algorithmic Version of the Hypergraph Regularity Method. </b>439-448<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.17"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HaxellNR05">BibTeX</a></font> </ul> <h2>Session 11</h2> <ul> <li><a name="DamgardFSS05" href="../../indices/a-tree/d/Damg=aring=rd:Ivan.html">Ivan Damgård</a>, <a href="../../indices/a-tree/f/Fehr:Serge.html">Serge Fehr</a>, <a href="../../indices/a-tree/s/Salvail:Louis.html">Louis Salvail</a>, <a href="../../indices/a-tree/s/Schaffner:Christian.html">Christian Schaffner</a>: <br><b>Cryptography In the Bounded Quantum-Storage Model. </b>449-458<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.30"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DamgardFSS05">BibTeX</a></font> <li><a name="Raz05" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>: <br><b>Quantum Information and the PCP Theorem. </b>459-468<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.62"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Raz05">BibTeX</a></font> <li><a name="BaconCD05" href="../../indices/a-tree/b/Bacon:Dave.html">Dave Bacon</a>, <a href="../../indices/a-tree/c/Childs:Andrew_M=.html">Andrew M. Childs</a>, <a href="../../indices/a-tree/d/Dam:Wim_van.html">Wim van Dam</a>: <br><b>From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. </b>469-478<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.38"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BaconCD05">BibTeX</a></font> <li><a name="MooreRS05" href="../../indices/a-tree/m/Moore:Cristopher.html">Cristopher Moore</a>, <a href="../../indices/a-tree/r/Russell:Alexander.html">Alexander Russell</a>, <a href="../../indices/a-tree/s/Schulman:Leonard_J=.html">Leonard J. Schulman</a>: <br><b>The Symmetric Group Defies Strong Fourier Sampling. </b>479-490<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.73"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MooreRS05">BibTeX</a></font> </ul> <h2>Session 12</h2> <ul> <li><a name="DasguptaHKS05" href="../../indices/a-tree/d/Dasgupta:Anirban.html">Anirban Dasgupta</a>, <a href="../../indices/a-tree/h/Hopcroft:John_E=.html">John E. Hopcroft</a>, <a href="../../indices/a-tree/k/Kleinberg:Jon_M=.html">Jon M. Kleinberg</a>, <a href="../../indices/a-tree/s/Sandler:Mark.html">Mark Sandler</a>: <br><b>On Learning Mixtures of Heavy-Tailed Distributions. </b>491-500<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.56"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DasguptaHKS05">BibTeX</a></font> <li><a name="SandlerOS05" href="../../indices/a-tree/f/Feldman:Jon.html">Jon Feldman</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 mixtures of product distributions over discrete domains. </b>501-510<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.46"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SandlerOS05">BibTeX</a></font> <li><a name="HayesS05" href="../../indices/a-tree/h/Hayes:Thomas_P=.html">Thomas P. Hayes</a>, <a href="../../indices/a-tree/s/Sinclair:Alistair.html">Alistair Sinclair</a>: <br><b>A general lower bound for mixing of single-site dynamics on graphs. </b>511-520<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.6"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HayesS05">BibTeX</a></font> <li><a name="BrazdilEK05" href="../../indices/a-tree/b/Br=aacute=zdil:Tom=aacute=s.html">Tomás Brázdil</a>, <a href="../../indices/a-tree/e/Esparza:Javier.html">Javier Esparza</a>, <a href="../../indices/a-tree/k/Kucera:Anton=iacute=n.html">Antonín Kucera</a>: <br><b>Analysis and Prediction of the Long-Run Behavior of Probabilistic Sequential Programs with Recursion (Extended Abstract). </b>521-530<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.19"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BrazdilEK05">BibTeX</a></font> <li><a name="KupfermanV05" href="../../indices/a-tree/k/Kupferman:Orna.html">Orna Kupferman</a>, <a href="../../indices/a-tree/v/Vardi:Moshe_Y=.html">Moshe Y. Vardi</a>: <br><b>Safraless Decision Procedures. </b>531-542<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.66"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KupfermanV05">BibTeX</a></font> </ul> <h2>Session 13</h2> <ul> <li><a name="Barak05" href="../../indices/a-tree/b/Barak:Boaz.html">Boaz Barak</a>, <a href="../../indices/a-tree/s/Sahai:Amit.html">Amit Sahai</a>: <br><b>How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation. </b>543-552<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.43"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Barak05">BibTeX</a></font> <li><a name="GoldwasserK05" 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>: <br><b>On the Impossibility of Obfuscation with Auxiliary Input. </b>553-562<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.60"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldwasserK05">BibTeX</a></font> <li><a name="PassR05" href="../../indices/a-tree/p/Pass:Rafael.html">Rafael Pass</a>, <a href="../../indices/a-tree/r/Rosen:Alon.html">Alon Rosen</a>: <br><b>Concurrent Non-Malleable Commitments. </b>563-572<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.27"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PassR05">BibTeX</a></font> <li><a name="NaorR05" href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>, <a href="../../indices/a-tree/r/Rothblum:Guy_N=.html">Guy N. Rothblum</a>: <br><b>The Complexity of Online Memory Checking. </b>573-584<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.71"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NaorR05">BibTeX</a></font> </ul> <h2>Session 14</h2> <ul> <li><a name="IzmalkovML05" href="../../indices/a-tree/i/Izmalkov:Sergei.html">Sergei Izmalkov</a>, <a href="../../indices/a-tree/m/Micali:Silvio.html">Silvio Micali</a>, <a href="../../indices/a-tree/l/Lepinski:Matt.html">Matt Lepinski</a>: <br><b>Rational Secure Computation and Ideal Mechanism Design. </b>585-595<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.64"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/IzmalkovML05">BibTeX</a></font> <li><a name="LaviS05" href="../../indices/a-tree/l/Lavi:Ron.html">Ron Lavi</a>, <a href="../../indices/a-tree/s/Swamy:Chaitanya.html">Chaitanya Swamy</a>: <br><b>Truthful and Near-Optimal Mechanism Design via Linear Programming. </b>595-604<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.76"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LaviS05">BibTeX</a></font> <li><a name="BalcanB05" 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/h/Hartline:Jason_D=.html">Jason D. Hartline</a>, <a href="../../indices/a-tree/m/Mansour:Yishay.html">Yishay Mansour</a>: <br><b>Mechanism Design via Machine Learning. </b>605-614<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.50"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BalcanB05">BibTeX</a></font> <li><a name="KarlinKT05" href="../../indices/a-tree/k/Karlin:Anna_R=.html">Anna R. Karlin</a>, <a href="../../indices/a-tree/k/Kempe:David.html">David Kempe</a>, <a href="../../indices/a-tree/t/Tamir:Tami.html">Tami Tamir</a>: <br><b>Beyond VCG: Frugality of Truthful Mechanisms. </b>615-626<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.25"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KarlinKT05">BibTeX</a></font> </ul> <h2>Session 15</h2> <ul> <li><a name="Kleinberg05" href="../../indices/a-tree/k/Kleinberg:Jon_M=.html">Jon M. Kleinberg</a>: <br><b>An Approximation Algorithm for the Disjoint Paths Problem in Even-Degree Planar Graphs. </b>627-636<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.18"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Kleinberg05">BibTeX</a></font> <li><a name="DemaineHK05" href="../../indices/a-tree/d/Demaine:Erik_D=.html">Erik D. Demaine</a>, <a href="../../indices/a-tree/h/Hajiaghayi:Mohammad_Taghi.html">Mohammad Taghi Hajiaghayi</a>, <a href="../../indices/a-tree/k/Kawarabayashi:Ken=ichi.html">Ken-ichi Kawarabayashi</a>: <br><b>Algorithmic Graph Minor Theory: Decomposition, Approximation, and Coloring. </b>637-646<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.14"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DemaineHK05">BibTeX</a></font> <li><a name="Klein05" href="../../indices/a-tree/k/Klein:Philip_N=.html">Philip N. Klein</a>: <br><b>A linear-time approximation scheme for planar weighted TSP. </b>647-657<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.7"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Klein05">BibTeX</a></font> <li><a name="BansalLS05" href="../../indices/a-tree/b/Bansal:Nikhil.html">Nikhil Bansal</a>, <a href="../../indices/a-tree/l/Lodi:Andrea.html">Andrea Lodi</a>, <a href="../../indices/a-tree/s/Sviridenko:Maxim.html">Maxim Sviridenko</a>: <br><b>A Tale of Two Dimensional Bin Packing. </b>657-666<br><a href="http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.10"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BansalLS05">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:27 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
