focs2007.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>FOCS 2007</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>48. <a href="index.html">FOCS</a> 2007: Providence, RI, USA</h1> 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings. IEEE Computer Society 2007 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/2007">BibTeX</a></font> <h2>Tutorials</h2> <ul> <li><a name="Tao07" href="../../indices/a-tree/t/Tao:Terence.html">Terence Tao</a>: <br><b>Structure and Randomness in Combinatorics. </b>3-15<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.68"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Tao07">BibTeX</a></font> <li><a name="Boneh07" href="../../indices/a-tree/b/Boneh:Dan.html">Dan Boneh</a>: <br><b>A Brief Look at Pairings Based Cryptography. </b>19-26<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.5"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Boneh07">BibTeX</a></font> <li><a name="Spielman07" href="../../indices/a-tree/s/Spielman:Daniel_A=.html">Daniel A. Spielman</a>: <br><b>Spectral Graph Theory and its Applications. </b>29-38<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.66"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Spielman07">BibTeX</a></font> </ul> <h2>Regular Papers</h2> <ul> <li><a name="BogdanovV07" href="../../indices/a-tree/b/Bogdanov:Andrej.html">Andrej Bogdanov</a>, <a href="../../indices/a-tree/v/Viola:Emanuele.html">Emanuele Viola</a>: <br><b>Pseudorandom Bits for Polynomials. </b>41-51<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.56"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BogdanovV07">BibTeX</a></font> <li><a name="DvirGW07" href="../../indices/a-tree/d/Dvir:Zeev.html">Zeev Dvir</a>, <a href="../../indices/a-tree/g/Gabizon:Ariel.html">Ariel Gabizon</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>Extractors and Rank Extractors for Polynomial Sources. </b>52-62<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.26"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DvirGW07">BibTeX</a></font> <li><a name="Bazzi07" href="../../indices/a-tree/b/Bazzi:Louay.html">Louay Bazzi</a>: <br><b>Polylogarithmic Independence Can Fool DNF Formulas. </b>63-73<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.55"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Bazzi07">BibTeX</a></font> <li><a name="Cheng07" href="../../indices/a-tree/c/Cheng:Qi.html">Qi Cheng</a>: <br><b>Derandomization of Sparse Cyclotomic Integer Zero Testing. </b>74-80<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.23"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Cheng07">BibTeX</a></font> <li><a name="DaskalakisP07" 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>Computing Equilibria in Anonymous Games. </b>83-93<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.19"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DaskalakisP07">BibTeX</a></font> <li><a name="McSherryT07" href="../../indices/a-tree/m/McSherry:Frank.html">Frank McSherry</a>, <a href="../../indices/a-tree/t/Talwar:Kunal.html">Kunal Talwar</a>: <br><b>Mechanism Design via Differential Privacy. </b>94-103<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.41"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/McSherryT07">BibTeX</a></font> <li><a name="ImmorlicaKMT07" href="../../indices/a-tree/i/Immorlica:Nicole.html">Nicole Immorlica</a>, <a href="../../indices/a-tree/k/Karlin:Anna_R=.html">Anna R. Karlin</a>, <a href="../../indices/a-tree/m/Mahdian:Mohammad.html">Mohammad Mahdian</a>, <a href="../../indices/a-tree/t/Talwar:Kunal.html">Kunal Talwar</a>: <br><b>Balloon Popping With Applications to Ascending Auctions. </b>104-112<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.15"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ImmorlicaKMT07">BibTeX</a></font> <li><a name="EtessamiY07" href="../../indices/a-tree/e/Etessami:Kousha.html">Kousha Etessami</a>, <a href="../../indices/a-tree/y/Yannakakis:Mihalis.html">Mihalis Yannakakis</a>: <br><b>On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract). </b>113-123<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.48"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/EtessamiY07">BibTeX</a></font> <li><a name="ChenT07" href="../../indices/a-tree/c/Chen:Xi.html">Xi Chen</a>, <a href="../../indices/a-tree/t/Teng:Shang=Hua.html">Shang-Hua Teng</a>: <br><b>Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation. </b>124-134<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.53"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChenT07">BibTeX</a></font> <li><a name="HertelP07" href="../../indices/a-tree/h/Hertel:Philipp.html">Philipp Hertel</a>, <a href="../../indices/a-tree/p/Pitassi:Toniann.html">Toniann Pitassi</a>: <br><b>Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling. </b>137-149<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.25"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HertelP07">BibTeX</a></font> <li><a name="DantchevMS07" href="../../indices/a-tree/d/Dantchev:Stefan_S=.html">Stefan S. Dantchev</a>, <a href="../../indices/a-tree/m/Martin:Barnaby.html">Barnaby Martin</a>, <a href="../../indices/a-tree/s/Szeider:Stefan.html">Stefan Szeider</a>: <br><b>Parameterized Proof Complexity. </b>150-160<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.52"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DantchevMS07">BibTeX</a></font> <li><a name="LubetzkyS07" href="../../indices/a-tree/l/Lubetzky:Eyal.html">Eyal Lubetzky</a>, <a href="../../indices/a-tree/s/Stav:Uri.html">Uri Stav</a>: <br><b>Non-Linear Index Coding Outperforming the Linear Optimum. </b>161-168<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.45"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LubetzkyS07">BibTeX</a></font> <li><a name="Marx07" href="../../indices/a-tree/m/Marx:D=aacute=niel.html">Dániel Marx</a>: <br><b>Can you beat treewidth? </b>169-179<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.18"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Marx07">BibTeX</a></font> <li><a name="StefankovicVV07" href="../../indices/a-tree/s/Stefankovic:Daniel.html">Daniel Stefankovic</a>, <a href="../../indices/a-tree/v/Vempala:Santosh.html">Santosh Vempala</a>, <a href="../../indices/a-tree/v/Vigoda:Eric.html">Eric Vigoda</a>: <br><b>Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. </b>183-193<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.8"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/StefankovicVV07">BibTeX</a></font> <li><a name="GerschenfeldM07" href="../../indices/a-tree/g/Gerschenfeld:Antoine.html">Antoine Gerschenfeld</a>, <a href="../../indices/a-tree/m/Montanari:Andrea.html">Andrea Montanari</a>: <br><b>Reconstruction for Models on Random Graphs. </b>194-204<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.58"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GerschenfeldM07">BibTeX</a></font> <li><a name="LongNP07" href="../../indices/a-tree/l/Long:Yun.html">Yun Long</a>, <a href="../../indices/a-tree/n/Nachmias:Asaf.html">Asaf Nachmias</a>, <a href="../../indices/a-tree/p/Peres:Yuval.html">Yuval Peres</a>: <br><b>Mixing Time Power Laws at Criticality. </b>205-214<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.43"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LongNP07">BibTeX</a></font> <li><a name="KimMT07" href="../../indices/a-tree/k/Kim:Jeong_Han.html">Jeong Han Kim</a>, <a href="../../indices/a-tree/m/Montenegro:Ravi.html">Ravi Montenegro</a>, <a href="../../indices/a-tree/t/Tetali:Prasad.html">Prasad Tetali</a>: <br><b>Near Optimal Bounds for Collision in Pollard Rho for Discrete Log. </b>215-223<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.44"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KimMT07">BibTeX</a></font> <li><a name="DziembowskiP07" 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>Intrusion-Resilient Secret Sharing. </b>227-237<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.35"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DziembowskiP07">BibTeX</a></font> <li><a name="ChandranGOS07" href="../../indices/a-tree/c/Chandran:Nishanth.html">Nishanth Chandran</a>, <a href="../../indices/a-tree/g/Goyal:Vipul.html">Vipul Goyal</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>Covert Multi-Party Computation. </b>238-248<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.21"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChandranGOS07">BibTeX</a></font> <li><a name="CanettiPS07" href="../../indices/a-tree/c/Canetti:Ran.html">Ran Canetti</a>, <a href="../../indices/a-tree/p/Pass:Rafael.html">Rafael Pass</a>, <a href="../../indices/a-tree/s/Shelat:Abhi.html">Abhi Shelat</a>: <br><b>Cryptography from Sunspots: How to Use an Imperfect Reference String. </b>249-259<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.22"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CanettiPS07">BibTeX</a></font> <li><a name="PatrascuT07" 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>Planning for Fast Connectivity Updates. </b>263-271<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.54"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PatrascuT07">BibTeX</a></font> <li><a name="BlellochG07" href="../../indices/a-tree/b/Blelloch:Guy_E=.html">Guy E. Blelloch</a>, <a href="../../indices/a-tree/g/Golovin:Daniel.html">Daniel Golovin</a>: <br><b>Strongly History-Independent Hashing with Applications. </b>272-282<br><a href="http://doi.ieeecomputersociety.org/"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BlellochG07">BibTeX</a></font> <li><a name="BravermanO07" href="../../indices/a-tree/b/Braverman:Vladimir.html">Vladimir Braverman</a>, <a href="../../indices/a-tree/o/Ostrovsky:Rafail.html">Rafail Ostrovsky</a>: <br><b>Smooth Histograms for Sliding Windows. </b>283-293<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.63"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BravermanO07">BibTeX</a></font> <li><a name="GalG07" href="../../indices/a-tree/g/G=aacute=l:Anna.html">Anna Gál</a>, <a href="../../indices/a-tree/g/Gopalan:Parikshit.html">Parikshit Gopalan</a>: <br><b>Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence. </b>294-304<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.39"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GalG07">BibTeX</a></font> <li><a name="Austrin07" href="../../indices/a-tree/a/Austrin:Per.html">Per Austrin</a>: <br><b>Towards Sharp Inapproximability For Any 2-CSP. </b>307-317<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.73"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Austrin07">BibTeX</a></font> <li><a name="KhotN07" 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>Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. </b>318-328<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.36"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KhotN07">BibTeX</a></font> <li><a name="AmbuhlMS07" href="../../indices/a-tree/a/Amb=uuml=hl:Christoph.html">Christoph Ambühl</a>, <a 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>Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling. </b>329-337<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.32"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AmbuhlMS07">BibTeX</a></font> <li><a name="Marx07a" href="../../indices/a-tree/m/Marx:D=aacute=niel.html">Dániel Marx</a>: <br><b>On the Optimality of Planar and Geometric Approximation Schemes. </b>338-348<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.50"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Marx07a">BibTeX</a></font> <li><a name="GopalanKS07" 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/s/Saket:Rishi.html">Rishi Saket</a>: <br><b>Hardness of Reconstructing Multivariate Polynomials over Finite Fields. </b>349-359<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.31"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GopalanKS07">BibTeX</a></font> <li><a name="AmbainisCRSZ07" href="../../indices/a-tree/a/Ambainis:Andris.html">Andris Ambainis</a>, <a href="../../indices/a-tree/c/Childs:Andrew_M=.html">Andrew M. Childs</a>, <a href="../../indices/a-tree/r/Reichardt:Ben.html">Ben Reichardt</a>, <a href="../../indices/a-tree/s/Spalek:Robert.html">Robert Spalek</a>, <a href="../../indices/a-tree/z/Zhang:Shengyu.html">Shengyu Zhang</a>: <br><b>Any AND-OR Formula of Size N can be Evaluated in time N<sup>1/2+o(1)</sup> on a Quantum Computer. </b>363-372<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.10"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AmbainisCRSZ07">BibTeX</a></font> <li><a name="AharonovGIK07" href="../../indices/a-tree/a/Aharonov:Dorit.html">Dorit Aharonov</a>, <a href="../../indices/a-tree/g/Gottesman:Daniel.html">Daniel Gottesman</a>, <a href="../../indices/a-tree/i/Irani:Sandy.html">Sandy Irani</a>, <a href="../../indices/a-tree/k/Kempe:Julia.html">Julia Kempe</a>: <br><b>The Power of Quantum Systems on a Line. </b>373-383<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.72"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AharonovGIK07">BibTeX</a></font> <li><a name="RegevT07" 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>Simulating Quantum Correlations with Finite Communication. </b>384-394<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.62"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RegevT07">BibTeX</a></font> <li><a name="ChildsSV07" href="../../indices/a-tree/c/Childs:Andrew_M=.html">Andrew M. Childs</a>, <a href="../../indices/a-tree/s/Schulman:Leonard_J=.html">Leonard J. Schulman</a>, <a href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>: <br><b>Quantum Algorithms for Hidden Nonlinear Structures. </b>395-404<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.57"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChildsSV07">BibTeX</a></font> <li><a name="Feige07" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>: <br><b>Refuting Smoothed 3CNF Formulas. </b>407-417<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.59"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Feige07">BibTeX</a></font> <li><a name="BogdanovS07" href="../../indices/a-tree/b/Bogdanov:Andrej.html">Andrej Bogdanov</a>, <a href="../../indices/a-tree/s/Safra:Muli.html">Muli Safra</a>: <br><b>Hardness Amplification for Errorless Heuristics. </b>418-426<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.30"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BogdanovS07">BibTeX</a></font> <li><a name="ViolaW07" href="../../indices/a-tree/v/Viola:Emanuele.html">Emanuele Viola</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications. </b>427-437<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.51"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ViolaW07">BibTeX</a></font> <li><a name="RazSY07" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>, <a href="../../indices/a-tree/s/Shpilka:Amir.html">Amir Shpilka</a>, <a href="../../indices/a-tree/y/Yehudayoff:Amir.html">Amir Yehudayoff</a>: <br><b>A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. </b>438-448<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.6"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RazSY07">BibTeX</a></font> <li><a name="Chattopadhyay07" href="../../indices/a-tree/c/Chattopadhyay:Arkadev.html">Arkadev Chattopadhyay</a>: <br><b>Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits. </b>449-458<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.24"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Chattopadhyay07">BibTeX</a></font> <li><a name="FeigeMV07" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>, <a href="../../indices/a-tree/m/Mirrokni:Vahab_S=.html">Vahab S. Mirrokni</a>, <a href="../../indices/a-tree/v/Vondr=aacute=k:Jan.html">Jan Vondrák</a>: <br><b>Maximizing Non-Monotone Submodular Functions. </b>461-471<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.40"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FeigeMV07">BibTeX</a></font> <li><a name="KelnerN07" href="../../indices/a-tree/k/Kelner:Jonathan_A=.html">Jonathan A. Kelner</a>, <a href="../../indices/a-tree/n/Nikolova:Evdokia.html">Evdokia Nikolova</a>: <br><b>On the Hardness and Smoothed Complexity of Quasi-Concave Minimization. </b>472-482<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.49"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KelnerN07">BibTeX</a></font> <li><a name="GuhaM07" href="../../indices/a-tree/g/Guha:Sudipto.html">Sudipto Guha</a>, <a href="../../indices/a-tree/m/Munagala:Kamesh.html">Kamesh Munagala</a>: <br><b>Approximation Algorithms for Partial-Information Based Stochastic Control with Markovian Rewards. </b>483-493<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.12"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GuhaM07">BibTeX</a></font> <li><a name="KoufogiannakisY07" href="../../indices/a-tree/k/Koufogiannakis:Christos.html">Christos Koufogiannakis</a>, <a href="../../indices/a-tree/y/Young:Neal_E=.html">Neal E. Young</a>: <br><b>Beating Simplex for Fractional Packing and Covering Linear Programs. </b>494-504<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.16"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KoufogiannakisY07">BibTeX</a></font> <li><a name="BansalBN07" href="../../indices/a-tree/b/Bansal:Nikhil.html">Nikhil Bansal</a>, <a href="../../indices/a-tree/b/Buchbinder:Niv.html">Niv Buchbinder</a>, <a href="../../indices/a-tree/n/Naor:Joseph.html">Joseph Naor</a>: <br><b>A Primal-Dual Randomized Algorithm for Weighted Paging. </b>507-517<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.7"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BansalBN07">BibTeX</a></font> <li><a name="AlonC07" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/c/Capalbo:Michael_R=.html">Michael R. Capalbo</a>: <br><b>Finding Disjoint Paths in Expanders Deterministically and Online. </b>518-524<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.28"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonC07">BibTeX</a></font> <li><a name="EzraS07" href="../../indices/a-tree/e/Ezra:Esther.html">Esther Ezra</a>, <a href="../../indices/a-tree/s/Sharir:Micha.html">Micha Sharir</a>: <br><b>Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions. </b>525-535<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.9"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/EzraS07">BibTeX</a></font> <li><a name="BendichCEHM07" href="../../indices/a-tree/b/Bendich:Paul.html">Paul Bendich</a>, <a href="../../indices/a-tree/c/Cohen=Steiner:David.html">David Cohen-Steiner</a>, <a href="../../indices/a-tree/e/Edelsbrunner:Herbert.html">Herbert Edelsbrunner</a>, <a href="../../indices/a-tree/h/Harer:John.html">John Harer</a>, <a href="../../indices/a-tree/m/Morozov:Dmitriy.html">Dmitriy Morozov</a>: <br><b>Inferring Local Homology from Sampled Stratified Spaces. </b>536-546<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.33"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BendichCEHM07">BibTeX</a></font> <li><a name="DiakonikolasLMORSW07" href="../../indices/a-tree/d/Diakonikolas:Ilias.html">Ilias Diakonikolas</a>, <a href="../../indices/a-tree/l/Lee:Homin_K=.html">Homin K. Lee</a>, <a href="../../indices/a-tree/m/Matulef:Kevin.html">Kevin Matulef</a>, <a href="../../indices/a-tree/o/Onak:Krzysztof.html">Krzysztof Onak</a>, <a href="../../indices/a-tree/r/Rubinfeld:Ronitt.html">Ronitt Rubinfeld</a>, <a href="../../indices/a-tree/s/Servedio:Rocco_A=.html">Rocco A. Servedio</a>, <a href="../../indices/a-tree/w/Wan:Andrew.html">Andrew Wan</a>: <br><b>Testing for Concise Representations. </b>549-558<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.70"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DiakonikolasLMORSW07">BibTeX</a></font> <li><a name="RaskhodnikovaRSS07" href="../../indices/a-tree/r/Raskhodnikova:Sofya.html">Sofya Raskhodnikova</a>, <a href="../../indices/a-tree/r/Ron:Dana.html">Dana Ron</a>, <a href="../../indices/a-tree/s/Shpilka:Amir.html">Amir Shpilka</a>, <a href="../../indices/a-tree/s/Smith:Adam.html">Adam Smith</a>: <br><b>Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. </b>559-569<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.67"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RaskhodnikovaRSS07">BibTeX</a></font> <li><a name="CzumajS07" href="../../indices/a-tree/c/Czumaj:Artur.html">Artur Czumaj</a>, <a href="../../indices/a-tree/s/Sohler:Christian.html">Christian Sohler</a>: <br><b>Testing Expansion in Bounded-Degree Graphs. </b>570-578<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.69"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CzumajS07">BibTeX</a></font> <li><a name="FischerMS07" href="../../indices/a-tree/f/Fischer:Eldar.html">Eldar Fischer</a>, <a href="../../indices/a-tree/m/Matsliah:Arie.html">Arie Matsliah</a>, <a href="../../indices/a-tree/s/Shapira:Asaf.html">Asaf Shapira</a>: <br><b>Approximate Hypergraph Partitioning and Applications. </b>579-589<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.11"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FischerMS07">BibTeX</a></font> <li><a name="KaufmanS07" href="../../indices/a-tree/k/Kaufman:Tali.html">Tali Kaufman</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: <br><b>Sparse Random Linear Codes are Locally Decodable and Testable. </b>590-600<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.65"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KaufmanS07">BibTeX</a></font> <li><a name="GargK07" href="../../indices/a-tree/g/Garg:Naveen.html">Naveen Garg</a>, <a href="../../indices/a-tree/k/Kumar:Amit.html">Amit Kumar</a>: <br><b>Minimizing Average Flow-time : Upper and Lower Bounds. </b>603-613<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.42"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GargK07">BibTeX</a></font> <li><a name="BansalCKPSS07" href="../../indices/a-tree/b/Bansal:Nikhil.html">Nikhil Bansal</a>, <a href="../../indices/a-tree/c/Chan:Ho=Leung.html">Ho-Leung Chan</a>, <a href="../../indices/a-tree/k/Khandekar:Rohit.html">Rohit Khandekar</a>, <a href="../../indices/a-tree/p/Pruhs:Kirk.html">Kirk Pruhs</a>, <a href="../../indices/a-tree/s/Stein:Clifford.html">Clifford Stein</a>, <a href="../../indices/a-tree/s/Schieber:Baruch.html">Baruch Schieber</a>: <br><b>Non-Preemptive Min-Sum Scheduling with Resource Augmentation. </b>614-624<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.46"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BansalCKPSS07">BibTeX</a></font> <li><a name="CharikarMM07" href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/m/Makarychev:Konstantin.html">Konstantin Makarychev</a>, <a href="../../indices/a-tree/m/Makarychev:Yury.html">Yury Makarychev</a>: <br><b>On the Advantage over Random for Maximum Acyclic Subgraph. </b>625-633<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.47"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CharikarMM07">BibTeX</a></font> <li><a name="AntonakopoulosCSZ07" href="../../indices/a-tree/a/Antonakopoulos:Spyridon.html">Spyridon Antonakopoulos</a>, <a href="../../indices/a-tree/c/Chekuri:Chandra.html">Chandra Chekuri</a>, <a href="../../indices/a-tree/s/Shepherd:F=_Bruce.html">F. Bruce Shepherd</a>, <a href="../../indices/a-tree/z/Zhang:Lisa.html">Lisa Zhang</a>: <br><b>Buy-at-Bulk Network Design with Protection. </b>634-644<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.17"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AntonakopoulosCSZ07">BibTeX</a></font> <li><a name="BonehGH07" href="../../indices/a-tree/b/Boneh:Dan.html">Dan Boneh</a>, <a href="../../indices/a-tree/g/Gentry:Craig.html">Craig Gentry</a>, <a href="../../indices/a-tree/h/Hamburg:Michael.html">Michael Hamburg</a>: <br><b>Space-Efficient Identity Based Encryption Without Pairings. </b>647-657<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.64"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BonehGH07">BibTeX</a></font> <li><a name="GarayKKO07" href="../../indices/a-tree/g/Garay:Juan_A=.html">Juan A. Garay</a>, <a href="../../indices/a-tree/k/Katz:Jonathan.html">Jonathan Katz</a>, <a href="../../indices/a-tree/k/Koo:Chiu=Yuen.html">Chiu-Yuen Koo</a>, <a href="../../indices/a-tree/o/Ostrovsky:Rafail.html">Rafail Ostrovsky</a>: <br><b>Round Complexity of Authenticated Broadcast with a Dishonest Majority. </b>658-668<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.61"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GarayKKO07">BibTeX</a></font> <li><a name="HaitnerHRS07" href="../../indices/a-tree/h/Haitner:Iftach.html">Iftach Haitner</a>, <a href="../../indices/a-tree/h/Hoch:Jonathan_J=.html">Jonathan J. Hoch</a>, <a href="../../indices/a-tree/r/Reingold:Omer.html">Omer Reingold</a>, <a href="../../indices/a-tree/s/Segev:Gil.html">Gil Segev</a>: <br><b>Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments. </b>669-679<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.27"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HaitnerHRS07">BibTeX</a></font> <li><a name="BarakM07" href="../../indices/a-tree/b/Barak:Boaz.html">Boaz Barak</a>, <a href="../../indices/a-tree/m/Mahmoody=Ghidary:Mohammad.html">Mohammad Mahmoody-Ghidary</a>: <br><b>Lower Bounds on Signatures From Symmetric Primitives. </b>680-688<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.38"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BarakM07">BibTeX</a></font> <li><a name="Chlamtac07" href="../../indices/a-tree/c/Chlamtac:Eden.html">Eden Chlamtac</a>: <br><b>Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations. </b>691-701<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.13"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Chlamtac07">BibTeX</a></font> <li><a name="GeorgiouMPT07" href="../../indices/a-tree/g/Georgiou:Konstantinos.html">Konstantinos Georgiou</a>, <a href="../../indices/a-tree/m/Magen:Avner.html">Avner Magen</a>, <a href="../../indices/a-tree/p/Pitassi:Toniann.html">Toniann Pitassi</a>, <a href="../../indices/a-tree/t/Tourlakis:Iannis.html">Iannis Tourlakis</a>: <br><b>Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy. </b>702-712<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.34"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GeorgiouMPT07">BibTeX</a></font> <li><a name="CharikarMM07a" href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/m/Makarychev:Konstantin.html">Konstantin Makarychev</a>, <a href="../../indices/a-tree/m/Makarychev:Yury.html">Yury Makarychev</a>: <br><b>Local Global Tradeoffs in Metric Embeddings. </b>713-723<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.37"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CharikarMM07a">BibTeX</a></font> <li><a name="AndoniK07" href="../../indices/a-tree/a/Andoni:Alexandr.html">Alexandr Andoni</a>, <a href="../../indices/a-tree/k/Krauthgamer:Robert.html">Robert Krauthgamer</a>: <br><b>The Computational Hardness of Estimating Edit Distance [Extended Abstract]. </b>724-734<br><a href="http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.71"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AndoniK07">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
