focs2003.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>FOCS 2003</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>44. <a href="index.html">FOCS</a> 2003:
Cambridge,
MA,
USA</h1> 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, Proceedings.
IEEE Computer Society 2003, ISBN 0-7695-2040-5 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/2003">BibTeX</a></font>
<pre>@proceedings{<a href="../../about/bibtex.html">DBLP</a>:conf/focs/2003,
title = {44th Symposium on Foundations of Computer Science (FOCS 2003),
11-14 October 2003, Cambridge, MA, USA, Proceedings},
booktitle = {FOCS},
publisher = {IEEE Computer Society},
year = {2003},
isbn = {0-7695-2040-5},
bibsource = {DBLP, http://dblp.uni-trier.de}
}
</pre>
<h2>Tutorial 1</h2>
<ul>
<li><a name="Blum03" href="../../indices/a-tree/b/Blum:Avrim.html">Avrim Blum</a>:
<br><b>Machine Learning: My Favorite Results, Directions, and Open Problems.
</b>2-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400002.pdf"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Blum03">BibTeX</a></font>
</ul>
<h2>Tutorial 2</h2>
<ul>
<li><a name="Randall03" href="../../indices/a-tree/r/Randall:Dana.html">Dana Randall</a>:
<br><b>Mixing.
</b>4-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400004abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Randall03">BibTeX</a></font>
</ul>
<h2>Tutorial 3</h2>
<ul>
<li><a name="Upfal03" href="../../indices/a-tree/u/Upfal:Eli.html">Eli Upfal</a>:
<br><b>Performance Analysis of Dynamic Network Processes.
</b>18-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400018abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Upfal03">BibTeX</a></font>
</ul>
<h2>Session 1</h2>
<ul>
<li><a name="CornuejolsLV03" href="../../indices/a-tree/c/Cornu=eacute=jols:G=eacute=rard.html">Gérard Cornuéjols</a>, <a href="../../indices/a-tree/l/Liu:Xinming.html">Xinming Liu</a>, <a href="../../indices/a-tree/v/Vuskovic:Kristina.html">Kristina Vuskovic</a>:
<br><b>A Polynomial Algorithm for Recognizing Perfect Graphs.
</b>20-27<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400020abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CornuejolsLV03">BibTeX</a></font>
<li><a name="MihailPS03" href="../../indices/a-tree/m/Mihail:Milena.html">Milena Mihail</a>, <a href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>, <a href="../../indices/a-tree/s/Saberi:Amin.html">Amin Saberi</a>:
<br><b>On Certain Connectivity Properties of the Internet Topology.
</b>28-35<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400028abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MihailPS03">BibTeX</a></font>
<li><a name="ChaudhuriGRT03" href="../../indices/a-tree/c/Chaudhuri:Kamalika.html">Kamalika Chaudhuri</a>, <a href="../../indices/a-tree/g/Godfrey:Brighten.html">Brighten Godfrey</a>, <a href="../../indices/a-tree/r/Rao:Satish.html">Satish Rao</a>, <a href="../../indices/a-tree/t/Talwar:Kunal.html">Kunal Talwar</a>:
<br><b>Paths, Trees, and Minimum Latency Tours.
</b>36-45<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400036abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChaudhuriGRT03">BibTeX</a></font>
<li><a name="BlumCKLMM03" href="../../indices/a-tree/b/Blum:Avrim.html">Avrim Blum</a>, <a href="../../indices/a-tree/c/Chawla:Shuchi.html">Shuchi Chawla</a>, <a href="../../indices/a-tree/k/Karger:David_R=.html">David R. Karger</a>, <a href="../../indices/a-tree/l/Lane:Terran.html">Terran Lane</a>, <a href="../../indices/a-tree/m/Meyerson:Adam.html">Adam Meyerson</a>, <a href="../../indices/a-tree/m/Minkoff:Maria.html">Maria Minkoff</a>:
<br><b>Approximation Algorithms for Orienteering and Discounted-Reward TSP.
</b>46-55<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400046abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BlumCKLMM03">BibTeX</a></font>
<li><a name="KaplanLSS03" href="../../indices/a-tree/k/Kaplan:Haim.html">Haim Kaplan</a>, <a href="../../indices/a-tree/l/Lewenstein:Moshe.html">Moshe Lewenstein</a>, <a href="../../indices/a-tree/s/Shafrir:Nira.html">Nira Shafrir</a>, <a href="../../indices/a-tree/s/Sviridenko:Maxim.html">Maxim Sviridenko</a>:
<br><b>Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs.
</b>56-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400056abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KaplanLSS03">BibTeX</a></font>
</ul>
<h2>Session 2</h2>
<ul>
<li><a name="GoldreichGN03" href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/n/Nussboim:Asaf.html">Asaf Nussboim</a>:
<br><b>On the Implementation of Huge Random Objects.
</b>68-79<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400068abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldreichGN03">BibTeX</a></font>
<li><a name="MicaliRK03" href="../../indices/a-tree/m/Micali:Silvio.html">Silvio Micali</a>, <a href="../../indices/a-tree/r/Rabin:Michael_O=.html">Michael O. Rabin</a>, <a href="../../indices/a-tree/k/Kilian:Joe.html">Joe Kilian</a>:
<br><b>Zero-Knowledge Sets.
</b>80-91<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400080abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MicaliRK03">BibTeX</a></font>
<li><a name="KampZ03" href="../../indices/a-tree/k/Kamp:Jesse.html">Jesse Kamp</a>, <a href="../../indices/a-tree/z/Zuckerman:David.html">David Zuckerman</a>:
<br><b>Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography.
</b>92-101<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400092abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KampZ03">BibTeX</a></font>
<li><a name="GoldwasserK03" href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/k/Kalai:Yael_Tauman.html">Yael Tauman Kalai</a>:
<br><b>On the (In)security of the Fiat-Shamir Paradigm.
</b>102-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400102abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldwasserK03">BibTeX</a></font>
</ul>
<h2>Session 3</h2>
<ul>
<li><a name="BabaiSS03" href="../../indices/a-tree/b/Babai:L=aacute=szl=oacute=.html">László Babai</a>, <a href="../../indices/a-tree/s/Shpilka:Amir.html">Amir Shpilka</a>, <a href="../../indices/a-tree/s/Stefankovic:Daniel.html">Daniel Stefankovic</a>:
<br><b>Locally Testable Cyclic Codes.
</b>116-125<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400116abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BabaiSS03">BibTeX</a></font>
<li><a name="Trevisa03" href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>:
<br><b>List-Decoding Using The XOR Lemma.
</b>126-135<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400126abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Trevisa03">BibTeX</a></font>
<li><a name="MosselST03" href="../../indices/a-tree/m/Mossel:Elchanan.html">Elchanan Mossel</a>, <a href="../../indices/a-tree/s/Shpilka:Amir.html">Amir Shpilka</a>, <a href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>:
<br><b>On e-Biased Generators in NC0.
</b>136-145<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400136abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MosselST03">BibTeX</a></font>
<li><a name="AkaviaGS03" href="../../indices/a-tree/a/Akavia:Adi.html">Adi Akavia</a>, <a href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/s/Safra:Shmuel.html">Shmuel Safra</a>:
<br><b>Proving Hard-Core Predicates Using List Decoding.
</b>146-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400146abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AkaviaGS03">BibTeX</a></font>
</ul>
<h2>Session 4</h2>
<ul>
<li><a name="BhattacharjeeG03" href="../../indices/a-tree/b/Bhattacharjee:Rajat.html">Rajat Bhattacharjee</a>, <a href="../../indices/a-tree/g/Goel:Ashish.html">Ashish Goel</a>:
<br><b>Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model.
</b>160-167<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400160abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BhattacharjeeG03">BibTeX</a></font>
<li><a name="NairPS03" href="../../indices/a-tree/n/Nair:Chandra.html">Chandra Nair</a>, <a href="../../indices/a-tree/p/Prabhakar:Balaji.html">Balaji Prabhakar</a>, <a href="../../indices/a-tree/s/Sharma:Mayank.html">Mayank Sharma</a>:
<br><b>Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Finite Random Assignment Problem.
</b>168-178<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400168abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NairPS03">BibTeX</a></font>
<li><a name="OrlitskySZ03" href="../../indices/a-tree/o/Orlitsky:Alon.html">Alon Orlitsky</a>, <a href="../../indices/a-tree/s/Santhanam:Narayana_P=.html">Narayana P. Santhanam</a>, <a href="../../indices/a-tree/z/Zhang:Junan.html">Junan Zhang</a>:
<br><b>Always Good Turing: Asymptotically Optimal Probability Estimation.
</b>179-188<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400179abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/OrlitskySZ03">BibTeX</a></font>
<li><a name="BshoutyMOS03" href="../../indices/a-tree/b/Bshouty:Nader_H=.html">Nader H. Bshouty</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>, <a href="../../indices/a-tree/s/Servedio:Rocco_A=.html">Rocco A. Servedio</a>:
<br><b>Learning DNF from Random Walks.
</b>189-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400189abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BshoutyMOS03">BibTeX</a></font>
</ul>
<h2>Session 5</h2>
<ul>
<li><a name="AaronsonA03" href="../../indices/a-tree/a/Aaronson:Scott.html">Scott Aaronson</a>, <a href="../../indices/a-tree/a/Ambainis:Andris.html">Andris Ambainis</a>:
<br><b>Quantum Search of Spatial Regions.
</b>200-209<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400200abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AaronsonA03">BibTeX</a></font>
<li><a name="AharonovR03" 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>A Lattice Problem in Quantum NP.
</b>210-219<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400210abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AharonovR03">BibTeX</a></font>
<li><a name="JainRS03" href="../../indices/a-tree/j/Jain:Rahul.html">Rahul Jain</a>, <a href="../../indices/a-tree/r/Radhakrishnan:Jaikumar.html">Jaikumar Radhakrishnan</a>, <a href="../../indices/a-tree/s/Sen:Pranab.html">Pranab Sen</a>:
<br><b>A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness.
</b>220-229<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400220abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/JainRS03">BibTeX</a></font>
<li><a name="Ambainis03" href="../../indices/a-tree/a/Ambainis:Andris.html">Andris Ambainis</a>:
<br><b>Polynomial Degree vs. Quantum Query Complexity.
</b>230-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400230abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ambainis03">BibTeX</a></font>
</ul>
<h2>Session 6</h2>
<ul>
<li><a name="FranceschiniG03" href="../../indices/a-tree/f/Franceschini:Gianni.html">Gianni Franceschini</a>, <a href="../../indices/a-tree/g/Geffert:Viliam.html">Viliam Geffert</a>:
<br><b>An In-Place Sorting with O(n log n) Comparisons and O(n) Moves.
</b>242-250<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400242abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FranceschiniG03">BibTeX</a></font>
<li><a name="HonSS03" href="../../indices/a-tree/h/Hon:Wing=Kai.html">Wing-Kai Hon</a>, <a href="../../indices/a-tree/s/Sadakane:Kunihiko.html">Kunihiko Sadakane</a>, <a href="../../indices/a-tree/s/Sung:Wing=Kin.html">Wing-Kin Sung</a>:
<br><b>Breaking a Time-and-Space Barrier in Constructing Full-Text Indices.
</b>251-260<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400251abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HonSS03">BibTeX</a></font>
<li><a name="ArgeZ03" href="../../indices/a-tree/a/Arge:Lars.html">Lars Arge</a>, <a href="../../indices/a-tree/z/Zeh:Norbert.html">Norbert Zeh</a>:
<br><b>I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs.
</b>261-270<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400261abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ArgeZ03">BibTeX</a></font>
<li><a name="BenderBFGHHIL03" href="../../indices/a-tree/b/Bender:Michael_A=.html">Michael A. Bender</a>, <a href="../../indices/a-tree/b/Brodal:Gerth_St=oslash=lting.html">Gerth Stølting Brodal</a>, <a href="../../indices/a-tree/f/Fagerberg:Rolf.html">Rolf Fagerberg</a>, <a href="../../indices/a-tree/g/Ge:Dongdong.html">Dongdong Ge</a>, <a href="../../indices/a-tree/h/He:Simai.html">Simai He</a>, <a href="../../indices/a-tree/h/Hu:Haodong.html">Haodong Hu</a>, <a href="../../indices/a-tree/i/Iacono:John.html">John Iacono</a>, <a href="../../indices/a-tree/l/L=oacute=pez=Ortiz:Alejandro.html">Alejandro López-Ortiz</a>:
<br><b>The Cost of Cache-Oblivious Searching.
</b>271-282<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400271abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BenderBFGHHIL03">BibTeX</a></font>
<li><a name="IndykW03" href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>, <a href="../../indices/a-tree/w/Woodruff:David_P=.html">David P. Woodruff</a>:
<br><b>Tight Lower Bounds for the Distinct Elements Problem.
</b>283-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400283abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/IndykW03">BibTeX</a></font>
</ul>
<h2>Session 7</h2>
<ul>
<li><a name="Khot03" href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>:
<br><b>Hardness of Approximating the Shortest Vector Problem in High Lp Norms.
</b>290-297<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400290abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Khot03">BibTeX</a></font>
<li><a name="Alekhnovich03" href="../../indices/a-tree/a/Alekhnovich:Michael.html">Michael Alekhnovich</a>:
<br><b>More on Average Case vs Approximation Complexity.
</b>298-307<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400298abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Alekhnovich03">BibTeX</a></font>
<li><a name="BogdanovT03" href="../../indices/a-tree/b/Bogdanov:Andrej.html">Andrej Bogdanov</a>, <a href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>:
<br><b>On Worst-Case to Average-Case Reductions for NP Problems.
</b>308-317<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400308abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BogdanovT03">BibTeX</a></font>
<li><a name="Buresh-OppenheimGHMP03" href="../../indices/a-tree/b/Buresh=Oppenheim:Josh.html">Josh Buresh-Oppenheim</a>, <a href="../../indices/a-tree/g/Galesi:Nicola.html">Nicola Galesi</a>, <a href="../../indices/a-tree/h/Hoory:Shlomo.html">Shlomo Hoory</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>:
<br><b>Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua.
</b>318-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400318abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Buresh-OppenheimGHMP03">BibTeX</a></font>
</ul>
<h2>Session 8</h2>
<ul>
<li><a name="MolloyS03" href="../../indices/a-tree/m/Molloy:Michael.html">Michael Molloy</a>, <a href="../../indices/a-tree/s/Salavatipour:Mohammad_R=.html">Mohammad R. Salavatipour</a>:
<br><b>The Resolution Complexity of Random Constraint Satisfaction Problems.
</b>330-339<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400330abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MolloyS03">BibTeX</a></font>
<li><a name="BacchusDP03" href="../../indices/a-tree/b/Bacchus:Fahiem.html">Fahiem Bacchus</a>, <a href="../../indices/a-tree/d/Dalmao:Shannon.html">Shannon Dalmao</a>, <a href="../../indices/a-tree/p/Pitassi:Toniann.html">Toniann Pitassi</a>:
<br><b>Algorithms and Complexity Results for #SAT and Bayesian Inference.
</b>340-351<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400340abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BacchusDP03">BibTeX</a></font>
<li><a name="AlekhnovichB03" href="../../indices/a-tree/a/Alekhnovich:Michael.html">Michael Alekhnovich</a>, <a href="../../indices/a-tree/b/Ben=Sasson:Eli.html">Eli Ben-Sasson</a>:
<br><b>Linear Upper Bounds for Random Walk on Small Density Random 3-CNF.
</b>352-361<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400352abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlekhnovichB03">BibTeX</a></font>
<li><a name="AchlioptasNP03" href="../../indices/a-tree/a/Achlioptas:Dimitris.html">Dimitris Achlioptas</a>, <a href="../../indices/a-tree/n/Naor:Assaf.html">Assaf Naor</a>, <a href="../../indices/a-tree/p/Peres:Yuval.html">Yuval Peres</a>:
<br><b>On the Maximum Satisfiability of Random Formulas.
</b>362-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400362abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AchlioptasNP03">BibTeX</a></font>
</ul>
<h2>Session 9</h2>
<ul>
<li><a name="ImpagliazzoK03" href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/k/Kapron:Bruce_M=.html">Bruce M. Kapron</a>:
<br><b>Logics for Reasoning about Cryptographic Constructions.
</b>372-383<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400372abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ImpagliazzoK03">BibTeX</a></font>
<li><a name="BarakLV03" href="../../indices/a-tree/b/Barak:Boaz.html">Boaz Barak</a>, <a href="../../indices/a-tree/l/Lindell:Yehuda.html">Yehuda Lindell</a>, <a href="../../indices/a-tree/v/Vadhan:Salil_P=.html">Salil P. Vadhan</a>:
<br><b>Lower Bounds for Non-Black-Box Zero Knowledge.
</b>384-393<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400384abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BarakLV03">BibTeX</a></font>
<li><a name="Lindell03" href="../../indices/a-tree/l/Lindell:Yehuda.html">Yehuda Lindell</a>:
<br><b>General Composition and Universal Composability in Secure Multi-Party Computation.
</b>394-403<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400394abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Lindell03">BibTeX</a></font>
<li><a name="PassR03" 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>Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds.
</b>404-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400404abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PassR03">BibTeX</a></font>
</ul>
<h2>Session 10</h2>
<ul>
<li><a name="SpielmanT03" href="../../indices/a-tree/s/Spielman:Daniel_A=.html">Daniel A. Spielman</a>, <a href="../../indices/a-tree/t/Teng:Shang=Hua.html">Shang-Hua Teng</a>:
<br><b>Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(m<sup>1.31</sup>).
</b>416-427<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400416abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SpielmanT03">BibTeX</a></font>
<li><a name="BeimelW03" href="../../indices/a-tree/b/Beimel:Amos.html">Amos Beimel</a>, <a href="../../indices/a-tree/w/Weinreb:Enav.html">Enav Weinreb</a>:
<br><b>Separating the Power of Monotone Span Programs over Different Fields.
</b>428-437<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400428abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BeimelW03">BibTeX</a></font>
<li><a name="CohnU03" href="../../indices/a-tree/c/Cohn:Henry.html">Henry Cohn</a>, <a href="../../indices/a-tree/u/Umans:Christopher.html">Christopher Umans</a>:
<br><b>A Group-Theoretic Approach to Fast Matrix Multiplication.
</b>438-449<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400438abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CohnU03">BibTeX</a></font>
<li><a name="BhatnagarGL03" href="../../indices/a-tree/b/Bhatnagar:Nayantara.html">Nayantara Bhatnagar</a>, <a href="../../indices/a-tree/g/Gopalan:Parikshit.html">Parikshit Gopalan</a>, <a href="../../indices/a-tree/l/Lipton:Richard_J=.html">Richard J. Lipton</a>:
<br><b>Symmetric Polynomials over Z<sub>m</sub> and Simultaneous Communication Protocol.
</b>450-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400450abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BhatnagarGL03">BibTeX</a></font>
</ul>
<h2>Session 11</h2>
<ul>
<li><a name="BecchettiLMSV03" href="../../indices/a-tree/b/Becchetti:Luca.html">Luca Becchetti</a>, <a href="../../indices/a-tree/l/Leonardi:Stefano.html">Stefano Leonardi</a>, <a href="../../indices/a-tree/m/Marchetti=Spaccamela:Alberto.html">Alberto Marchetti-Spaccamela</a>, <a href="../../indices/a-tree/s/Sch=auml=fer:Guido.html">Guido Schäfer</a>, <a href="../../indices/a-tree/v/Vredeveld:Tjark.html">Tjark Vredeveld</a>:
<br><b>Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm.
</b>462-471<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400462abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BecchettiLMSV03">BibTeX</a></font>
<li><a name="AnagnostopoulosKU03" href="../../indices/a-tree/a/Anagnostopoulos:Aris.html">Aris Anagnostopoulos</a>, <a href="../../indices/a-tree/k/Kirsch:Adam.html">Adam Kirsch</a>, <a href="../../indices/a-tree/u/Upfal:Eli.html">Eli Upfal</a>:
<br><b>Stability and Efficiency of a Random Local Load Balancing Protocol.
</b>472-481<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400472abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AnagnostopoulosKU03">BibTeX</a></font>
<li><a name="KempeDG03" href="../../indices/a-tree/k/Kempe:David.html">David Kempe</a>, <a href="../../indices/a-tree/d/Dobra:Alin.html">Alin Dobra</a>, <a href="../../indices/a-tree/g/Gehrke:Johannes.html">Johannes Gehrke</a>:
<br><b>Gossip-Based Computation of Aggregate Information.
</b>482-491<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400482abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KempeDG03">BibTeX</a></font>
<li><a name="CzumajR03" href="../../indices/a-tree/c/Czumaj:Artur.html">Artur Czumaj</a>, <a href="../../indices/a-tree/r/Rytter:Wojciech.html">Wojciech Rytter</a>:
<br><b>Broadcasting Algorithms in Radio Networks with Unknown Topology.
</b>492-501<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400492abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CzumajR03">BibTeX</a></font>
<li><a name="AggarwalMSZ03" href="../../indices/a-tree/a/Aggarwal:Gagan.html">Gagan Aggarwal</a>, <a href="../../indices/a-tree/m/Motwani:Rajeev.html">Rajeev Motwani</a>, <a href="../../indices/a-tree/s/Shah:Devavrat.html">Devavrat Shah</a>, <a href="../../indices/a-tree/z/Zhu:An.html">An Zhu</a>:
<br><b>Switch Scheduling via Randomized Edge Coloring.
</b>502-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400502abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AggarwalMSZ03">BibTeX</a></font>
</ul>
<h2>Session 12</h2>
<ul>
<li><a name="BrinkmanC03" href="../../indices/a-tree/b/Brinkman:Bo.html">Bo Brinkman</a>, <a href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>:
<br><b>On the Impossibility of Dimension Reduction in l<sub>1</sub>.
</b>514-523<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400514abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BrinkmanC03">BibTeX</a></font>
<li><a name="CharikarGW03" href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/g/Guruswami:Venkatesan.html">Venkatesan Guruswami</a>, <a href="../../indices/a-tree/w/Wirth:Anthony.html">Anthony Wirth</a>:
<br><b>Clustering with Qualitative Information.
</b>524-533<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400524abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CharikarGW03">BibTeX</a></font>
<li><a name="GuptaKL03" href="../../indices/a-tree/g/Gupta:Anupam.html">Anupam Gupta</a>, <a 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>Bounded Geometries, Fractals, and Low-Distortion Embeddings.
</b>534-543<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400534abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GuptaKL03">BibTeX</a></font>
<li><a name="Chan03" href="../../indices/a-tree/c/Chan:Timothy_M=.html">Timothy M. Chan</a>:
<br><b>On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences.
</b>544-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400544abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Chan03">BibTeX</a></font>
</ul>
<h2>Session 13</h2>
<ul>
<li><a name="Grohe03" href="../../indices/a-tree/g/Grohe:Martin.html">Martin Grohe</a>:
<br><b>The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side.
</b>552-561<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400552abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Grohe03">BibTeX</a></font>
<li><a name="BulatovD03" href="../../indices/a-tree/b/Bulatov:Andrei_A=.html">Andrei A. Bulatov</a>, <a href="../../indices/a-tree/d/Dalmau:V=iacute=ctor.html">Víctor Dalmau</a>:
<br><b>Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem.
</b>562-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400562abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BulatovD03">BibTeX</a></font>
</ul>
<h2>Session 14</h2>
<ul>
<li><a name="LaviMN03" href="../../indices/a-tree/l/Lavi:Ron.html">Ron Lavi</a>, <a href="../../indices/a-tree/m/Mu=alem:Ahuva.html">Ahuva Mu'alem</a>, <a href="../../indices/a-tree/n/Nisan:Noam.html">Noam Nisan</a>:
<br><b>Towards a Characterization of Truthful Combinatorial Auctions.
</b>574-583<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400574abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LaviMN03">BibTeX</a></font>
<li><a name="PalT03" href="../../indices/a-tree/p/P=aacute=l:Martin.html">Martin Pál</a>, <a href="../../indices/a-tree/t/Tardos:=Eacute=va.html">Éva Tardos</a>:
<br><b>Group Strategyproof Mechanisms via Primal-Dual Algorithms.
</b>584-593<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400584abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PalT03">BibTeX</a></font>
<li><a name="KleinbergL03" href="../../indices/a-tree/k/Kleinberg:Robert_D=.html">Robert D. Kleinberg</a>, <a href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>:
<br><b>The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions.
</b>594-605<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400594abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KleinbergL03">BibTeX</a></font>
<li><a name="GuptaKPR03" href="../../indices/a-tree/g/Gupta:Anupam.html">Anupam Gupta</a>, <a href="../../indices/a-tree/k/Kumar:Amit.html">Amit Kumar</a>, <a href="../../indices/a-tree/p/P=aacute=l:Martin.html">Martin Pál</a>, <a href="../../indices/a-tree/r/Roughgarden:Tim.html">Tim Roughgarden</a>:
<br><b>Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem.
</b>606-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400606abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GuptaKPR03">BibTeX</a></font>
</ul>
<h2>Session 15</h2>
<ul>
<li><a name="HayesV03" 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>A Non-Markovian Coupling for Randomly Sampling Colorings.
</b>618-627<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400618abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HayesV03">BibTeX</a></font>
<li><a name="MartinelliSW03" href="../../indices/a-tree/m/Martinelli:Fabio.html">Fabio Martinelli</a>, <a href="../../indices/a-tree/s/Sinclair:Alistair.html">Alistair Sinclair</a>, <a href="../../indices/a-tree/w/Weitz:Dror.html">Dror Weitz</a>:
<br><b>The Ising Model on Trees: Boundary Conditions and Mixing Time.
</b>628-639<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400628abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MartinelliSW03">BibTeX</a></font>
<li><a name="LovaszV03a" 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>Logconcave Functions: Geometry and Efficient Sampling Algorithms.
</b>640-649<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400640abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LovaszV03a">BibTeX</a></font>
<li><a name="LovaszV03" 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>Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm.
</b>650-<br><a href="http://csdl.computer.org/comp/proceedings/focs/2003/2040/00/20400650abs.htm"><i>Electronic Edition</i></a> (link) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LovaszV03">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
