focs2001.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>42. FOCS 2001: Las Vegas, Nevada, USA</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>42. <a href="index.html">FOCS</a> 2001: Las Vegas, Nevada, USA</h1> 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA. IEEE Computer Society, 2001, ISBN 0-7695-1390-5 <h2>Tutorials Day</h2> <ul> <li><a name="Papadimitriou01" href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction. 4-8 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Papadimitriou01">BibTeX</a></font> <li><a name="Indyk01" href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>: Algorithmic Applications of Low-Distortion Geometric Embeddings. 10-33 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Indyk01">BibTeX</a></font> <li><a name="Sudan01" href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: Coding Theory: Tutorial and Survey. 36-53 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Sudan01">BibTeX</a></font> </ul> <h2>Session 1</h2> <ul> <li><a name="Koltun01" href="../../indices/a-tree/k/Koltun:Vladlen.html">Vladlen Koltun</a>: Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions. 56-65 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Koltun01">BibTeX</a></font> <li><a name="Har-PeledV01" href="../../indices/a-tree/h/Har=Peled:Sariel.html">Sariel Har-Peled</a>, <a href="../../indices/a-tree/v/Varadarajan:Kasturi_R=.html">Kasturi R. Varadarajan</a>: Approximate Shape Fitting via Linearization. 66-73 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Har-PeledV01">BibTeX</a></font> <li><a name="AgarwalAS01" href="../../indices/a-tree/a/Agarwal:Pankaj_K=.html">Pankaj K. Agarwal</a>, <a href="../../indices/a-tree/a/Aronov:Boris.html">Boris Aronov</a>, <a href="../../indices/a-tree/s/Sharir:Micha.html">Micha Sharir</a>: On the Complexity of Many Faces in Arrangements of Circles. 74-83 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AgarwalAS01">BibTeX</a></font> <li><a name="Har-Peled01" href="../../indices/a-tree/h/Har=Peled:Sariel.html">Sariel Har-Peled</a>: Clustering Motion. 84-93 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Har-Peled01">BibTeX</a></font> <li><a name="Har-Peled01a" href="../../indices/a-tree/h/Har=Peled:Sariel.html">Sariel Har-Peled</a>: A Replacement for Voronoi Diagrams of Near Linear Size. 94-103 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Har-Peled01a">BibTeX</a></font> </ul> <h2>Session 2</h2> <ul> <li><a name="Barak01" href="../../indices/a-tree/b/Barak:Boaz.html">Boaz Barak</a>: How to Go Beyond the Black-Box Simulation Barrier. 106-115 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Barak01">BibTeX</a></font> <li><a name="BarakGGL01" href="../../indices/a-tree/b/Barak:Boaz.html">Boaz Barak</a>, <a 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/l/Lindell:Yehuda.html">Yehuda Lindell</a>: Resettably-Sound Zero-Knowledge and its Applications. 116-125 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BarakGGL01">BibTeX</a></font> <li><a name="GertnerMR01" href="../../indices/a-tree/g/Gertner:Yael.html">Yael Gertner</a>, <a href="../../indices/a-tree/m/Malkin:Tal.html">Tal Malkin</a>, <a href="../../indices/a-tree/r/Reingold:Omer.html">Omer Reingold</a>: On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates. 126-135 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GertnerMR01">BibTeX</a></font> <li><a name="Canetti01" href="../../indices/a-tree/c/Canetti:Ran.html">Ran Canetti</a>: Universally Composable Security: A New Paradigm for Cryptographic Protocols. 136-145 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Canetti01">BibTeX</a></font> </ul> <h2>Session 3</h2> <ul> <li><a name="GuptaKR01" 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/Rastogi:Rajeev.html">Rajeev Rastogi</a>: Traveling with a Pez Dispenser (Or, Routing Issues in MPLS). 148-157 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GuptaKR01">BibTeX</a></font> <li><a name="AwerbuchBBS01" href="../../indices/a-tree/a/Awerbuch:Baruch.html">Baruch Awerbuch</a>, <a href="../../indices/a-tree/b/Berenbrink:Petra.html">Petra Berenbrink</a>, <a href="../../indices/a-tree/b/Brinkmann:Andr=eacute=.html">André Brinkmann</a>, <a href="../../indices/a-tree/s/Scheideler:Christian.html">Christian Scheideler</a>: Simple Routing Strategies for Adversarial Systems. 158-167 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchBBS01">BibTeX</a></font> <li><a name="AndrewsFGZ01" href="../../indices/a-tree/a/Andrews:Matthew.html">Matthew Andrews</a>, <a href="../../indices/a-tree/f/Fern=aacute=ndez:Antonio.html">Antonio Fernández</a>, <a href="../../indices/a-tree/g/Goel:Ashish.html">Ashish Goel</a>, <a href="../../indices/a-tree/z/Zhang:Lisa.html">Lisa Zhang</a>: Source Routing and Scheduling in Packet Networks. 168-177 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AndrewsFGZ01">BibTeX</a></font> <li><a name="BerenbrinkFG01" href="../../indices/a-tree/b/Berenbrink:Petra.html">Petra Berenbrink</a>, <a href="../../indices/a-tree/f/Friedetzky:Tom.html">Tom Friedetzky</a>, <a href="../../indices/a-tree/g/Goldberg:Leslie_Ann.html">Leslie Ann Goldberg</a>: The Natural Work-Stealing Algorithm is Stable. 178-187 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BerenbrinkFG01">BibTeX</a></font> </ul> <h2>Session 4</h2> <ul> <li><a name="AlekhnovichR01" href="../../indices/a-tree/a/Alekhnovich:Michael.html">Michael Alekhnovich</a>, <a href="../../indices/a-tree/r/Razborov:Alexander_A=.html">Alexander A. Razborov</a>: Lower Bounds for Polynomial Calculus: Non-Binomial Case. 190-199 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlekhnovichR01">BibTeX</a></font> <li><a name="ImpagliazzoS01" href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/s/Segerlind:Nathan.html">Nathan Segerlind</a>: Counting Axioms Do Not Polynomially Simulate Counting Gates. 200-209 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ImpagliazzoS01">BibTeX</a></font> <li><a name="AlekhnovichR01a" href="../../indices/a-tree/a/Alekhnovich:Michael.html">Michael Alekhnovich</a>, <a href="../../indices/a-tree/r/Razborov:Alexander_A=.html">Alexander A. Razborov</a>: Resolution is Not Automatizable Unless W[P] is Tractable. 210-219 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlekhnovichR01a">BibTeX</a></font> <li><a name="DantchevR01" href="../../indices/a-tree/d/Dantchev:Stefan_S=.html">Stefan S. Dantchev</a>, <a href="../../indices/a-tree/r/Riis:S=oslash=ren.html">Søren Riis</a>: "Planar" Tautologies Hard for Resolution. 220-229 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DantchevR01">BibTeX</a></font> </ul> <h2>Session 5</h2> <ul> <li><a name="FakcharoenpholR01" href="../../indices/a-tree/f/Fakcharoenphol:Jittat.html">Jittat Fakcharoenphol</a>, <a href="../../indices/a-tree/r/Rao:Satish.html">Satish Rao</a>: Planar Graphs, Negative Weight Edges, Shortest Paths, Near Linear Time. 232-241 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FakcharoenpholR01">BibTeX</a></font> <li><a name="Thorup01" href="../../indices/a-tree/t/Thorup:Mikkel.html">Mikkel Thorup</a>: Compact Oracles for Reachability and Approximate Distances in Planar Digraphs. 242-251 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Thorup01">BibTeX</a></font> <li><a name="HershbergerS01" href="../../indices/a-tree/h/Hershberger:John.html">John Hershberger</a>, <a href="../../indices/a-tree/s/Suri:Subhash.html">Subhash Suri</a>: Vickrey Prices and Shortest Paths: What is an Edge Worth?. 252-259 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HershbergerS01">BibTeX</a></font> <li><a name="DemetrescuI01" 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>: Fully Dynamic All Pairs Shortest Paths with Real Edge Weights. 260-267 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DemetrescuI01">BibTeX</a></font> </ul> <h2>Session 6</h2> <ul> <li><a name="ChakrabartiSWY01" href="../../indices/a-tree/c/Chakrabarti:Amit.html">Amit Chakrabarti</a>, <a href="../../indices/a-tree/s/Shi:Yaoyun.html">Yaoyun Shi</a>, <a href="../../indices/a-tree/w/Wirth:Anthony.html">Anthony Wirth</a>, <a href="../../indices/a-tree/y/Yao:Andrew_Chi=Chih.html">Andrew Chi-Chih Yao</a>: Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity. 270-278 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChakrabartiSWY01">BibTeX</a></font> <li><a name="DamMV01" href="../../indices/a-tree/d/Dam:Wim_van.html">Wim van Dam</a>, <a href="../../indices/a-tree/m/Mosca:Michele.html">Michele Mosca</a>, <a href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>: How Powerful is Adiabatic Quantum Computation?. 279-287 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DamMV01">BibTeX</a></font> <li><a name="Klauck01" href="../../indices/a-tree/k/Klauck:Hartmut.html">Hartmut Klauck</a>: Lower Bounds for Quantum Communication Complexity. 288-297 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Klauck01">BibTeX</a></font> <li><a name="ComonGN01" href="../../indices/a-tree/c/Comon:Hubert.html">Hubert Comon</a>, <a href="../../indices/a-tree/g/Godoy:Guillem.html">Guillem Godoy</a>, <a href="../../indices/a-tree/n/Nieuwenhuis:Robert.html">Robert Nieuwenhuis</a>: The Confluence of Ground Term Rewrite Systems is Decidable in Polynomial Time. 298-307 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ComonGN01">BibTeX</a></font> <li><a name="Cai01" href="../../indices/a-tree/c/Cai:Jin=yi.html">Jin-yi Cai</a>: On the Average-Case Hardness of CVP. 308-317 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Cai01">BibTeX</a></font> </ul> <h2>Session 7</h2> <ul> <li><a name="CheriyanKR01" href="../../indices/a-tree/c/Cheriyan:Joseph.html">Joseph Cheriyan</a>, <a href="../../indices/a-tree/k/Karloff:Howard_J=.html">Howard J. Karloff</a>, <a href="../../indices/a-tree/r/Rabani:Yuval.html">Yuval Rabani</a>: Approximating Directed Multicuts. 320-328 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CheriyanKR01">BibTeX</a></font> <li><a name="PalTW01" 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>, <a href="../../indices/a-tree/w/Wexler:Tom.html">Tom Wexler</a>: Facility Location with Nonuniform Hard Capacities. 329-338 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PalTW01">BibTeX</a></font> <li><a name="FleischerJW01" 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/w/Williamson:David_P=.html">David P. Williamson</a>: An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem. 339-347 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FleischerJW01">BibTeX</a></font> <li><a name="ChuzhoyOR01" href="../../indices/a-tree/c/Chuzhoy:Julia.html">Julia Chuzhoy</a>, <a href="../../indices/a-tree/o/Ostrovsky:Rafail.html">Rafail Ostrovsky</a>, <a href="../../indices/a-tree/r/Rabani:Yuval.html">Yuval Rabani</a>: Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems. 348-356 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChuzhoyOR01">BibTeX</a></font> </ul> <h2>Session 8</h2> <ul> <li><a name="Shpilka01" href="../../indices/a-tree/s/Shpilka:Amir.html">Amir Shpilka</a>: Lower Bounds for Matrix Product. 358-367 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Shpilka01">BibTeX</a></font> <li><a name="Storjohann01" href="../../indices/a-tree/s/Storjohann:Arne.html">Arne Storjohann</a>: Deterministic Computation of the Frobenius Form. 368-377 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Storjohann01">BibTeX</a></font> <li><a name="Burgisser01" href="../../indices/a-tree/b/B=uuml=rgisser:Peter.html">Peter Bürgisser</a>: The Complexity of Factors of Multivariate Polynomials. 378-385 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Burgisser01">BibTeX</a></font> <li><a name="McConnell01" href="../../indices/a-tree/m/McConnell:Ross_M=.html">Ross M. McConnell</a>: Linear-time Recognition of Circular-arc Graphs. 386-394 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/McConnell01">BibTeX</a></font> </ul> <h2>Sessoin 9</h2> <ul> <li><a name="BartalBM01" href="../../indices/a-tree/b/Bartal:Yair.html">Yair Bartal</a>, <a href="../../indices/a-tree/b/Bollob=aacute=s:B=eacute=la.html">Béla Bollobás</a>, <a href="../../indices/a-tree/m/Mendel:Manor.html">Manor Mendel</a>: A Ramsy-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems. 396-405 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BartalBM01">BibTeX</a></font> <li><a name="MeyersonMP01" href="../../indices/a-tree/m/Meyerson:Adam.html">Adam Meyerson</a>, <a href="../../indices/a-tree/m/Munagala:Kamesh.html">Kamesh Munagala</a>, <a href="../../indices/a-tree/p/Plotkin:Serge_A=.html">Serge A. Plotkin</a>: Designing Networks Incrementally. 406-415 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MeyersonMP01">BibTeX</a></font> <li><a name="GuptaK01" href="../../indices/a-tree/g/Gupta:Anupam.html">Anupam Gupta</a>, <a href="../../indices/a-tree/k/Kumar:Amit.html">Amit Kumar</a>: Sorting and Selection with Structured Costs. 416-425 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GuptaK01">BibTeX</a></font> <li><a name="Meyerson01" href="../../indices/a-tree/m/Meyerson:Adam.html">Adam Meyerson</a>: Online Facility Location. 426-431 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Meyerson01">BibTeX</a></font> </ul> <h2>Session 10</h2> <ul> <li><a name="Alon01" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>: Testing Subgraphs in Large Graphs. 434-441 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Alon01">BibTeX</a></font> <li><a name="BatuFFKRW01" href="../../indices/a-tree/b/Batu:Tugkan.html">Tugkan Batu</a>, <a href="../../indices/a-tree/f/Fortnow:Lance.html">Lance Fortnow</a>, <a href="../../indices/a-tree/f/Fischer:Eldar.html">Eldar Fischer</a>, <a href="../../indices/a-tree/k/Kumar:Ravi.html">Ravi Kumar</a>, <a href="../../indices/a-tree/r/Rubinfeld:Ronitt.html">Ronitt Rubinfeld</a>, <a href="../../indices/a-tree/w/White:Patrick.html">Patrick White</a>: Testing Random Variables for Independence and Identity. 442-451 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BatuFFKRW01">BibTeX</a></font> <li><a name="DrineasK01" href="../../indices/a-tree/d/Drineas:Petros.html">Petros Drineas</a>, <a href="../../indices/a-tree/k/Kannan:Ravi.html">Ravi Kannan</a>: Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication. 452-459 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DrineasK01">BibTeX</a></font> <li><a name="GoldreichT01" href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/t/Trevisan:Luca.html">Luca Trevisan</a>: Three Theorems Regarding Testing Graph Properties. 460-469 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldreichT01">BibTeX</a></font> </ul> <h2>Session 11</h2> <ul> <li><a name="Roughgarden01" href="../../indices/a-tree/r/Roughgarden:Tim.html">Tim Roughgarden</a>: Designing Networks for Selfish Users is Hard. 472-481 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Roughgarden01">BibTeX</a></font> <li><a name="ArcherT01" href="../../indices/a-tree/a/Archer:Aaron.html">Aaron Archer</a>, <a href="../../indices/a-tree/t/Tardos:=Eacute=va.html">Éva Tardos</a>: Truthful Mechanisms for One-Parameter Agents. 482-491 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ArcherT01">BibTeX</a></font> <li><a name="PanduranganRU01" href="../../indices/a-tree/p/Pandurangan:Gopal.html">Gopal Pandurangan</a>, <a href="../../indices/a-tree/r/Raghavan:Prabhakar.html">Prabhakar Raghavan</a>, <a href="../../indices/a-tree/u/Upfal:Eli.html">Eli Upfal</a>: Building Low-Diameter P2P Networks. 492-499 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PanduranganRU01">BibTeX</a></font> <li><a name="AchlioptasFKM01" href="../../indices/a-tree/a/Achlioptas:Dimitris.html">Dimitris Achlioptas</a>, <a href="../../indices/a-tree/f/Fiat:Amos.html">Amos Fiat</a>, <a href="../../indices/a-tree/k/Karlin:Anna_R=.html">Anna R. Karlin</a>, <a href="../../indices/a-tree/m/McSherry:Frank.html">Frank McSherry</a>: Web Search via Hub Synthesis. 500-509 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AchlioptasFKM01">BibTeX</a></font> <li><a name="AielloCL01" href="../../indices/a-tree/a/Aiello:William.html">William Aiello</a>, <a href="../../indices/a-tree/c/Chung:Fan_R=_K=.html">Fan R. K. Chung</a>, <a href="../../indices/a-tree/l/Lu:Linyuan.html">Linyuan Lu</a>: Random Evolution in Massive Graphs. 510-519 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AielloCL01">BibTeX</a></font> </ul> <h2>Session 12</h2> <ul> <li><a name="KolliopoulosY01" href="../../indices/a-tree/k/Kolliopoulos:Stavros_G=.html">Stavros G. Kolliopoulos</a>, <a href="../../indices/a-tree/y/Young:Neal_E=.html">Neal E. Young</a>: Tight Approximation Results for General Covering Integer Programs. 522-528 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KolliopoulosY01">BibTeX</a></font> <li><a name="McSherry01" href="../../indices/a-tree/m/McSherry:Frank.html">Frank McSherry</a>: Spectral Partitioning of Random Graphs. 529-537 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/McSherry01">BibTeX</a></font> <li><a name="Young01" href="../../indices/a-tree/y/Young:Neal_E=.html">Neal E. Young</a>: Sequential and Parallel Algorithms for Mixed Packing and Covering. 538-546 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Young01">BibTeX</a></font> <li><a name="SzaboW01" href="../../indices/a-tree/s/Szab=oacute=:Tibor.html">Tibor Szabó</a>, <a href="../../indices/a-tree/w/Welzl:Emo.html">Emo Welzl</a>: Unique Sink Orientations of Cubes. 547-555 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SzaboW01">BibTeX</a></font> </ul> <h2>Session 13</h2> <ul> <li><a name="BohmanF01" href="../../indices/a-tree/b/Bohman:Tom.html">Tom Bohman</a>, <a href="../../indices/a-tree/f/Frieze:Alan_M=.html">Alan M. Frieze</a>: Arc-Disjoint Paths in Expander Digraphs. 558-567 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BohmanF01">BibTeX</a></font> <li><a name="KenyonMP01" href="../../indices/a-tree/k/Kenyon:Claire.html">Claire Kenyon</a>, <a href="../../indices/a-tree/m/Mossel:Elchanan.html">Elchanan Mossel</a>, <a href="../../indices/a-tree/p/Peres:Yuval.html">Yuval Peres</a>: Glauber Dynamics on Trees and Hyperbolic Graphs. 568-578 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KenyonMP01">BibTeX</a></font> <li><a name="DyerF01" 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>: Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree. 579-587 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DyerF01">BibTeX</a></font> <li><a name="Srinivasan01" href="../../indices/a-tree/s/Srinivasan:Aravind.html">Aravind Srinivasan</a>: Distributions on Level-Sets with Applications to Approximation Algorithms. 588-597 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Srinivasan01">BibTeX</a></font> </ul> <h2>Session 14</h2> <ul> <li><a name="Khot01" href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>: Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring. 600-609 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Khot01">BibTeX</a></font> <li><a name="HastadK01" href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>, <a href="../../indices/a-tree/k/Khot:Subhash.html">Subhash Khot</a>: Query Efficient PCPs with Perfect Completeness. 610-619 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HastadK01">BibTeX</a></font> <li><a name="Cai01a" href="../../indices/a-tree/c/Cai:Jin=yi.html">Jin-yi Cai</a>: S<sup>p</sup><sub>2</sub> subseteq ZPP<sup>NP</sup>. 620-629 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Cai01a">BibTeX</a></font> </ul> <h2>Session 15</h2> <ul> <li><a name="AlonLW01" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/l/Lubotzky:Alexander.html">Alexander Lubotzky</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications. 630-637 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonLW01">BibTeX</a></font> <li><a name="Ta-ShmaZS01" href="../../indices/a-tree/t/Ta=Shma:Amnon.html">Amnon Ta-Shma</a>, <a href="../../indices/a-tree/z/Zuckerman:David.html">David Zuckerman</a>, <a href="../../indices/a-tree/s/Safra:Shmuel.html">Shmuel Safra</a>: Extractors from Reed-Muller Codes. 638-647 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ta-ShmaZS01">BibTeX</a></font> <li><a name="ShaltielU01" href="../../indices/a-tree/s/Shaltiel:Ronen.html">Ronen Shaltiel</a>, <a href="../../indices/a-tree/u/Umans:Christopher.html">Christopher Umans</a>: Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator. 648-657 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ShaltielU01">BibTeX</a></font> <li><a name="GuruswamiI01" href="../../indices/a-tree/g/Guruswami:Venkatesan.html">Venkatesan Guruswami</a>, <a href="../../indices/a-tree/i/Indyk:Piotr.html">Piotr Indyk</a>: Expander-Based Constructions of Efficiently Decodable Codes. 658-667 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GuruswamiI01">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
