focs2004.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>FOCS 2004</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>45. <a href="index.html">FOCS</a> 2004: Rome, Italy</h1> 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings. IEEE Computer Society 2004, ISBN 0-7695-2228-9 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/2004">BibTeX</a></font> <h2>Session 1</h2> <ul> <li><a name="Mochon04" href="../../indices/a-tree/m/Mochon:Carlos.html">Carlos Mochon</a>: <br><b>Quantum Weak Coin-Flipping with Bias of 0.192. </b>2-11<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280002abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Mochon04">BibTeX</a></font> <li><a name="KlauckSW04" href="../../indices/a-tree/k/Klauck:Hartmut.html">Hartmut Klauck</a>, <a href="../../indices/a-tree/s/Spalek:Robert.html">Robert Spalek</a>, <a href="../../indices/a-tree/w/Wolf:Ronald_de.html">Ronald de Wolf</a>: <br><b>Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. </b>12-21<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280012abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KlauckSW04">BibTeX</a></font> <li><a name="Ambainis04" href="../../indices/a-tree/a/Ambainis:Andris.html">Andris Ambainis</a>: <br><b>Quantum Walk Algorithm for Element Distinctness. </b>22-31<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280022abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ambainis04">BibTeX</a></font> <li><a name="Szegedy04" href="../../indices/a-tree/s/Szegedy:Mario.html">Mario Szegedy</a>: <br><b>Quantum Speed-Up of Markov Chain Based Algorithms. </b>32-41<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280032abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Szegedy04">BibTeX</a></font> <li><a name="AharonovDKLLR04" href="../../indices/a-tree/a/Aharonov:Dorit.html">Dorit Aharonov</a>, <a href="../../indices/a-tree/d/Dam:Wim_van.html">Wim van Dam</a>, <a href="../../indices/a-tree/k/Kempe:Julia.html">Julia Kempe</a>, <a href="../../indices/a-tree/l/Landau:Zeph.html">Zeph Landau</a>, <a href="../../indices/a-tree/l/Lloyd:Seth.html">Seth Lloyd</a>, <a href="../../indices/a-tree/r/Regev:Oded.html">Oded Regev</a>: <br><b>Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. </b>42-51<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280042abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AharonovDKLLR04">BibTeX</a></font> </ul> <h2>Session 2</h2> <ul> <li><a name="CharikarW04" href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/w/Wirth:Anthony.html">Anthony Wirth</a>: <br><b>Maximizing Quadratic Programs: Extending Grothendieck's Inequality. </b>54-60<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280054abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CharikarW04">BibTeX</a></font> <li><a name="Lau04" href="../../indices/a-tree/l/Lau:Lap_Chi.html">Lap Chi Lau</a>: <br><b>An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem. </b>61-70<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280061abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Lau04">BibTeX</a></font> <li><a name="ChekuriKS04" href="../../indices/a-tree/c/Chekuri:Chandra.html">Chandra Chekuri</a>, <a href="../../indices/a-tree/k/Khanna:Sanjeev.html">Sanjeev Khanna</a>, <a href="../../indices/a-tree/s/Shepherd:F=_Bruce.html">F. Bruce Shepherd</a>: <br><b>Edge-Disjoint Paths in Planar Graphs. </b>71-80<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280071abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChekuriKS04">BibTeX</a></font> <li><a name="ChuzhoyGKN04" href="../../indices/a-tree/c/Chuzhoy:Julia.html">Julia Chuzhoy</a>, <a href="../../indices/a-tree/g/Guha:Sudipto.html">Sudipto Guha</a>, <a href="../../indices/a-tree/k/Khanna:Sanjeev.html">Sanjeev Khanna</a>, <a href="../../indices/a-tree/n/Naor:Joseph.html">Joseph Naor</a>: <br><b>Machine Minimization for Scheduling Jobs with Interval Constraints. </b>81-90<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280081abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChuzhoyGKN04">BibTeX</a></font> </ul> <h2>Session 3</h2> <ul> <li><a name="MatousekS04" href="../../indices/a-tree/m/Matousek:Jir=iacute=.html">Jirí Matousek</a>, <a href="../../indices/a-tree/s/Szab=oacute=:Tibor.html">Tibor Szabó</a>: <br><b>Random Edge Can Be Exponential on Abstract Cubes. </b>92-100<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280092abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MatousekS04">BibTeX</a></font> <li><a name="CharikarGK04" href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/g/Goemans:Michel_X=.html">Michel X. Goemans</a>, <a href="../../indices/a-tree/k/Karloff:Howard_J=.html">Howard J. Karloff</a>: <br><b>On the Integrality Ratio for Asymmetric TSP. </b>101-107<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280101abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CharikarGK04">BibTeX</a></font> <li><a name="ChuzhoyN04" href="../../indices/a-tree/c/Chuzhoy:Julia.html">Julia Chuzhoy</a>, <a href="../../indices/a-tree/n/Naor:Joseph.html">Joseph Naor</a>: <br><b>The Hardness of Metric Labeling. </b>108-114<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280108abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChuzhoyN04">BibTeX</a></font> <li><a name="Andrews04" href="../../indices/a-tree/a/Andrews:Matthew.html">Matthew Andrews</a>: <br><b>Hardness of Buy-at-Bulk Network Design. </b>115-124<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280115abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Andrews04">BibTeX</a></font> </ul> <h2>Session 4</h2> <ul> <li><a name="Khot04" href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>: <br><b>Hardness of Approximating the Shortest Vector Problem in Lattices. </b>126-135<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280126abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Khot04">BibTeX</a></font> <li><a name="Khot04a" href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>: <br><b>Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. </b>136-145<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280136abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Khot04a">BibTeX</a></font> <li><a name="KhotKMO04" 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/m/Mossel:Elchanan.html">Elchanan Mossel</a>, <a href="../../indices/a-tree/o/O=Donnell:Ryan.html">Ryan O'Donnell</a>: <br><b>Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? </b>146-154<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280146abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KhotKMO04">BibTeX</a></font> <li><a name="DinurR04" href="../../indices/a-tree/d/Dinur:Irit.html">Irit Dinur</a>, <a href="../../indices/a-tree/r/Reingold:Omer.html">Omer Reingold</a>: <br><b>Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem. </b>155-164<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280155abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DinurR04">BibTeX</a></font> </ul> <h2>Session 5</h2> <ul> <li><a name="ApplebaumIK04" href="../../indices/a-tree/a/Applebaum:Benny.html">Benny Applebaum</a>, <a href="../../indices/a-tree/i/Ishai:Yuval.html">Yuval Ishai</a>, <a href="../../indices/a-tree/k/Kushilevitz:Eyal.html">Eyal Kushilevitz</a>: <br><b>Cryptography in NC<sup>0</sup>. </b>166-175<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280166abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ApplebaumIK04">BibTeX</a></font> <li><a name="Vadhan04" href="../../indices/a-tree/v/Vadhan:Salil_P=.html">Salil P. Vadhan</a>: <br><b>An Unconditional Study of Computational Zero Knowledge. </b>176-185<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280176abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Vadhan04">BibTeX</a></font> <li><a name="BarakCNP04" href="../../indices/a-tree/b/Barak:Boaz.html">Boaz Barak</a>, <a href="../../indices/a-tree/c/Canetti:Ran.html">Ran Canetti</a>, <a href="../../indices/a-tree/n/Nielsen:Jesper_Buus.html">Jesper Buus Nielsen</a>, <a href="../../indices/a-tree/p/Pass:Rafael.html">Rafael Pass</a>: <br><b>Universally Composable Protocols with Relaxed Set-Up Assumptions. </b>186-195<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280186abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BarakCNP04">BibTeX</a></font> <li><a name="DodisOPS04" href="../../indices/a-tree/d/Dodis:Yevgeniy.html">Yevgeniy Dodis</a>, <a href="../../indices/a-tree/o/Ong:Shien_Jin.html">Shien Jin Ong</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>On the (Im)possibility of Cryptography with Imperfect Randomness. </b>196-205<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280196abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DodisOPS04">BibTeX</a></font> </ul> <h2>Session 6</h2> <ul> <li><a name="DeanGV04" href="../../indices/a-tree/d/Dean:Brian_C=.html">Brian C. Dean</a>, <a href="../../indices/a-tree/g/Goemans:Michel_X=.html">Michel X. Goemans</a>, <a href="../../indices/a-tree/v/Vondr=aacute=k:Jan.html">Jan Vondrák</a>: <br><b>Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. </b>208-217<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280208abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DeanGV04">BibTeX</a></font> <li><a name="GuptaRS04" href="../../indices/a-tree/g/Gupta:Anupam.html">Anupam Gupta</a>, <a href="../../indices/a-tree/r/Ravi:R=.html">R. Ravi</a>, <a href="../../indices/a-tree/s/Sinha:Amitabh.html">Amitabh Sinha</a>: <br><b>An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design. </b>218-227<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280218abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GuptaRS04">BibTeX</a></font> <li><a name="ShmoysS04" href="../../indices/a-tree/s/Shmoys:David_B=.html">David B. Shmoys</a>, <a href="../../indices/a-tree/s/Swamy:Chaitanya.html">Chaitanya Swamy</a>: <br><b>Stochastic Optimization is (Almost) as easy as Deterministic Optimization. </b>228-237<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280228abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ShmoysS04">BibTeX</a></font> <li><a name="AroraHK04" 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>0(sqrt (log n)) Approximation to SPARSEST CUT in Õ(n<sup>2</sup>) Time. </b>238-247<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280238abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AroraHK04">BibTeX</a></font> <li><a name="MuchaS04" href="../../indices/a-tree/m/Mucha:Marcin.html">Marcin Mucha</a>, <a href="../../indices/a-tree/s/Sankowski:Piotr.html">Piotr Sankowski</a>: <br><b>Maximum Matchings via Gaussian Elimination. </b>248-255<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280248abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MuchaS04">BibTeX</a></font> </ul> <h2>Session 7</h2> <ul> <li><a name="SavaniS04" href="../../indices/a-tree/s/Savani:Rahul.html">Rahul Savani</a>, <a href="../../indices/a-tree/s/Stengel:Bernhard_von.html">Bernhard von Stengel</a>: <br><b>Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game. </b>258-267<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280258abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SavaniS04">BibTeX</a></font> <li><a name="KarakostasK04" href="../../indices/a-tree/k/Karakostas:George.html">George Karakostas</a>, <a href="../../indices/a-tree/k/Kolliopoulos:Stavros_G=.html">Stavros G. Kolliopoulos</a>: <br><b>Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users. </b>268-276<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280268abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KarakostasK04">BibTeX</a></font> <li><a name="FleischerJM04" href="../../indices/a-tree/f/Fleischer:Lisa.html">Lisa Fleischer</a>, <a href="../../indices/a-tree/j/Jain:Kamal.html">Kamal Jain</a>, <a href="../../indices/a-tree/m/Mahdian:Mohammad.html">Mohammad Mahdian</a>: <br><b>Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games. </b>277-285<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280277abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FleischerJM04">BibTeX</a></font> <li><a name="Jain04" href="../../indices/a-tree/j/Jain:Kamal.html">Kamal Jain</a>: <br><b>A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities. </b>286-294<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280286abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Jain04">BibTeX</a></font> <li><a name="AnshelevichDKTWR04" href="../../indices/a-tree/a/Anshelevich:Elliot.html">Elliot Anshelevich</a>, <a href="../../indices/a-tree/d/Dasgupta:Anirban.html">Anirban Dasgupta</a>, <a href="../../indices/a-tree/k/Kleinberg:Jon_M=.html">Jon M. Kleinberg</a>, <a href="../../indices/a-tree/t/Tardos:=Eacute=va.html">Éva Tardos</a>, <a href="../../indices/a-tree/w/Wexler:Tom.html">Tom Wexler</a>, <a href="../../indices/a-tree/r/Roughgarden:Tim.html">Tim Roughgarden</a>: <br><b>The Price of Stability for Network Design with Fair Cost Allocation. </b>295-304<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280295abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AnshelevichDKTWR04">BibTeX</a></font> </ul> <h2>Session 8</h2> <ul> <li><a name="Valiant04" href="../../indices/a-tree/v/Valiant:Leslie_G=.html">Leslie G. Valiant</a>: <br><b>Holographic Algorithms (Extended Abstract). </b>306-315<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280306abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Valiant04">BibTeX</a></font> <li><a name="FortnowS04" href="../../indices/a-tree/f/Fortnow:Lance.html">Lance Fortnow</a>, <a href="../../indices/a-tree/s/Santhanam:Rahul.html">Rahul Santhanam</a>: <br><b>Hierarchy Theorems for Probabilistic Polynomial Time. </b>316-324<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280316abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FortnowS04">BibTeX</a></font> <li><a name="Langberg04" href="../../indices/a-tree/l/Langberg:Michael.html">Michael Langberg</a>: <br><b>Private Codes or Succinct Random Codes That Are (Almost) Perfect. </b>325-334<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280325abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Langberg04">BibTeX</a></font> <li><a name="ChengW04" href="../../indices/a-tree/c/Cheng:Qi.html">Qi Cheng</a>, <a href="../../indices/a-tree/w/Wan:Daqing.html">Daqing Wan</a>: <br><b>On the List and Bounded Distance Decodibility of the Reed-Solomon Codes (Extended Abstract). </b>335-341<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280335abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChengW04">BibTeX</a></font> </ul> <h2>Session 9</h2> <ul> <li><a name="Raz04" href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>: <br><b>Multilinear-NC neq Multilinear-NC. </b>344-351<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280344abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Raz04">BibTeX</a></font> <li><a name="ChienS04" href="../../indices/a-tree/c/Chien:Steve.html">Steve Chien</a>, <a href="../../indices/a-tree/s/Sinclair:Alistair.html">Alistair Sinclair</a>: <br><b>Algebras with Polynomial Identities and Computing the Determinant. </b>352-361<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280352abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChienS04">BibTeX</a></font> <li><a name="AharonovR04" href="../../indices/a-tree/a/Aharonov:Dorit.html">Dorit Aharonov</a>, <a href="../../indices/a-tree/r/Regev:Oded.html">Oded Regev</a>: <br><b>Lattice Problems in NP cap coNP. </b>362-371<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280362abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AharonovR04">BibTeX</a></font> <li><a name="MicciancioR04" href="../../indices/a-tree/m/Micciancio:Daniele.html">Daniele Micciancio</a>, <a href="../../indices/a-tree/r/Regev:Oded.html">Oded Regev</a>: <br><b>Worst-Case to Average-Case Reductions Based on Gaussian Measures. </b>372-381<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280372abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MicciancioR04">BibTeX</a></font> </ul> <h2>Session 10</h2> <ul> <li><a name="BarakIW04" href="../../indices/a-tree/b/Barak:Boaz.html">Boaz Barak</a>, <a href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: <br><b>Extracting Randomness Using Few Independent Sources. </b>384-393<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280384abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BarakIW04">BibTeX</a></font> <li><a name="GabizonRS04" href="../../indices/a-tree/g/Gabizon:Ariel.html">Ariel Gabizon</a>, <a href="../../indices/a-tree/r/Raz:Ran.html">Ran Raz</a>, <a href="../../indices/a-tree/s/Shaltiel:Ronen.html">Ronen Shaltiel</a>: <br><b>Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed. </b>394-403<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280394abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GabizonRS04">BibTeX</a></font> <li><a name="BiluL04" href="../../indices/a-tree/b/Bilu:Yonatan.html">Yonatan Bilu</a>, <a href="../../indices/a-tree/l/Linial:Nathan.html">Nathan Linial</a>: <br><b>Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap. </b>404-412<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280404abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BiluL04">BibTeX</a></font> <li><a name="KaufmanR04" href="../../indices/a-tree/k/Kaufman:Tali.html">Tali Kaufman</a>, <a href="../../indices/a-tree/r/Ron:Dana.html">Dana Ron</a>: <br><b>Testing Polynomials over General Fields. </b>413-422<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280413abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KaufmanR04">BibTeX</a></font> <li><a name="JutlaPRZ04" href="../../indices/a-tree/j/Jutla:Charanjit_S=.html">Charanjit S. Jutla</a>, <a href="../../indices/a-tree/p/Patthak:Anindya_C=.html">Anindya C. Patthak</a>, <a href="../../indices/a-tree/r/Rudra:Atri.html">Atri Rudra</a>, <a href="../../indices/a-tree/z/Zuckerman:David.html">David Zuckerman</a>: <br><b>Testing Low-Degree Polynomials over Prime Fields. </b>423-432<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280423abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/JutlaPRZ04">BibTeX</a></font> </ul> <h2>Session 11</h2> <ul> <li><a name="KrauthgamerLMN04" 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>, <a 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>Measured Descent: A New Embedding Method for Finite Metrics. </b>434-443<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280434abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KrauthgamerLMN04">BibTeX</a></font> <li><a name="KleinbergSW04" href="../../indices/a-tree/k/Kleinberg:Jon_M=.html">Jon M. Kleinberg</a>, <a href="../../indices/a-tree/s/Slivkins:Aleksandrs.html">Aleksandrs Slivkins</a>, <a href="../../indices/a-tree/w/Wexler:Tom.html">Tom Wexler</a>: <br><b>Triangulation and Embedding Using Small Sets of Beacons. </b>444-453<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280444abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KleinbergSW04">BibTeX</a></font> <li><a name="KumarSS04" href="../../indices/a-tree/k/Kumar:Amit.html">Amit Kumar</a>, <a href="../../indices/a-tree/s/Sabharwal:Yogish.html">Yogish Sabharwal</a>, <a href="../../indices/a-tree/s/Sen:Sandeep.html">Sandeep Sen</a>: <br><b>A Simple Linear Time (1+ ) -Approximation Algorithm for k-Means Clustering in Any Dimensions. </b>454-462<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280454abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KumarSS04">BibTeX</a></font> <li><a name="Halman04" href="../../indices/a-tree/h/Halman:Nir.html">Nir Halman</a>: <br><b>On the Power of Discrete and of Lexicographic Helly-Type Theorems. </b>463-472<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280463abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Halman04">BibTeX</a></font> <li><a name="ChakrabartiR04" href="../../indices/a-tree/c/Chakrabarti:Amit.html">Amit Chakrabarti</a>, <a href="../../indices/a-tree/r/Regev:Oded.html">Oded Regev</a>: <br><b>An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. </b>473-482<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280473abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChakrabartiR04">BibTeX</a></font> </ul> <h2>Session 12</h2> <ul> <li><a name="DemaineHIP04" href="../../indices/a-tree/d/Demaine:Erik_D=.html">Erik D. Demaine</a>, <a href="../../indices/a-tree/h/Harmon:Dion.html">Dion Harmon</a>, <a href="../../indices/a-tree/i/Iacono:John.html">John Iacono</a>, <a href="../../indices/a-tree/p/Patrascu:Mihai.html">Mihai Patrascu</a>: <br><b>Dynamic Optimality -- Almost. </b>484-490<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280484abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DemaineHIP04">BibTeX</a></font> <li><a name="FranceschiniG04" href="../../indices/a-tree/f/Franceschini:Gianni.html">Gianni Franceschini</a>, <a href="../../indices/a-tree/g/Grossi:Roberto.html">Roberto Grossi</a>: <br><b>No Sorting? Better Searching! </b>491-498<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280491abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FranceschiniG04">BibTeX</a></font> <li><a name="RodittyZ04" href="../../indices/a-tree/r/Roditty:Liam.html">Liam Roditty</a>, <a href="../../indices/a-tree/z/Zwick:Uri.html">Uri Zwick</a>: <br><b>Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs. </b>499-508<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280499abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RodittyZ04">BibTeX</a></font> <li><a name="Sankowski04" href="../../indices/a-tree/s/Sankowski:Piotr.html">Piotr Sankowski</a>: <br><b>Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract). </b>509-517<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280509abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Sankowski04">BibTeX</a></font> </ul> <h2>Session 13</h2> <ul> <li><a name="BansalKP04" href="../../indices/a-tree/b/Bansal:Nikhil.html">Nikhil Bansal</a>, <a href="../../indices/a-tree/k/Kimbrel:Tracy.html">Tracy Kimbrel</a>, <a href="../../indices/a-tree/p/Pruhs:Kirk.html">Kirk Pruhs</a>: <br><b>Dynamic Speed Scaling to Manage Energy and Temperature. </b>520-529<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280520abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BansalKP04">BibTeX</a></font> <li><a name="AugustineIS04" href="../../indices/a-tree/a/Augustine:John.html">John Augustine</a>, <a href="../../indices/a-tree/i/Irani:Sandy.html">Sandy Irani</a>, <a href="../../indices/a-tree/s/Swamy:Chaitanya.html">Chaitanya Swamy</a>: <br><b>Optimal Power-Down Strategies. </b>530-539<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280530abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AugustineIS04">BibTeX</a></font> <li><a name="AggarwalDRR04" href="../../indices/a-tree/a/Aggarwal:Gagan.html">Gagan Aggarwal</a>, <a href="../../indices/a-tree/d/Datar:Mayur.html">Mayur Datar</a>, <a href="../../indices/a-tree/r/Rajagopalan:Sridhar.html">Sridhar Rajagopalan</a>, <a href="../../indices/a-tree/r/Ruhl:Matthias.html">Matthias Ruhl</a>: <br><b>On the Streaming Model Augmented with a Sorting Primitive. </b>540-549<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280540abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AggarwalDRR04">BibTeX</a></font> <li><a name="Bar-YossefJKK04" href="../../indices/a-tree/b/Bar=Yossef:Ziv.html">Ziv Bar-Yossef</a>, <a href="../../indices/a-tree/j/Jayram:T=_S=.html">T. S. Jayram</a>, <a href="../../indices/a-tree/k/Krauthgamer:Robert.html">Robert Krauthgamer</a>, <a href="../../indices/a-tree/k/Kumar:Ravi.html">Ravi Kumar</a>: <br><b>Approximating Edit Distance Efficiently. </b>550-559<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280550abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Bar-YossefJKK04">BibTeX</a></font> </ul> <h2>Session 14</h2> <ul> <li><a name="GoldbergMP04" href="../../indices/a-tree/g/Goldberg:Leslie_Ann.html">Leslie Ann Goldberg</a>, <a href="../../indices/a-tree/m/Martin:Russell_A=.html">Russell A. Martin</a>, <a href="../../indices/a-tree/p/Paterson:Mike.html">Mike Paterson</a>: <br><b>trong Spatial Mixing for Lattice Graphs with Fewer Colours. </b>562-571<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280562abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldbergMP04">BibTeX</a></font> <li><a name="MosselPS04" href="../../indices/a-tree/m/Mossel:Elchanan.html">Elchanan Mossel</a>, <a href="../../indices/a-tree/p/Peres:Yuval.html">Yuval Peres</a>, <a href="../../indices/a-tree/s/Sinclair:Alistair.html">Alistair Sinclair</a>: <br><b>Shuffling by Semi-Random Transpositions. </b>572-581<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280572abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MosselPS04">BibTeX</a></font> <li><a name="DyerFHV04" href="../../indices/a-tree/d/Dyer:Martin_E=.html">Martin E. Dyer</a>, <a href="../../indices/a-tree/f/Frieze:Alan_M=.html">Alan M. Frieze</a>, <a href="../../indices/a-tree/h/Hayes:Thomas_P=.html">Thomas P. Hayes</a>, <a href="../../indices/a-tree/v/Vigoda:Eric.html">Eric Vigoda</a>: <br><b>Randomly Coloring Constant Degree Graphs. </b>582-589<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280582abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DyerFHV04">BibTeX</a></font> <li><a name="ConnamacherM04" href="../../indices/a-tree/c/Connamacher:Harold_S=.html">Harold S. Connamacher</a>, <a href="../../indices/a-tree/m/Molloy:Michael.html">Michael Molloy</a>: <br><b>The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem. </b>590-599<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280590abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ConnamacherM04">BibTeX</a></font> </ul> <h2>Session 15</h2> <ul> <li><a name="DasguptaHM04" 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/m/McSherry:Frank.html">Frank McSherry</a>: <br><b>Spectral Analysis of Random Graphs with Skewed Degree Distributions. </b>602-610<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280602abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DasguptaHM04">BibTeX</a></font> <li><a name="BishtBK04" href="../../indices/a-tree/b/Bisht:Laurence.html">Laurence Bisht</a>, <a href="../../indices/a-tree/b/Bshouty:Nader_H=.html">Nader H. Bshouty</a>, <a href="../../indices/a-tree/k/Khoury:Lawrance.html">Lawrance Khoury</a>: <br><b>Learning with Errors in Answers to Membership Queries. </b>611-620<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280611abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BishtBK04">BibTeX</a></font> <li><a name="AlekhnovichBFKP04" href="../../indices/a-tree/a/Alekhnovich:Michael.html">Michael Alekhnovich</a>, <a href="../../indices/a-tree/b/Braverman:Mark.html">Mark Braverman</a>, <a href="../../indices/a-tree/f/Feldman:Vitaly.html">Vitaly Feldman</a>, <a href="../../indices/a-tree/k/Klivans:Adam_R=.html">Adam R. Klivans</a>, <a href="../../indices/a-tree/p/Pitassi:Toniann.html">Toniann Pitassi</a>: <br><b>Learnability and Automatizability. </b>621-630<br><a href="http://csdl.computer.org/comp/proceedings/focs/2004/2228/00/22280621abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlekhnovichBFKP04">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
