focs2006.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>FOCS 2006</title><link href="../../../dblp.css" rel="stylesheet" type="text/css" /></head><body> <table width="100%"><tr><td align="left"><a href="../../index.html"><img alt="dblp.uni-trier.de" src="../../Logo.gif" border=0 height=60 width=170></a></td> <td align="right"><a href="http://www.uni-trier.de"><img alt="www.uni-trier.de" src="../../logo_universitaet-trier.gif" border=0 height=48 width=215></a></td></tr></table> <h1>47. <a href="index.html">FOCS</a> 2006: Berkeley, CA, USA</h1> 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings. IEEE Computer Society 2006, ISBN 0-7695-2720-5 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/2006">BibTeX</a></font> <ul> <li><a name="NguyenOV06" href="../../indices/a-tree/n/Nguyen:Minh=Huyen.html">Minh-Huyen Nguyen</a>, <a href="../../indices/a-tree/o/Ong:Shien_Jin.html">Shien Jin Ong</a>, <a href="../../indices/a-tree/v/Vadhan:Salil_P=.html">Salil P. Vadhan</a>: <br><b>Statistical Zero-Knowledge Arguments for NP from Any One-Way Function. </b>3-14<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.71"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NguyenOV06">BibTeX</a></font> <li><a name="GoldwasserPV06" href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/p/Pavlov:Elan.html">Elan Pavlov</a>, <a href="../../indices/a-tree/v/Vaikuntanathan:Vinod.html">Vinod Vaikuntanathan</a>: <br><b>Fault-Tolerant Distributed Computing in Full-Information Networks. </b>15-26<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.30"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldwasserPV06">BibTeX</a></font> <li><a name="GentryRW06" href="../../indices/a-tree/g/Gentry:Craig.html">Craig Gentry</a>, <a href="../../indices/a-tree/r/Ramzan:Zulfikar.html">Zulfikar Ramzan</a>, <a href="../../indices/a-tree/w/Woodruff:David_P=.html">David P. Woodruff</a>: <br><b>Explicit Exclusive Set Systems with Applications to Broadcast Encryption. </b>27-38<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.27"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GentryRW06">BibTeX</a></font> <li><a name="Hayes06" href="../../indices/a-tree/h/Hayes:Thomas_P=.html">Thomas P. Hayes</a>: <br><b>A simple condition implying rapid mixing of single-site dynamics on spin systems. </b>39-46<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.6"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Hayes06">BibTeX</a></font> <li><a name="BelkinNN06" href="../../indices/a-tree/b/Belkin:Mikhail.html">Mikhail Belkin</a>, <a href="../../indices/a-tree/n/Narayanan:Hariharan.html">Hariharan Narayanan</a>, <a href="../../indices/a-tree/n/Niyogi:Partha.html">Partha Niyogi</a>: <br><b>Heat Flow and a Faster Algorithm to Compute the Surface Area of a Convex Body. </b>47-56<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.34"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BelkinNN06">BibTeX</a></font> <li><a name="LovaszV06" href="../../indices/a-tree/l/Lov=aacute=sz:L=aacute=szl=oacute=.html">László Lovász</a>, <a href="../../indices/a-tree/v/Vempala:Santosh.html">Santosh Vempala</a>: <br><b>Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization. </b>57-68<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.28"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LovaszV06">BibTeX</a></font> <li><a name="FederGMS06" href="../../indices/a-tree/f/Feder:Tom=aacute=s.html">Tomás Feder</a>, <a href="../../indices/a-tree/g/Guetz:Adam.html">Adam Guetz</a>, <a href="../../indices/a-tree/m/Mihail:Milena.html">Milena Mihail</a>, <a href="../../indices/a-tree/s/Saberi:Amin.html">Amin Saberi</a>: <br><b>A Local Switch Markov Chain on Given Degree Graphs with Application in Connectivity of Peer-to-Peer Networks. </b>69-76<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.5"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FederGMS06">BibTeX</a></font> <li><a name="AnshelevichSW06" href="../../indices/a-tree/a/Anshelevich:Elliot.html">Elliot Anshelevich</a>, <a href="../../indices/a-tree/s/Shepherd:F=_Bruce.html">F. Bruce Shepherd</a>, <a href="../../indices/a-tree/w/Wilfong:Gordon_T=.html">Gordon T. Wilfong</a>: <br><b>Strategic Network Formation through Peering and Service Agreements. </b>77-86<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.72"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AnshelevichSW06">BibTeX</a></font> <li><a name="KingSSV06" href="../../indices/a-tree/k/King:Valerie.html">Valerie King</a>, <a href="../../indices/a-tree/s/Saia:Jared.html">Jared Saia</a>, <a href="../../indices/a-tree/s/Sanwalani:Vishal.html">Vishal Sanwalani</a>, <a href="../../indices/a-tree/v/Vee:Erik.html">Erik Vee</a>: <br><b>Towards Secure and Scalable Computation in Peer-to-Peer Networks. </b>87-98<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.77"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KingSSV06">BibTeX</a></font> <li><a name="LeeN06" href="../../indices/a-tree/l/Lee:James_R=.html">James R. Lee</a>, <a href="../../indices/a-tree/n/Naor:Assaf.html">Assaf Naor</a>: <br><b>Lp metrics on the Heisenberg group and the Goemans-Linial conjecture. </b>99-108<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.47"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LeeN06">BibTeX</a></font> <li><a name="MendelN06" href="../../indices/a-tree/m/Mendel:Manor.html">Manor Mendel</a>, <a href="../../indices/a-tree/n/Naor:Assaf.html">Assaf Naor</a>: <br><b>Ramsey partitions and proximity data structures. </b>109-118<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.65"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MendelN06">BibTeX</a></font> <li><a name="KrauthgamerL06" href="../../indices/a-tree/k/Krauthgamer:Robert.html">Robert Krauthgamer</a>, <a href="../../indices/a-tree/l/Lee:James_R=.html">James R. Lee</a>: <br><b>Algorithms on negatively curved spaces. </b>119-132<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.9"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KrauthgamerL06">BibTeX</a></font> <li><a name="Vershynin06" href="../../indices/a-tree/v/Vershynin:Roman.html">Roman Vershynin</a>: <br><b>Beyond Hirsch Conjecture: Walks on Random Polytopes and Smoothed Complexity of the Simplex Method. </b>133-142<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.19"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Vershynin06">BibTeX</a></font> <li><a name="Sarlos06" href="../../indices/a-tree/s/Sarl=oacute=s:Tam=aacute=s.html">Tamás Sarlós</a>: <br><b>Improved Approximation Algorithms for Large Matrices via Random Projections. </b>143-152<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.37"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Sarlos06">BibTeX</a></font> <li><a name="ArthurV06" href="../../indices/a-tree/a/Arthur:David.html">David Arthur</a>, <a href="../../indices/a-tree/v/Vassilvitskii:Sergei.html">Sergei Vassilvitskii</a>: <br><b>Worst-case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-means Method. </b>153-164<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.79"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ArthurV06">BibTeX</a></font> <li><a name="OstrovskyRSS06" 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>, <a href="../../indices/a-tree/s/Swamy:Chaitanya.html">Chaitanya Swamy</a>: <br><b>The Effectiveness of Lloyd-Type Methods for the k-Means Problem. </b>165-176<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.75"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/OstrovskyRSS06">BibTeX</a></font> <li><a name="Ta-ShmaU06" href="../../indices/a-tree/t/Ta=Shma:Amnon.html">Amnon Ta-Shma</a>, <a href="../../indices/a-tree/u/Umans:Christopher.html">Christopher Umans</a>: <br><b>Better lossless condensers through derandomized curve samplers. </b>177-186<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.18"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ta-ShmaU06">BibTeX</a></font> <li><a name="ImpagliazzoJK06" 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>: <br><b>Approximately List-Decoding Direct Product Codes and Uniform Hardness Amplification. </b>187-196<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.13"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ImpagliazzoJK06">BibTeX</a></font> <li><a name="Bar-YossefBJK06" href="../../indices/a-tree/b/Bar=Yossef:Ziv.html">Ziv Bar-Yossef</a>, <a href="../../indices/a-tree/b/Birk:Yitzhak.html">Yitzhak Birk</a>, <a href="../../indices/a-tree/j/Jayram:T=_S=.html">T. S. Jayram</a>, <a href="../../indices/a-tree/k/Kol:Tomer.html">Tomer Kol</a>: <br><b>Index Coding with Side Information. </b>197-206<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.42"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Bar-YossefBJK06">BibTeX</a></font> <li><a name="Ben-SassonKR06" href="../../indices/a-tree/b/Ben=Sasson:Eli.html">Eli Ben-Sasson</a>, <a href="../../indices/a-tree/k/Kopparty:Swastik.html">Swastik Kopparty</a>, <a href="../../indices/a-tree/r/Radhakrishnan:Jaikumar.html">Jaikumar Radhakrishnan</a>: <br><b>Subspace Polynomials and List Decoding of Reed-Solomon Codes. </b>207-216<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.73"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ben-SassonKR06">BibTeX</a></font> <li><a name="KhotO06" href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>, <a href="../../indices/a-tree/o/O=Donnell:Ryan.html">Ryan O'Donnell</a>: <br><b>SDP gaps and UGC-hardness for MAXCUTGAIN. </b>217-226<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.67"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KhotO06">BibTeX</a></font> <li><a name="GuruswamiP06" href="../../indices/a-tree/g/Guruswami:Venkatesan.html">Venkatesan Guruswami</a>, <a href="../../indices/a-tree/p/Patthak:Anindya_C=.html">Anindya C. Patthak</a>: <br><b>Correlated Algebraic-Geometric Codes: Improved List Decoding over Bounded Alphabets. </b>227-238<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.23"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GuruswamiP06">BibTeX</a></font> <li><a name="IshaiKOS06" 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 from Anonymity. </b>239-248<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.25"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/IshaiKOS06">BibTeX</a></font> <li><a name="Ben-OrCGHS06" href="../../indices/a-tree/b/Ben=Or:Michael.html">Michael Ben-Or</a>, <a href="../../indices/a-tree/c/Cr=eacute=peau:Claude.html">Claude Crépeau</a>, <a href="../../indices/a-tree/g/Gottesman:Daniel.html">Daniel Gottesman</a>, <a href="../../indices/a-tree/h/Hassidim:Avinatan.html">Avinatan Hassidim</a>, <a href="../../indices/a-tree/s/Smith:Adam.html">Adam Smith</a>: <br><b>Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority. </b>249-260<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.68"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ben-OrCGHS06">BibTeX</a></font> <li><a name="ChenD06" href="../../indices/a-tree/c/Chen:Xi.html">Xi Chen</a>, <a href="../../indices/a-tree/d/Deng:Xiaotie.html">Xiaotie Deng</a>: <br><b>Settling the Complexity of Two-Player Nash Equilibrium. </b>261-272<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.69"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChenD06">BibTeX</a></font> <li><a name="Goemans06" href="../../indices/a-tree/g/Goemans:Michel_X=.html">Michel X. Goemans</a>: <br><b>Minimum Bounded Degree Spanning Trees. </b>273-282<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.48"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Goemans06">BibTeX</a></font> <li><a name="KiralyL06" href="../../indices/a-tree/k/Kir=aacute=ly:Tam=aacute=s.html">Tamás Király</a>, <a href="../../indices/a-tree/l/Lau:Lap_Chi.html">Lap Chi Lau</a>: <br><b>Approximate Min-Max Theorems of Steiner Rooted-Orientations of Hypergraphs. </b>283-292<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.12"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KiralyL06">BibTeX</a></font> <li><a name="BuchbinderN06" 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>Improved Bounds for Online Routing and Packing Via a Primal-Dual Approach. </b>293-304<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.39"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BuchbinderN06">BibTeX</a></font> <li><a name="ArgeBG06" href="../../indices/a-tree/a/Arge:Lars.html">Lars Arge</a>, <a href="../../indices/a-tree/b/Brodal:Gerth_St=oslash=lting.html">Gerth Stølting Brodal</a>, <a href="../../indices/a-tree/g/Georgiadis:Loukas.html">Loukas Georgiadis</a>: <br><b>Improved Dynamic Planar Point Location. </b>305-314<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.40"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ArgeBG06">BibTeX</a></font> <li><a name="FeldmanFS06" href="../../indices/a-tree/f/Feldman:Dan.html">Dan Feldman</a>, <a href="../../indices/a-tree/f/Fiat:Amos.html">Amos Fiat</a>, <a href="../../indices/a-tree/s/Sharir:Micha.html">Micha Sharir</a>: <br><b>Coresets forWeighted Facilities and Their Applications. </b>315-324<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.22"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FeldmanFS06">BibTeX</a></font> <li><a name="Patrascu06" href="../../indices/a-tree/p/Patrascu:Mihai.html">Mihai Patrascu</a>: <br><b>Planar Point Location in Sublogarithmic Time. </b>325-332<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.61"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Patrascu06">BibTeX</a></font> <li><a name="Chan06" href="../../indices/a-tree/c/Chan:Timothy_M=.html">Timothy M. Chan</a>: <br><b>Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry. </b>333-344<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.62"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Chan06">BibTeX</a></font> <li><a name="BarakPS06" href="../../indices/a-tree/b/Barak:Boaz.html">Boaz Barak</a>, <a href="../../indices/a-tree/p/Prabhakaran:Manoj.html">Manoj Prabhakaran</a>, <a href="../../indices/a-tree/s/Sahai:Amit.html">Amit Sahai</a>: <br><b>Concurrent Non-Malleable Zero Knowledge. </b>345-354<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.21"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BarakPS06">BibTeX</a></font> <li><a name="KalaiR06" href="../../indices/a-tree/k/Kalai:Yael_Tauman.html">Yael Tauman Kalai</a>, <a href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>: <br><b>Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP. </b>355-366<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.74"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KalaiR06">BibTeX</a></font> <li><a name="MicaliPR06" href="../../indices/a-tree/m/Micali:Silvio.html">Silvio Micali</a>, <a 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>Input-Indistinguishable Computation. </b>367-378<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.43"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MicaliPR06">BibTeX</a></font> <li><a name="OnakP06" href="../../indices/a-tree/o/Onak:Krzysztof.html">Krzysztof Onak</a>, <a href="../../indices/a-tree/p/Parys:Pawel.html">Pawel Parys</a>: <br><b>Generalization of Binary Search: Searching in Trees and Forest-Like Partial Orders. </b>379-388<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.32"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/OnakP06">BibTeX</a></font> <li><a name="Woodruff06" href="../../indices/a-tree/w/Woodruff:David_P=.html">David P. Woodruff</a>: <br><b>Lower Bounds for Additive Spanners, Emulators, and More. </b>389-398<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.45"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Woodruff06">BibTeX</a></font> <li><a name="BaumannS06" href="../../indices/a-tree/b/Baumann:Nadine.html">Nadine Baumann</a>, <a href="../../indices/a-tree/s/Skutella:Martin.html">Martin Skutella</a>: <br><b>Solving Evacuation Problems Efficiently--Earliest Arrival Flows with Multiple Sources. </b>399-410<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.70"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BaumannS06">BibTeX</a></font> <li><a name="BuhrmanCLLSU06" href="../../indices/a-tree/b/Buhrman:Harry.html">Harry Buhrman</a>, <a href="../../indices/a-tree/c/Cleve:Richard.html">Richard Cleve</a>, <a href="../../indices/a-tree/l/Laurent:Monique.html">Monique Laurent</a>, <a href="../../indices/a-tree/l/Linden:Noah.html">Noah Linden</a>, <a href="../../indices/a-tree/s/Schrijver:Alexander.html">Alexander Schrijver</a>, <a href="../../indices/a-tree/u/Unger:Falk.html">Falk Unger</a>: <br><b>New Limits on Fault-Tolerant Quantum Computation. </b>411-419<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.50"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BuhrmanCLLSU06">BibTeX</a></font> <li><a name="Reichardt06" href="../../indices/a-tree/r/Reichardt:Ben.html">Ben Reichardt</a>: <br><b>Postselection threshold against biased noise. </b>420-428<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.64"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Reichardt06">BibTeX</a></font> <li><a name="SunY06" href="../../indices/a-tree/s/Sun:Xiaoming.html">Xiaoming Sun</a>, <a href="../../indices/a-tree/y/Yao:Andrew_Chi=Chih.html">Andrew Chi-Chih Yao</a>: <br><b>On the Quantum Query Complexity of Local Search in Two and Three Dimensions. </b>429-438<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.57"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SunY06">BibTeX</a></font> <li><a name="WoodsN06" href="../../indices/a-tree/w/Woods:Damien.html">Damien Woods</a>, <a href="../../indices/a-tree/n/Neary:Turlough.html">Turlough Neary</a>: <br><b>On the time complexity of 2-tag systems and small universal Turing machines. </b>439-448<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.58"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/WoodsN06">BibTeX</a></font> <li><a name="AndoniIP06" href="../../indices/a-tree/a/Andoni:Alexandr.html">Alexandr Andoni</a>, <a href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>, <a href="../../indices/a-tree/p/Patrascu:Mihai.html">Mihai Patrascu</a>: <br><b>On the Optimality of the Dimensionality Reduction Method. </b>449-458<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.56"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AndoniIP06">BibTeX</a></font> <li><a name="AndoniI06" href="../../indices/a-tree/a/Andoni:Alexandr.html">Alexandr Andoni</a>, <a href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>: <br><b>Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions. </b>459-468<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.49"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AndoniI06">BibTeX</a></font> <li><a name="GuLM06" href="../../indices/a-tree/g/Gu:Xiaoyang.html">Xiaoyang Gu</a>, <a href="../../indices/a-tree/l/Lutz:Jack_H=.html">Jack H. Lutz</a>, <a href="../../indices/a-tree/m/Mayordomo:Elvira.html">Elvira Mayordomo</a>: <br><b>Points on Computable Curves. </b>469-474<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.63"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GuLM06">BibTeX</a></font> <li><a name="AndersenCL06" href="../../indices/a-tree/a/Andersen:Reid.html">Reid Andersen</a>, <a href="../../indices/a-tree/c/Chung:Fan_R=_K=.html">Fan R. K. Chung</a>, <a href="../../indices/a-tree/l/Lang:Kevin_J=.html">Kevin J. Lang</a>: <br><b>Local Graph Partitioning using PageRank Vectors. </b>475-486<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.44"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AndersenCL06">BibTeX</a></font> <li><a name="Rudelson06" href="../../indices/a-tree/r/Rudelson:Mark.html">Mark Rudelson</a>: <br><b>Norm of the inverse of a random matrix. </b>487-496<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.52"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Rudelson06">BibTeX</a></font> <li><a name="FeigeKO06" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>, <a href="../../indices/a-tree/k/Kim:Jeong_Han.html">Jeong Han Kim</a>, <a href="../../indices/a-tree/o/Ofek:Eran.html">Eran Ofek</a>: <br><b>Witnesses for non-satisfiability of dense random 3CNF formulas. </b>497-508<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.78"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FeigeKO06">BibTeX</a></font> <li><a name="Valiant06" href="../../indices/a-tree/v/Valiant:Leslie_G=.html">Leslie G. Valiant</a>: <br><b>Accidental Algorthims. </b>509-517<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.7"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Valiant06">BibTeX</a></font> <li><a name="BorgsCMR06" 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/m/Mossel:Elchanan.html">Elchanan Mossel</a>, <a href="../../indices/a-tree/r/Roch:S=eacute=bastien.html">Sébastien Roch</a>: <br><b>The Kesten-Stigum Reconstruction Bound Is Tight for Roughly Symmetric Binary Channels. </b>518-530<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.76"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BorgsCMR06">BibTeX</a></font> <li><a name="Harvey06" href="../../indices/a-tree/h/Harvey:Nicholas_J=_A=.html">Nicholas J. A. Harvey</a>: <br><b>Algebraic Structures and Algorithms for Matching and Matroid Problems. </b>531-542<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.8"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Harvey06">BibTeX</a></font> <li><a name="GuruswamiR06" href="../../indices/a-tree/g/Guruswami:Venkatesan.html">Venkatesan Guruswami</a>, <a href="../../indices/a-tree/r/Raghavendra:Prasad.html">Prasad Raghavendra</a>: <br><b>Hardness of Learning Halfspaces with Noise. </b>543-552<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.33"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GuruswamiR06">BibTeX</a></font> <li><a name="KlivansS06" href="../../indices/a-tree/k/Klivans:Adam_R=.html">Adam R. Klivans</a>, <a href="../../indices/a-tree/s/Sherstov:Alexander_A=.html">Alexander A. Sherstov</a>: <br><b>Cryptographic Hardness for Learning Intersections of Halfspaces. </b>553-562<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.24"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KlivansS06">BibTeX</a></font> <li><a name="FeldmanGKP06" href="../../indices/a-tree/f/Feldman:Vitaly.html">Vitaly Feldman</a>, <a href="../../indices/a-tree/g/Gopalan:Parikshit.html">Parikshit Gopalan</a>, <a href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>, <a href="../../indices/a-tree/p/Ponnuswami:Ashok_Kumar.html">Ashok Kumar Ponnuswami</a>: <br><b>New Results for Learning Noisy Parities and Halfspaces. </b>563-574<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.51"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FeldmanGKP06">BibTeX</a></font> <li><a name="BjorklundH06" 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>: <br><b>Inclusion--Exclusion Algorithms for Counting Set Partitions. </b>575-582<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.41"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BjorklundH06">BibTeX</a></font> <li><a name="Koivisto06" href="../../indices/a-tree/k/Koivisto:Mikko.html">Mikko Koivisto</a>: <br><b>An O*(2^n ) Algorithm for Graph Coloring and Other Partitioning Problems via Inclusion--Exclusion. </b>583-590<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.11"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Koivisto06">BibTeX</a></font> <li><a name="BaswanaK06" href="../../indices/a-tree/b/Baswana:Surender.html">Surender Baswana</a>, <a href="../../indices/a-tree/k/Kavitha:Telikepalli.html">Telikepalli Kavitha</a>: <br><b>Faster Algorithms for Approximate Distance Oracles and All-Pairs Small Stretch Paths. </b>591-602<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.29"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BaswanaK06">BibTeX</a></font> <li><a name="ChenDT06" href="../../indices/a-tree/c/Chen:Xi.html">Xi Chen</a>, <a href="../../indices/a-tree/d/Deng:Xiaotie.html">Xiaotie Deng</a>, <a href="../../indices/a-tree/t/Teng:Shang=Hua.html">Shang-Hua Teng</a>: <br><b>Computing Nash Equilibria: Approximation and Smoothed Complexity. </b>603-612<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.20"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChenDT06">BibTeX</a></font> <li><a name="AckermannRV06" href="../../indices/a-tree/a/Ackermann:Heiner.html">Heiner Ackermann</a>, <a href="../../indices/a-tree/r/R=ouml=glin:Heiko.html">Heiko Röglin</a>, <a href="../../indices/a-tree/v/V=ouml=cking:Berthold.html">Berthold Vöcking</a>: <br><b>On the Impact of Combinatorial Structure on Congestion Games. </b>613-622<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.55"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AckermannRV06">BibTeX</a></font> <li><a name="EdmondsP06" href="../../indices/a-tree/e/Edmonds:Jeff.html">Jeff Edmonds</a>, <a href="../../indices/a-tree/p/Pruhs:Kirk.html">Kirk Pruhs</a>: <br><b>Balanced Allocations of Cake. </b>623-634<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.17"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/EdmondsP06">BibTeX</a></font> <li><a name="Wagner06" href="../../indices/a-tree/w/Wagner:Uli.html">Uli Wagner</a>: <br><b>On a Geometric Generalization of the Upper Bound Theorem. </b>635-645<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.53"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Wagner06">BibTeX</a></font> <li><a name="PatrascuT06" href="../../indices/a-tree/p/Patrascu:Mihai.html">Mihai Patrascu</a>, <a href="../../indices/a-tree/t/Thorup:Mikkel.html">Mikkel Thorup</a>: <br><b>Higher Lower Bounds for Near-Neighbor and Further Rich Problems. </b>646-654<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.35"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PatrascuT06">BibTeX</a></font> <li><a name="NaorS06" href="../../indices/a-tree/n/Naor:Assaf.html">Assaf Naor</a>, <a href="../../indices/a-tree/s/Schechtman:Gideon.html">Gideon Schechtman</a>: <br><b>Planar Earthmover is not in L_1. </b>655-666<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.60"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NaorS06">BibTeX</a></font> <li><a name="FeigeV06" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>, <a href="../../indices/a-tree/v/Vondr=aacute=k:Jan.html">Jan Vondrák</a>: <br><b>Approximation algorithms for allocation problems: Improving the factor of 1 - 1/e. </b>667-676<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.14"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FeigeV06">BibTeX</a></font> <li><a name="ChekuriHKS06" href="../../indices/a-tree/c/Chekuri:Chandra.html">Chandra Chekuri</a>, <a href="../../indices/a-tree/h/Hajiaghayi:Mohammad_Taghi.html">Mohammad Taghi Hajiaghayi</a>, <a href="../../indices/a-tree/k/Kortsarz:Guy.html">Guy Kortsarz</a>, <a href="../../indices/a-tree/s/Salavatipour:Mohammad_R=.html">Mohammad R. Salavatipour</a>: <br><b>Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design. </b>677-686<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.15"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChekuriHKS06">BibTeX</a></font> <li><a name="ChlamtacMM06" href="../../indices/a-tree/c/Chlamtac:Eden.html">Eden Chlamtac</a>, <a href="../../indices/a-tree/m/Makarychev:Konstantin.html">Konstantin Makarychev</a>, <a href="../../indices/a-tree/m/Makarychev:Yury.html">Yury Makarychev</a>: <br><b>How to Play Unique Games Using Embeddings. </b>687-696<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.36"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChlamtacMM06">BibTeX</a></font> <li><a name="BansalCS06" href="../../indices/a-tree/b/Bansal:Nikhil.html">Nikhil Bansal</a>, <a href="../../indices/a-tree/c/Caprara:Alberto.html">Alberto Caprara</a>, <a href="../../indices/a-tree/s/Sviridenko:Maxim.html">Maxim Sviridenko</a>: <br><b>Improved approximation algorithms for multidimensional bin packing problems. </b>697-708<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.38"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BansalCS06">BibTeX</a></font> <li><a name="ChattopadhyayGPT06" href="../../indices/a-tree/c/Chattopadhyay:Arkadev.html">Arkadev Chattopadhyay</a>, <a href="../../indices/a-tree/g/Goyal:Navin.html">Navin Goyal</a>, <a href="../../indices/a-tree/p/Pudl=aacute=k:Pavel.html">Pavel Pudlák</a>, <a href="../../indices/a-tree/t/Th=eacute=rien:Denis.html">Denis Thérien</a>: <br><b>Lower bounds for circuits with MOD_m gates. </b>709-718<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.46"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChattopadhyayGPT06">BibTeX</a></font> <li><a name="HarnikN06" href="../../indices/a-tree/h/Harnik:Danny.html">Danny Harnik</a>, <a href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>: <br><b>On the Compressibility of NP Instances and Cryptographic Applications. </b>719-728<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.54"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HarnikN06">BibTeX</a></font> <li><a name="RademacherV06" href="../../indices/a-tree/r/Rademacher:Luis.html">Luis Rademacher</a>, <a href="../../indices/a-tree/v/Vempala:Santosh.html">Santosh Vempala</a>: <br><b>Dispersion of Mass and the Complexity of Randomized Geometric Algorithms. </b>729-738<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.26"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RademacherV06">BibTeX</a></font> <li><a name="RazborovY06" href="../../indices/a-tree/r/Razborov:Alexander_A=.html">Alexander A. Razborov</a>, <a href="../../indices/a-tree/y/Yekhanin:Sergey.html">Sergey Yekhanin</a>: <br><b>An Omega(n<sup>1/3</sup>) Lower Bound for Bilinear Group Based Private Information Retrieval. </b>739-748<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.10"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RazborovY06">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
