Personal tools
You are here: Home → dblp → db → conf → stoc → stoc2003.html
 

stoc2003.html

Click here to view the file or click here to download the file

Size 42.8 kB - File type text/html

File contents

<html><head><title>STOC 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>35. <a href="index.html">STOC</a> 2003:
San Diego,
California,
USA</h1> Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA.
 ACM 2003, ISBN 1-58113-674-9 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/2003">BibTeX</a></font>
 <pre>@proceedings{<a href="../../about/bibtex.html">DBLP</a>:conf/stoc/2003,
  title     = {Proceedings of the 35th Annual ACM Symposium on Theory of Computing,
               June 9-11, 2003, San Diego, CA, USA},
  booktitle = {STOC},
  publisher = {ACM},
  year      = {2003},
  isbn      = {1-58113-674-9},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
</pre>
 
<h2>Session 1A</h2> 
<ul>
<li><a name="FriedlIMSS03" href="../../indices/a-tree/f/Friedl:Katalin.html">Katalin Friedl</a>, <a href="../../indices/a-tree/i/Ivanyos:G=aacute=bor.html">G&aacute;bor Ivanyos</a>, <a href="../../indices/a-tree/m/Magniez:Fr=eacute=d=eacute=ric.html">Fr&eacute;d&eacute;ric Magniez</a>, <a href="../../indices/a-tree/s/Santha:Miklos.html">Miklos Santha</a>, <a href="../../indices/a-tree/s/Sen:Pranab.html">Pranab Sen</a>:
<br><b>Hidden translation and orbit coset in quantum computing.
</b>1-9<br><a href="http://doi.acm.org/10.1145/780542.780544"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FriedlIMSS03">BibTeX</a></font>

<li><a name="Gurvits03" href="../../indices/a-tree/g/Gurvits:Leonid.html">Leonid Gurvits</a>:
<br><b>Classical deterministic complexity of Edmonds' Problem and quantum entanglement.
</b>10-19<br><a href="http://doi.acm.org/10.1145/780542.780545"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Gurvits03">BibTeX</a></font>

<li><a name="AharonovT03" href="../../indices/a-tree/a/Aharonov:Dorit.html">Dorit Aharonov</a>, <a href="../../indices/a-tree/t/Ta=Shma:Amnon.html">Amnon Ta-Shma</a>:
<br><b>Adiabatic quantum state generation and statistical zero knowledge.
</b>20-29<br><a href="http://doi.acm.org/10.1145/780542.780546"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AharonovT03">BibTeX</a></font>

</ul>
<h2>Session 1B</h2> 
<ul>
<li><a name="CharikarOP03" href="../../indices/a-tree/c/Charikar:Moses.html">Moses Charikar</a>, <a href="../../indices/a-tree/o/O=Callaghan:Liadan.html">Liadan O'Callaghan</a>, <a href="../../indices/a-tree/p/Panigrahy:Rina.html">Rina Panigrahy</a>:
<br><b>Better streaming algorithms for clustering problems.
</b>30-39<br><a href="http://doi.acm.org/10.1145/780542.780548"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CharikarOP03">BibTeX</a></font>

<li><a name="Plaxton03" href="../../indices/a-tree/p/Plaxton:C=_Greg.html">C. Greg Plaxton</a>:
<br><b>Approximation algorithms for hierarchical location problems.
</b>40-49<br><a href="http://doi.acm.org/10.1145/780542.780549"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Plaxton03">BibTeX</a></font>

<li><a name="VegaKKR03" href="../../indices/a-tree/v/Vega:Wenceslas_Fernandez_de_la.html">Wenceslas Fernandez de la Vega</a>, <a href="../../indices/a-tree/k/Karpinski:Marek.html">Marek Karpinski</a>, <a href="../../indices/a-tree/k/Kenyon:Claire.html">Claire Kenyon</a>, <a href="../../indices/a-tree/r/Rabani:Yuval.html">Yuval Rabani</a>:
<br><b>Approximation schemes for clustering problems.
</b>50-58<br><a href="http://doi.acm.org/10.1145/780542.780550"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/VegaKKR03">BibTeX</a></font>

</ul>
<h2>Session 2A</h2> 
<ul>
<li><a name="ChildsCDFGS03" href="../../indices/a-tree/c/Childs:Andrew_M=.html">Andrew M. Childs</a>, <a href="../../indices/a-tree/c/Cleve:Richard.html">Richard Cleve</a>, <a href="../../indices/a-tree/d/Deotto:Enrico.html">Enrico Deotto</a>, <a href="../../indices/a-tree/f/Farhi:Edward.html">Edward Farhi</a>, <a href="../../indices/a-tree/g/Gutmann:Sam.html">Sam Gutmann</a>, <a href="../../indices/a-tree/s/Spielman:Daniel_A=.html">Daniel A. Spielman</a>:
<br><b>Exponential algorithmic speedup by a quantum walk.
</b>59-68<br><a href="http://doi.acm.org/10.1145/780542.780552"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChildsCDFGS03">BibTeX</a></font>

<li><a name="Klauck03" href="../../indices/a-tree/k/Klauck:Hartmut.html">Hartmut Klauck</a>:
<br><b>Quantum time-space tradeoffs for sorting.
</b>69-76<br><a href="http://doi.acm.org/10.1145/780542.780553"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Klauck03">BibTeX</a></font>

<li><a name="Ya03" href="../../indices/a-tree/y/Ya:Andrew_Chi=Chih.html">Andrew Chi-Chih Ya</a>:
<br><b>On the power of quantum fingerprinting.
</b>77-81<br><a href="http://doi.acm.org/10.1145/780542.780554"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Ya03">BibTeX</a></font>

</ul>
<h2>Session 2B</h2> 
<ul>
<li><a name="AzarR03" href="../../indices/a-tree/a/Azar:Yossi.html">Yossi Azar</a>, <a href="../../indices/a-tree/r/Richter:Yossi.html">Yossi Richter</a>:
<br><b>Management of multi-queue switches in QoS networks.
</b>82-89<br><a href="http://doi.acm.org/10.1145/780542.780556"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AzarR03">BibTeX</a></font>

<li><a name="AmirKR03" href="../../indices/a-tree/a/Amir:Eyal.html">Eyal Amir</a>, <a href="../../indices/a-tree/k/Krauthgamer:Robert.html">Robert Krauthgamer</a>, <a href="../../indices/a-tree/r/Rao:Satish.html">Satish Rao</a>:
<br><b>Constant factor approximation of vertex-cuts in planar graphs.
</b>90-99<br><a href="http://doi.acm.org/10.1145/780542.780557"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AmirKR03">BibTeX</a></font>

<li><a name="AlonAA03" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/a/Azar:Yossi.html">Yossi Azar</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>The online set cover problem.
</b>100-105<br><a href="http://doi.acm.org/10.1145/780542.780558"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AlonAA03">BibTeX</a></font>

</ul>
<h2>Session 3A</h2> 
<ul>
<li><a name="KerenidisW03" href="../../indices/a-tree/k/Kerenidis:Iordanis.html">Iordanis Kerenidis</a>, <a href="../../indices/a-tree/w/Wolf:Ronald_de.html">Ronald de Wolf</a>:
<br><b>Exponential lower bound for 2-query locally decodable codes via a quantum argument.
</b>106-115<br><a href="http://doi.acm.org/10.1145/780542.780560"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KerenidisW03">BibTeX</a></font>

<li><a name="Tardo03" href="../../indices/a-tree/t/Tardos:G=aacute=bor.html">G&aacute;bor Tardos</a>:
<br><b>Optimal probabilistic fingerprint codes.
</b>116-125<br><a href="http://doi.acm.org/10.1145/780542.780561"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Tardo03">BibTeX</a></font>

<li><a name="GuruswamiI03" href="../../indices/a-tree/g/Guruswami:Venkatesan.html">Venkatesan Guruswami</a>, <a href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>:
<br><b>Linear time encodable and list decodable codes.
</b>126-135<br><a href="http://doi.acm.org/10.1145/780542.780562"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GuruswamiI03">BibTeX</a></font>

<li><a name="CoppersmithS03" href="../../indices/a-tree/c/Coppersmith:Don.html">Don Coppersmith</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>:
<br><b>Reconstructing curves in three (and higher) dimensional space from noisy data.
</b>136-142<br><a href="http://doi.acm.org/10.1145/780542.780563"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/CoppersmithS03">BibTeX</a></font>

</ul>
<h2>Session 3B</h2> 
<ul>
<li><a name="KowalikK03" href="../../indices/a-tree/k/Kowalik:Lukasz.html">Lukasz Kowalik</a>, <a href="../../indices/a-tree/k/Kurowski:Maciej.html">Maciej Kurowski</a>:
<br><b>Short path queries in planar graphs in constant time.
</b>143-148<br><a href="http://doi.acm.org/10.1145/780542.780565"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KowalikK03">BibTeX</a></font>

<li><a name="Thorup03" href="../../indices/a-tree/t/Thorup:Mikkel.html">Mikkel Thorup</a>:
<br><b>Integer priority queues with decrease key in constant time and the single source shortest paths problem.
</b>149-158<br><a href="http://doi.acm.org/10.1145/780542.780566"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Thorup03">BibTeX</a></font>

<li><a name="DemetrescuI03" href="../../indices/a-tree/d/Demetrescu:Camil.html">Camil Demetrescu</a>, <a href="../../indices/a-tree/i/Italiano:Giuseppe_F=.html">Giuseppe F. Italiano</a>:
<br><b>A new approach to dynamic all pairs shortest paths.
</b>159-166<br><a href="http://doi.acm.org/10.1145/780542.780567"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DemetrescuI03">BibTeX</a></font>

<li><a name="ColeH03" href="../../indices/a-tree/c/Cole:Richard.html">Richard Cole</a>, <a href="../../indices/a-tree/h/Hariharan:Ramesh.html">Ramesh Hariharan</a>:
<br><b>A fast algorithm for computing steiner edge connectivity.
</b>167-176<br><a href="http://doi.acm.org/10.1145/780542.780568"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ColeH03">BibTeX</a></font>

</ul>
<h2>Session 4A</h2> 
<ul>
<li><a name="RettingerW03" href="../../indices/a-tree/r/Rettinger:Robert.html">Robert Rettinger</a>, <a href="../../indices/a-tree/w/Weihrauch:Klaus.html">Klaus Weihrauch</a>:
<br><b>The computational complexity of some julia sets.
</b>177-185<br><a href="http://doi.acm.org/10.1145/780542.780570"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/RettingerW03">BibTeX</a></font>

<li><a name="SauerhoffW03" href="../../indices/a-tree/s/Sauerhoff:Martin.html">Martin Sauerhoff</a>, <a href="../../indices/a-tree/w/Woelfel:Philipp.html">Philipp Woelfel</a>:
<br><b>Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions.
</b>186-195<br><a href="http://doi.acm.org/10.1145/780542.780571"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/SauerhoffW03">BibTeX</a></font>

</ul>
<h2>Session 4B</h2> 
<ul>
<li><a name="KalaiS03" href="../../indices/a-tree/k/Kalai:Adam.html">Adam Kalai</a>, <a href="../../indices/a-tree/s/Servedio:Rocco_A=.html">Rocco A. Servedio</a>:
<br><b>Boosting in the presence of noise.
</b>195-205<br><a href="http://doi.acm.org/10.1145/780542.780573"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KalaiS03">BibTeX</a></font>

<li><a name="MosselOS03" 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 juntas.
</b>206-212<br><a href="http://doi.acm.org/10.1145/780542.780574"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MosselOS03">BibTeX</a></font>

</ul>
<h2>Session 5A</h2> 
<ul>
<li><a name="KimV03" href="../../indices/a-tree/k/Kim:Jeong_Han.html">Jeong Han Kim</a>, <a href="../../indices/a-tree/v/Vu:Van_H=.html">Van H. Vu</a>:
<br><b>Generating random regular graphs.
</b>213-222<br><a href="http://doi.acm.org/10.1145/780542.780576"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KimV03">BibTeX</a></font>

<li><a name="AchlioptasP03" href="../../indices/a-tree/a/Achlioptas:Dimitris.html">Dimitris Achlioptas</a>, <a href="../../indices/a-tree/p/Peres:Yuval.html">Yuval Peres</a>:
<br><b>The threshold for random k-SAT is 2<sup>k</sup> (ln 2 - O(k)).
</b>223-231<br><a href="http://doi.acm.org/10.1145/780542.780577"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AchlioptasP03">BibTeX</a></font>

<li><a name="BeierV03" href="../../indices/a-tree/b/Beier:Ren=eacute=.html">Ren&eacute; Beier</a>, <a href="../../indices/a-tree/v/V=ouml=cking:Berthold.html">Berthold V&ouml;cking</a>:
<br><b>Random knapsack in expected polynomial time.
</b>232-241<br><a href="http://doi.acm.org/10.1145/780542.780578"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BeierV03">BibTeX</a></font>

</ul>
<h2>Session 5B</h2> 
<ul>
<li><a name="BansalP03" href="../../indices/a-tree/b/Bansal:Nikhil.html">Nikhil Bansal</a>, <a href="../../indices/a-tree/p/Pruhs:Kirk.html">Kirk Pruhs</a>:
<br><b>Server scheduling in the L<sub>p</sub> norm: a rising tide lifts all boat.
</b>242-250<br><a href="http://doi.acm.org/10.1145/780542.780580"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BansalP03">BibTeX</a></font>

<li><a name="GeorgiouRS03" href="../../indices/a-tree/g/Georgiou:Chryssis.html">Chryssis Georgiou</a>, <a href="../../indices/a-tree/r/Russell:Alexander.html">Alexander Russell</a>, <a href="../../indices/a-tree/s/Shvartsman:Alexander_A=.html">Alexander A. Shvartsman</a>:
<br><b>Work-competitive scheduling for cooperative computing with dynamic groups.
</b>251-258<br><a href="http://doi.acm.org/10.1145/780542.780581"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GeorgiouRS03">BibTeX</a></font>

<li><a name="FatourouFR03" href="../../indices/a-tree/f/Fatourou:Panagiota.html">Panagiota Fatourou</a>, <a href="../../indices/a-tree/f/Fich:Faith_Ellen.html">Faith Ellen Fich</a>, <a href="../../indices/a-tree/r/Ruppert:Eric.html">Eric Ruppert</a>:
<br><b>A tight time lower bound for space-optimal implementations of multi-writer snapshots.
</b>259-268<br><a href="http://doi.acm.org/10.1145/780542.780582"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FatourouFR03">BibTeX</a></font>

</ul>
<h2>Session 6A</h2> 
<ul>
<li><a name="Hayes03" href="../../indices/a-tree/h/Hayes:Thomas_P=.html">Thomas P. Hayes</a>:
<br><b>Randomly coloring graphs of girth at least five.
</b>269-278<br><a href="http://doi.acm.org/10.1145/780542.780584"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Hayes03">BibTeX</a></font>

<li><a name="MorrisP03" href="../../indices/a-tree/m/Morris:Ben.html">Ben Morris</a>, <a href="../../indices/a-tree/p/Peres:Yuval.html">Yuval Peres</a>:
<br><b>Evolving sets and mixin.
</b>279-286<br><a href="http://doi.acm.org/10.1145/780542.780585"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/MorrisP03">BibTeX</a></font>

<li><a name="BobkovT03" href="../../indices/a-tree/b/Bobkov:Sergey.html">Sergey Bobkov</a>, <a href="../../indices/a-tree/t/Tetali:Prasad.html">Prasad Tetali</a>:
<br><b>Modified log-sobolev inequalities, mixing and hypercontractivity.
</b>287-296<br><a href="http://doi.acm.org/10.1145/780542.780586"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BobkovT03">BibTeX</a></font>

</ul>
<h2>Session 6B</h2> 
<ul>
<li><a name="GilbertK03" href="../../indices/a-tree/g/Gilbert:Anna_C=.html">Anna C. Gilbert</a>, <a href="../../indices/a-tree/k/Karloff:Howard_J=.html">Howard J. Karloff</a>:
<br><b>On the fractal behavior of TCP.
</b>297-306<br><a href="http://doi.acm.org/10.1145/780542.780588"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GilbertK03">BibTeX</a></font>

<li><a name="BrodalF03" href="../../indices/a-tree/b/Brodal:Gerth_St=oslash=lting.html">Gerth St&oslash;lting Brodal</a>, <a href="../../indices/a-tree/f/Fagerberg:Rolf.html">Rolf Fagerberg</a>:
<br><b>On the limits of cache-obliviousness.
</b>307-315<br><a href="http://doi.acm.org/10.1145/780542.780589"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BrodalF03">BibTeX</a></font>

<li><a name="BatuEKMRRS03" href="../../indices/a-tree/b/Batu:Tugkan.html">Tugkan Batu</a>, <a href="../../indices/a-tree/e/Erg=uuml=n:Funda.html">Funda Erg&uuml;n</a>, <a href="../../indices/a-tree/k/Kilian:Joe.html">Joe Kilian</a>, <a href="../../indices/a-tree/m/Magen:Avner.html">Avner Magen</a>, <a href="../../indices/a-tree/r/Raskhodnikova:Sofya.html">Sofya Raskhodnikova</a>, <a href="../../indices/a-tree/r/Rubinfeld:Ronitt.html">Ronitt Rubinfeld</a>, <a href="../../indices/a-tree/s/Sami:Rahul.html">Rahul Sami</a>:
<br><b>A sublinear algorithm for weakly approximating edit distance.
</b>316-324<br><a href="http://doi.acm.org/10.1145/780542.780590"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BatuEKMRRS03">BibTeX</a></font>

</ul>
<h2>Session 7A</h2> 
<ul>
<li><a name="ODonnellS03" 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>New degree bounds for polynomial threshold functions.
</b>325-334<br><a href="http://doi.acm.org/10.1145/780542.780592"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ODonnellS03">BibTeX</a></font>

<li><a name="Bar-Yossef03" href="../../indices/a-tree/b/Bar=Yossef:Ziv.html">Ziv Bar-Yossef</a>:
<br><b>Sampling lower bounds via information theory.
</b>335-344<br><a href="http://doi.acm.org/10.1145/780542.780593"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Bar-Yossef03">BibTeX</a></font>

<li><a name="Ben-SassonHR03" href="../../indices/a-tree/b/Ben=Sasson:Eli.html">Eli Ben-Sasson</a>, <a href="../../indices/a-tree/h/Harsha:Prahladh.html">Prahladh Harsha</a>, <a href="../../indices/a-tree/r/Raskhodnikova:Sofya.html">Sofya Raskhodnikova</a>:
<br><b>Some 3CNF properties are hard to test.
</b>345-354<br><a href="http://doi.acm.org/10.1145/780542.780594"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Ben-SassonHR03">BibTeX</a></font>

<li><a name="KabanetsI03" href="../../indices/a-tree/k/Kabanets:Valentine.html">Valentine Kabanets</a>, <a href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>:
<br><b>Derandomizing polynomial identity tests means proving circuit lower bounds.
</b>355-364<br><a href="http://doi.acm.org/10.1145/780542.780595"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KabanetsI03">BibTeX</a></font>

</ul>
<h2>Session 7B</h2> 
<ul>
<li><a name="GuptaKR03" 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/r/Roughgarden:Tim.html">Tim Roughgarden</a>:
<br><b>Simpler and better approximation algorithms for network design.
</b>365-372<br><a href="http://doi.acm.org/10.1145/780542.780597"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GuptaKR03">BibTeX</a></font>

<li><a name="ChenRS03" href="../../indices/a-tree/c/Chen:Jiangzhuo.html">Jiangzhuo Chen</a>, <a href="../../indices/a-tree/r/Rajaraman:Rajmohan.html">Rajmohan Rajaraman</a>, <a href="../../indices/a-tree/s/Sundaram:Ravi.html">Ravi Sundaram</a>:
<br><b>Meet and merge: approximation algorithms for confluent flows.
</b>373-382<br><a href="http://doi.acm.org/10.1145/780542.780598"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChenRS03">BibTeX</a></font>

<li><a name="AzarCFKR03" href="../../indices/a-tree/a/Azar:Yossi.html">Yossi Azar</a>, <a href="../../indices/a-tree/c/Cohen:Edith.html">Edith Cohen</a>, <a href="../../indices/a-tree/f/Fiat:Amos.html">Amos Fiat</a>, <a href="../../indices/a-tree/k/Kaplan:Haim.html">Haim Kaplan</a>, <a href="../../indices/a-tree/r/R=auml=cke:Harald.html">Harald R&auml;cke</a>:
<br><b>Optimal oblivious routing in polynomial time.
</b>383-388<br><a href="http://doi.acm.org/10.1145/780542.780599"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AzarCFKR03">BibTeX</a></font>

<li><a name="KonemannR03" href="../../indices/a-tree/k/K=ouml=nemann:Jochen.html">Jochen K&ouml;nemann</a>, <a href="../../indices/a-tree/r/Ravi:R=.html">R. Ravi</a>:
<br><b>Primal-dual meets local search: approximating MST's with nonuniform degree bounds.
</b>389-395<br><a href="http://doi.acm.org/10.1145/780542.780600"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KonemannR03">BibTeX</a></font>

</ul>
<h2>Session 8A</h2> 
<ul>
<li><a name="Ajtai03" href="../../indices/a-tree/a/Ajtai:Mikl=oacute=s.html">Mikl&oacute;s Ajtai</a>:
<br><b>The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice.
</b>396-406<br><a href="http://doi.acm.org/10.1145/780542.780602"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Ajtai03">BibTeX</a></font>

<li><a name="Regev03" href="../../indices/a-tree/r/Regev:Oded.html">Oded Regev</a>:
<br><b>New lattice based cryptographic constructions.
</b>407-416<br><a href="http://doi.acm.org/10.1145/780542.780603"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Regev03">BibTeX</a></font>

<li><a name="GennaroGK03" href="../../indices/a-tree/g/Gennaro:Rosario.html">Rosario Gennaro</a>, <a href="../../indices/a-tree/g/Gertner:Yael.html">Yael Gertner</a>, <a href="../../indices/a-tree/k/Katz:Jonathan.html">Jonathan Katz</a>:
<br><b>Lower bounds on the efficiency of encryption and digital signature schemes.
</b>417-425<br><a href="http://doi.acm.org/10.1145/780542.780604"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GennaroGK03">BibTeX</a></font>

<li><a name="DamgardG03" href="../../indices/a-tree/d/Damg=aring=rd:Ivan.html">Ivan Damg&aring;rd</a>, <a href="../../indices/a-tree/g/Groth:Jens.html">Jens Groth</a>:
<br><b>Non-interactive and reusable non-malleable commitment schemes.
</b>426-437<br><a href="http://doi.acm.org/10.1145/780542.780605"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DamgardG03">BibTeX</a></font>

</ul>
<h2>Session 8B</h2> 
<ul>
<li><a name="KrauthgamerL03" 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>The intrinsic dimensionality of graphs.
</b>438-447<br><a href="http://doi.acm.org/10.1145/780542.780607"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KrauthgamerL03">BibTeX</a></font>

<li><a name="FakcharoenpholRT03" href="../../indices/a-tree/f/Fakcharoenphol:Jittat.html">Jittat Fakcharoenphol</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>A tight bound on approximating arbitrary metrics by tree metrics.
</b>448-455<br><a href="http://doi.acm.org/10.1145/780542.780608"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/FakcharoenpholRT03">BibTeX</a></font>

<li><a name="Rabinovich03" href="../../indices/a-tree/r/Rabinovich:Yuri.html">Yuri Rabinovich</a>:
<br><b>On average distortion of embedding metrics into the line and into L1.
</b>456-462<br><a href="http://doi.acm.org/10.1145/780542.780609"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Rabinovich03">BibTeX</a></font>

<li><a name="BartalLMN03" href="../../indices/a-tree/b/Bartal:Yair.html">Yair Bartal</a>, <a href="../../indices/a-tree/l/Linial:Nathan.html">Nathan Linial</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>On metric ramsey-type phenomena.
</b>463-472<br><a href="http://doi.acm.org/10.1145/780542.780610"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BartalLMN03">BibTeX</a></font>

</ul>
<h2>Session 9A</h2> 
<ul>
<li><a name="DrorELM03" href="../../indices/a-tree/d/Dror:Moshe.html">Moshe Dror</a>, <a href="../../indices/a-tree/e/Efrat:Alon.html">Alon Efrat</a>, <a href="../../indices/a-tree/l/Lubiw:Anna.html">Anna Lubiw</a>, <a href="../../indices/a-tree/m/Mitchell:Joseph_S=_B=.html">Joseph S. B. Mitchell</a>:
<br><b>Touring a sequence of polygons.
</b>473-482<br><a href="http://doi.acm.org/10.1145/780542.780612"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DrorELM03">BibTeX</a></font>

<li><a name="GaoZ03" href="../../indices/a-tree/g/Gao:Jie.html">Jie Gao</a>, <a href="../../indices/a-tree/z/Zhang:Li.html">Li Zhang</a>:
<br><b>Well-separated pair decomposition for the unit-disk graph metric and its applications.
</b>483-492<br><a href="http://doi.acm.org/10.1145/780542.780613"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GaoZ03">BibTeX</a></font>

<li><a name="DeyGJ03" href="../../indices/a-tree/d/Dey:Tamal_K=.html">Tamal K. Dey</a>, <a href="../../indices/a-tree/g/Giesen:Joachim.html">Joachim Giesen</a>, <a href="../../indices/a-tree/j/John:Matthias.html">Matthias John</a>:
<br><b>Alpha-shapes and flow shapes are homotopy equivalent.
</b>493-502<br><a href="http://doi.acm.org/10.1145/780542.780614"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DeyGJ03">BibTeX</a></font>

</ul>
<h2>Session 9B</h2> 
<ul>
<li><a name="AwerbuchAM03" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/a/Azar:Yossi.html">Yossi Azar</a>, <a href="../../indices/a-tree/m/Meyerson:Adam.html">Adam Meyerson</a>:
<br><b>Reducing truth-telling online mechanisms to online optimization.
</b>503-510<br><a href="http://doi.acm.org/10.1145/780542.780616"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AwerbuchAM03">BibTeX</a></font>

<li><a name="AnshelevichDTW03" 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/t/Tardos:=Eacute=va.html">&Eacute;va Tardos</a>, <a href="../../indices/a-tree/w/Wexler:Tom.html">Tom Wexler</a>:
<br><b>Near-optimal network design with selfish agents.
</b>511-520<br><a href="http://doi.acm.org/10.1145/780542.780617"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AnshelevichDTW03">BibTeX</a></font>

<li><a name="ColeDR03" href="../../indices/a-tree/c/Cole:Richard.html">Richard Cole</a>, <a href="../../indices/a-tree/d/Dodis:Yevgeniy.html">Yevgeniy Dodis</a>, <a href="../../indices/a-tree/r/Roughgarden:Tim.html">Tim Roughgarden</a>:
<br><b>Pricing network edges for heterogeneous selfish users.
</b>521-530<br><a href="http://doi.acm.org/10.1145/780542.780618"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ColeDR03">BibTeX</a></font>

</ul>
<h2>Session 10A</h2> 
<ul>
<li><a name="ChazelleLM03" href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>, <a href="../../indices/a-tree/l/Liu:Ding.html">Ding Liu</a>, <a href="../../indices/a-tree/m/Magen:Avner.html">Avner Magen</a>:
<br><b>Sublinear geometric algorithms.
</b>531-540<br><a href="http://doi.acm.org/10.1145/780542.780620"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ChazelleLM03">BibTeX</a></font>

<li><a name="AronovPST03" href="../../indices/a-tree/a/Aronov:Boris.html">Boris Aronov</a>, <a href="../../indices/a-tree/p/Pach:J=aacute=nos.html">J&aacute;nos Pach</a>, <a href="../../indices/a-tree/s/Sharir:Micha.html">Micha Sharir</a>, <a href="../../indices/a-tree/t/Tardos:G=aacute=bor.html">G&aacute;bor Tardos</a>:
<br><b>Distinct distances in three and higher dimensions.
</b>541-546<br><a href="http://doi.acm.org/10.1145/780542.780621"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AronovPST03">BibTeX</a></font>

<li><a name="AronovKS03" href="../../indices/a-tree/a/Aronov:Boris.html">Boris Aronov</a>, <a href="../../indices/a-tree/k/Koltun:Vladlen.html">Vladlen Koltun</a>, <a href="../../indices/a-tree/s/Sharir:Micha.html">Micha Sharir</a>:
<br><b>Cutting triangular cycles of lines in space.
</b>547-555<br><a href="http://doi.acm.org/10.1145/780542.780622"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AronovKS03">BibTeX</a></font>

</ul>
<h2>Session 10B</h2> 
<ul>
<li><a name="BuchsbaumKKRT03" href="../../indices/a-tree/b/Buchsbaum:Adam_L=.html">Adam L. Buchsbaum</a>, <a href="../../indices/a-tree/k/Karloff:Howard_J=.html">Howard J. Karloff</a>, <a href="../../indices/a-tree/k/Kenyon:Claire.html">Claire Kenyon</a>, <a href="../../indices/a-tree/r/Reingold:Nick.html">Nick Reingold</a>, <a href="../../indices/a-tree/t/Thorup:Mikkel.html">Mikkel Thorup</a>:
<br><b>OPT versus LOAD in dynamic storage allocation.
</b>556-564<br><a href="http://doi.acm.org/10.1145/780542.780624"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/BuchsbaumKKRT03">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>Consistent load balancing via spread minimization.
</b>565-574<br><a href="http://doi.acm.org/10.1145/780542.780625"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KleinbergL03">BibTeX</a></font>

<li><a name="AdlerHKV03" href="../../indices/a-tree/a/Adler:Micah.html">Micah Adler</a>, <a href="../../indices/a-tree/h/Halperin:Eran.html">Eran Halperin</a>, <a href="../../indices/a-tree/k/Karp:Richard_M=.html">Richard M. Karp</a>, <a href="../../indices/a-tree/v/Vazirani:Vijay_V=.html">Vijay V. Vazirani</a>:
<br><b>A stochastic process on the hypercube with applications to peer-to-peer networks.
</b>575-584<br><a href="http://doi.acm.org/10.1145/780542.780626"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AdlerHKV03">BibTeX</a></font>

</ul>
<h2>Session 11A</h2> 
<ul>
<li><a name="HalperinK03" href="../../indices/a-tree/h/Halperin:Eran.html">Eran Halperin</a>, <a href="../../indices/a-tree/k/Krauthgamer:Robert.html">Robert Krauthgamer</a>:
<br><b>Polylogarithmic inapproximability.
</b>585-594<br><a href="http://doi.acm.org/10.1145/780542.780628"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/HalperinK03">BibTeX</a></font>

<li><a name="DinurGKR03" href="../../indices/a-tree/d/Dinur:Irit.html">Irit Dinur</a>, <a href="../../indices/a-tree/g/Guruswami:Venkatesan.html">Venkatesan Guruswami</a>, <a href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>, <a href="../../indices/a-tree/r/Regev:Oded.html">Oded Regev</a>:
<br><b>A new multilayered PCP and the hardness of hypergraph vertex cover.
</b>595-601<br><a href="http://doi.acm.org/10.1145/780542.780629"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DinurGKR03">BibTeX</a></font>

<li><a name="LuRVW03" href="../../indices/a-tree/l/Lu:Chi=Jen.html">Chi-Jen Lu</a>, <a href="../../indices/a-tree/r/Reingold:Omer.html">Omer Reingold</a>, <a href="../../indices/a-tree/v/Vadhan:Salil_P=.html">Salil P. Vadhan</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>:
<br><b>Extractors: optimal up to constant factors.
</b>602-611<br><a href="http://doi.acm.org/10.1145/780542.780630"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/LuRVW03">BibTeX</a></font>

<li><a name="Ben-SassonSVW03" href="../../indices/a-tree/b/Ben=Sasson:Eli.html">Eli Ben-Sasson</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>, <a href="../../indices/a-tree/v/Vadhan:Salil_P=.html">Salil P. Vadhan</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>:
<br><b>Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.
</b>612-621<br><a href="http://doi.acm.org/10.1145/780542.780631"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Ben-SassonSVW03">BibTeX</a></font>

</ul>
<h2>Session 11B</h2> 
<ul>
<li><a name="OstlinP03" href="../../indices/a-tree/=/=Ouml=stlin:Anna.html">Anna &Ouml;stlin</a>, <a href="../../indices/a-tree/p/Pagh:Rasmus.html">Rasmus Pagh</a>:
<br><b>Uniform hashing in constant time and linear space.
</b>622-628<br><a href="http://doi.acm.org/10.1145/780542.780633"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/OstlinP03">BibTeX</a></font>

<li><a name="DietzfelbingerW03" href="../../indices/a-tree/d/Dietzfelbinger:Martin.html">Martin Dietzfelbinger</a>, <a href="../../indices/a-tree/w/Woelfel:Philipp.html">Philipp Woelfel</a>:
<br><b>Almost random graphs with simple hash functions.
</b>629-638<br><a href="http://doi.acm.org/10.1145/780542.780634"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/DietzfelbingerW03">BibTeX</a></font>

<li><a name="KaplanMT03" href="../../indices/a-tree/k/Kaplan:Haim.html">Haim Kaplan</a>, <a href="../../indices/a-tree/m/Molad:Eyal.html">Eyal Molad</a>, <a href="../../indices/a-tree/t/Tarjan:Robert_Endre.html">Robert Endre Tarjan</a>:
<br><b>Dynamic rectangular intersection with priorities.
</b>639-648<br><a href="http://doi.acm.org/10.1145/780542.780635"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/KaplanMT03">BibTeX</a></font>

<li><a name="Thorup03a" href="../../indices/a-tree/t/Thorup:Mikkel.html">Mikkel Thorup</a>:
<br><b>Space efficient dynamic stabbing with fast queries.
</b>649-658<br><a href="http://doi.acm.org/10.1145/780542.780636"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Thorup03a">BibTeX</a></font>

</ul>
<h2>Session 12A</h2> 
<ul>
<li><a name="GalR03" href="../../indices/a-tree/g/G=aacute=l:Anna.html">Anna G&aacute;l</a>, <a href="../../indices/a-tree/r/Ros=eacute=n:Adi.html">Adi Ros&eacute;n</a>:
<br><b>Lower bounds on the amount of randomness in private computation.
</b>659-666<br><a href="http://doi.acm.org/10.1145/780542.780638"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/GalR03">BibTeX</a></font>

<li><a name="JayramKKR03" href="../../indices/a-tree/j/Jayram:T=_S=.html">T. S. Jayram</a>, <a href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>, <a href="../../indices/a-tree/k/Kumar:Ravi.html">Ravi Kumar</a>, <a href="../../indices/a-tree/r/Rabani:Yuval.html">Yuval Rabani</a>:
<br><b>Cell-probe lower bounds for the partial match problem.
</b>667-672<br><a href="http://doi.acm.org/10.1145/780542.780639"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/JayramKKR03">BibTeX</a></font>

<li><a name="JayramKS03" href="../../indices/a-tree/j/Jayram:T=_S=.html">T. S. Jayram</a>, <a href="../../indices/a-tree/k/Kumar:Ravi.html">Ravi Kumar</a>, <a href="../../indices/a-tree/s/Sivakumar:D=.html">D. Sivakumar</a>:
<br><b>Two applications of information complexity.
</b>673-682<br><a href="http://doi.acm.org/10.1145/780542.780640"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/JayramKS03">BibTeX</a></font>

<li><a name="Lindell03" href="../../indices/a-tree/l/Lindell:Yehuda.html">Yehuda Lindell</a>:
<br><b>Bounded-concurrent secure two-party computation without setup assumptions.
</b>683-692<br><a href="http://doi.acm.org/10.1145/780542.780641"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Lindell03">BibTeX</a></font>

</ul>
<h2>Session 12B</h2> 
<ul>
<li><a name="Dyer03" href="../../indices/a-tree/d/Dyer:Martin_E=.html">Martin E. Dyer</a>:
<br><b>Approximate counting by dynamic programming.
</b>693-699<br><a href="http://doi.acm.org/10.1145/780542.780643"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Dyer03">BibTeX</a></font>

<li><a name="AlonS03" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/s/Shapira:Asaf.html">Asaf Shapira</a>:
<br><b>Testing subgraphs in directed graphs.
</b>700-709<br><a href="http://doi.acm.org/10.1145/780542.780644"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/AlonS03">BibTeX</a></font>

<li><a name="ItohTT03" href="../../indices/a-tree/i/Itoh:Toshiya.html">Toshiya Itoh</a>, <a href="../../indices/a-tree/t/Takei:Yoshinori.html">Yoshinori Takei</a>, <a href="../../indices/a-tree/t/Tarui:Jun.html">Jun Tarui</a>:
<br><b>On the sample size of k-restricted min-wise independent permutations and other k-wise distributions.
</b>710-719<br><a href="http://doi.acm.org/10.1145/780542.780645"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/ItohTT03">BibTeX</a></font>

<li><a name="Friedman03" href="../../indices/a-tree/f/Friedman:Joel.html">Joel Friedman</a>:
<br><b>A proof of Alon's second eigenvalue conjecture.
</b>720-724<br><a href="http://doi.acm.org/10.1145/780542.780646"><i>Electronic Edition</i></a> (<a href="http://www.acm.org/dl/">ACM DL</a>) <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/stoc/Friedman03">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> &#151; 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 &#169;</a> Sat May 16 23:43:12 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>
Document Actions
SIGMOD Record
SIGMOD Record