focs95.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>36. FOCS 1995: Milwaukee, Wisconsin</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>36. <a href="index.html">FOCS</a> 1995: Milwaukee, Wisconsin</h1> 36th Annual Symposium on Foundations of Computer Science, Milwaukee, Wisconsin, 23-25 October 1995. IEEE Computer Society <ul> <li><a name="Valiant95" href="../../indices/a-tree/v/Valiant:Leslie_G=.html">Leslie G. Valiant</a>: Cognitive Computation (Extended Abstract). 2-3 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Valiant95">BibTeX</a></font> <li><a name="Lokam95" href="../../indices/a-tree/l/Lokam:Satyanarayana_V=.html">Satyanarayana V. Lokam</a>: Spectral Methods for Matrix Rigidity with Applications to Size-Depth Tradeoffs and Communication Complexity. 6-15 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Lokam95">BibTeX</a></font> , <li><a name="NisanW95" href="../../indices/a-tree/n/Nisan:Noam.html">Noam Nisan</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version). 16-25 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NisanW95">BibTeX</a></font> <li><a name="ReganSC95" href="../../indices/a-tree/r/Regan:Kenneth_W=.html">Kenneth W. Regan</a>, <a href="../../indices/a-tree/s/Sivakumar:D=.html">D. Sivakumar</a>, <a href="../../indices/a-tree/c/Cai:Jin=yi.html">Jin-yi Cai</a>: Pseudorandom Generators, Measure Theory, and Natural Proofs. 26-35 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ReganSC95">BibTeX</a></font> <li><a name="Haken95" href="../../indices/a-tree/h/Haken:Armin.html">Armin Haken</a>: Counting Bottlenecks to Show Monotone P <=> NP. 36-40 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Haken95">BibTeX</a></font> <li><a name="ChorGKS95" href="../../indices/a-tree/c/Chor:Benny.html">Benny Chor</a>, <a href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/k/Kushilevitz:Eyal.html">Eyal Kushilevitz</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: Private Information Retrieval. 41-50 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChorGKS95">BibTeX</a></font> <li><a name="KleinbergT95" href="../../indices/a-tree/k/Kleinberg:Jon_M=.html">Jon M. Kleinberg</a>, <a href="../../indices/a-tree/t/Tardos:=Eacute=va.html">Éva Tardos</a>: Disjoint Paths in Densely Embedded Graphs. 52-61 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KleinbergT95">BibTeX</a></font> <li><a name="EvenNRS95" href="../../indices/a-tree/e/Even:Guy.html">Guy Even</a>, <a href="../../indices/a-tree/n/Naor:Joseph.html">Joseph Naor</a>, <a href="../../indices/a-tree/r/Rao:Satish.html">Satish Rao</a>, <a href="../../indices/a-tree/s/Schieber:Baruch.html">Baruch Schieber</a>: Divide-and-Conquer Approximation Algorithms via Spreading Metrics (Extended Abstract). 62-71 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/EvenNRS95">BibTeX</a></font> <li><a name="BhatiaKN95" href="../../indices/a-tree/b/Bhatia:Randeep.html">Randeep Bhatia</a>, <a href="../../indices/a-tree/k/Khuller:Samir.html">Samir Khuller</a>, <a href="../../indices/a-tree/n/Naor:Joseph.html">Joseph Naor</a>: The Loading Time Scheduling Problem (Extended Abstract). 72-81 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BhatiaKN95">BibTeX</a></font> <li><a name="Hall95" href="../../indices/a-tree/h/Hall:Leslie_A=.html">Leslie A. Hall</a>: Approximability of Flow Shop Scheduling. 82-91 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Hall95">BibTeX</a></font> , <li><a name="Benczur95" href="../../indices/a-tree/b/Bencz=uacute=r:Andr=aacute=s_A=.html">András A. Benczúr</a>: A Representation of Cuts within 6/5 Times the Edge Connectivity with Applications. 92-102 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Benczur95">BibTeX</a></font> <li><a name="PatersonS95" href="../../indices/a-tree/p/Paterson:Mike.html">Mike Paterson</a>, <a href="../../indices/a-tree/s/Srinivasan:Aravind.html">Aravind Srinivasan</a>: Contention Resolution with Bounded Delay. 104-113 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PatersonS95">BibTeX</a></font> <li><a name="Plaxton95" href="../../indices/a-tree/p/Plaxton:C=_Greg.html">C. Greg Plaxton</a>: Tight Bounds for a Distributed Selection Game with Applications to Fixed-Connection Machines. 114-122 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Plaxton95">BibTeX</a></font> <li><a name="Reif95" href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>: Efficient Parallel Solution of Sparse Eigenvalue and Eigenvector Problems. 123-132 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Reif95">BibTeX</a></font> <li><a name="Koiran95" href="../../indices/a-tree/k/Koiran:Pascal.html">Pascal Koiran</a>: Approximating the Volume of Definable Sets. 134-141 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Koiran95">BibTeX</a></font> <li><a name="DagumKLR95" href="../../indices/a-tree/d/Dagum:Paul.html">Paul Dagum</a>, <a href="../../indices/a-tree/k/Karp:Richard_M=.html">Richard M. Karp</a>, <a href="../../indices/a-tree/l/Luby:Michael.html">Michael Luby</a>, <a href="../../indices/a-tree/r/Ross:Sheldon_M=.html">Sheldon M. Ross</a>: An Optimal Algorithm for Monte Carlo Estimation (Extended Abstract). 142-149 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DagumKLR95">BibTeX</a></font> <li><a name="LubyRS95" href="../../indices/a-tree/l/Luby:Michael.html">Michael Luby</a>, <a href="../../indices/a-tree/r/Randall:Dana.html">Dana Randall</a>, <a href="../../indices/a-tree/s/Sinclair:Alistair.html">Alistair Sinclair</a>: Markov Chain Algorithms for Planar Lattice Structures (Extended Abstract). 150-159 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LubyRS95">BibTeX</a></font> <li><a name="MahajanR95" href="../../indices/a-tree/m/Mahajan:Sanjeev.html">Sanjeev Mahajan</a>, <a href="../../indices/a-tree/h/Hariharan:Ramesh.html">Ramesh Hariharan</a>: Derandomizing Semidefinite Programming Based Approximation Algorithms. 162-169 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MahajanR95">BibTeX</a></font> <li><a name="NaorR95" href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>, <a href="../../indices/a-tree/r/Reingold:Omer.html">Omer Reingold</a>: Synthesizers and Their Application to the Parallel Construction of Psuedo-Random Functions. 170-181 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NaorR95">BibTeX</a></font> <li><a name="NaorSS95" href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>, <a href="../../indices/a-tree/s/Schulman:Leonard_J=.html">Leonard J. Schulman</a>, <a href="../../indices/a-tree/s/Srinivasan:Aravind.html">Aravind Srinivasan</a>: Splitters and Near-Optimal Derandomization. 182-191 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NaorSS95">BibTeX</a></font> <li><a name="Torng95" href="../../indices/a-tree/t/Torng:Eric.html">Eric Torng</a>: A Unified Analysis of Paging and Caching. 194-203 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Torng95">BibTeX</a></font> <li><a name="BarveGV95" href="../../indices/a-tree/b/Barve:Rakesh_D=.html">Rakesh D. Barve</a>, <a href="../../indices/a-tree/g/Grove:Edward_F=.html">Edward F. Grove</a>, <a href="../../indices/a-tree/v/Vitter:Jeffrey_Scott.html">Jeffrey Scott Vitter</a>: Application-Controlled Paging for a Shared Cache (Extended Abstract). 204-213 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BarveGV95">BibTeX</a></font> <li><a name="KalyanasundaramP95" href="../../indices/a-tree/k/Kalyanasundaram:Bala.html">Bala Kalyanasundaram</a>, <a href="../../indices/a-tree/p/Pruhs:Kirk.html">Kirk Pruhs</a>: Speed is as Powerful as Clairvoyance. 214-221 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KalyanasundaramP95">BibTeX</a></font> <li><a name="Yannakakis95" href="../../indices/a-tree/y/Yannakakis:Mihalis.html">Mihalis Yannakakis</a>: Perspectives on Database Theory. 224-246 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Yannakakis95">BibTeX</a></font> <li><a name="Edelsbrunner95" href="../../indices/a-tree/e/Edelsbrunner:Herbert.html">Herbert Edelsbrunner</a>: Algebraic Decompositions of Non-Convex Polyhedra. 248-257 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Edelsbrunner95">BibTeX</a></font> <li><a name="GrigorievKV95" href="../../indices/a-tree/g/Grigoriev:Dima.html">Dima Grigoriev</a>, <a href="../../indices/a-tree/k/Karpinski:Marek.html">Marek Karpinski</a>, <a href="../../indices/a-tree/v/Vorobjov:Nicolai.html">Nicolai Vorobjov</a>: Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees. 258-265 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GrigorievKV95">BibTeX</a></font> <li><a name="DeyG95" href="../../indices/a-tree/d/Dey:Tamal_K=.html">Tamal K. Dey</a>, <a href="../../indices/a-tree/g/Guha:Sumanta.html">Sumanta Guha</a>: Optimal Algorithms for Curves on Surfaces. 266-274 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DeyG95">BibTeX</a></font> <li><a name="Barvinok95" href="../../indices/a-tree/b/Barvinok:Alexander_I=.html">Alexander I. Barvinok</a>: Integral Geometry of Higher-Dimensional Polytopes and the Average Case in Combinatorial Optimization. 275-283 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Barvinok95">BibTeX</a></font> <li><a name="GathenS95" href="../../indices/a-tree/g/Gathen:Joachim_von_zur.html">Joachim von zur Gathen</a>, <a href="../../indices/a-tree/s/Shparlinski:Igor.html">Igor Shparlinski</a>: Finding Points on Curves over Finite Fields (Extended Abstract). 284-292 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GathenS95">BibTeX</a></font> <li><a name="GoldreichRS95" href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/r/Rubinfeld:Ronitt.html">Ronitt Rubinfeld</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: Learning Polynomials with Queries: The Highly Noisy Case. 294-303 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldreichRS95">BibTeX</a></font> <li><a name="BshoutyM95" href="../../indices/a-tree/b/Bshouty:Nader_H=.html">Nader H. Bshouty</a>, <a href="../../indices/a-tree/m/Mansour:Yishay.html">Yishay Mansour</a>: Simple Learning Algorithms for Decision Trees and Multivariate Polynomials. 304-311 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BshoutyM95">BibTeX</a></font> <li><a name="AuerW95" href="../../indices/a-tree/a/Auer:Peter.html">Peter Auer</a>, <a href="../../indices/a-tree/w/Warmuth:Manfred_K=.html">Manfred K. Warmuth</a>: Tracking the Best Disjunction. 312-321 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AuerW95">BibTeX</a></font> <li><a name="AuerCFS95" href="../../indices/a-tree/a/Auer:Peter.html">Peter Auer</a>, <a href="../../indices/a-tree/c/Cesa=Bianchi:Nicol=ograve=.html">Nicolò Cesa-Bianchi</a>, <a href="../../indices/a-tree/f/Freund:Yoav.html">Yoav Freund</a>, <a href="../../indices/a-tree/s/Schapire:Robert_E=.html">Robert E. Schapire</a>: Gambling in a Rigged Casino: The Adversarial Multi-Arm Bandit Problem. 322-331 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AuerCFS95">BibTeX</a></font> <li><a name="FreundKMRRS95" href="../../indices/a-tree/f/Freund:Yoav.html">Yoav Freund</a>, <a href="../../indices/a-tree/k/Kearns:Michael_J=.html">Michael J. Kearns</a>, <a href="../../indices/a-tree/m/Mansour:Yishay.html">Yishay Mansour</a>, <a href="../../indices/a-tree/r/Ron:Dana.html">Dana Ron</a>, <a href="../../indices/a-tree/r/Rubinfeld:Ronitt.html">Ronitt Rubinfeld</a>, <a href="../../indices/a-tree/s/Schapire:Robert_E=.html">Robert E. Schapire</a>: Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries. 332-341 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FreundKMRRS95">BibTeX</a></font> <li><a name="SaksZ95" href="../../indices/a-tree/s/Saks:Michael_E=.html">Michael E. Saks</a>, <a href="../../indices/a-tree/z/Zhou:Shiyu.html">Shiyu Zhou</a>: RSPACE(S) \subseteq DSPACE(S<sup>3/2</sup>). 344-353 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SaksZ95">BibTeX</a></font> <li><a name="Ogihara95" href="../../indices/a-tree/o/Ogihara:Mitsunori.html">Mitsunori Ogihara</a>: Sparse P-Hard Sets Yield Space-Efficient Algorithms. 354-361 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ogihara95">BibTeX</a></font> <li><a name="CaiS95" href="../../indices/a-tree/c/Cai:Jin=yi.html">Jin-yi Cai</a>, <a href="../../indices/a-tree/s/Sivakumar:D=.html">D. Sivakumar</a>: The Resolution of a Hartmanis Conjecture. 362-371 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CaiS95">BibTeX</a></font> <li><a name="YaoDS95" href="../../indices/a-tree/y/Yao:F=_Frances.html">F. Frances Yao</a>, <a href="../../indices/a-tree/d/Demers:Alan_J=.html">Alan J. Demers</a>, <a href="../../indices/a-tree/s/Shenker:Scott.html">Scott Shenker</a>: A Scheduling Model for Reduced CPU Energy. 374-382 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/YaoDS95">BibTeX</a></font> <li><a name="AwerbuchAGKKV95" 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/g/Grove:Edward_F=.html">Edward F. Grove</a>, <a href="../../indices/a-tree/k/Kao:Ming=Yang.html">Ming-Yang Kao</a>, <a href="../../indices/a-tree/k/Krishnan:P=.html">P. Krishnan</a>, <a href="../../indices/a-tree/v/Vitter:Jeffrey_Scott.html">Jeffrey Scott Vitter</a>: Load Balancing in the L<sub>p</sub> Norm. 383-391 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AwerbuchAGKKV95">BibTeX</a></font> <li><a name="FiatMRW95" href="../../indices/a-tree/f/Fiat:Amos.html">Amos Fiat</a>, <a href="../../indices/a-tree/m/Mansour:Yishay.html">Yishay Mansour</a>, <a href="../../indices/a-tree/r/Ros=eacute=n:Adi.html">Adi Rosén</a>, <a href="../../indices/a-tree/w/Waarts:Orli.html">Orli Waarts</a>: Competitive Access Time via Dynamic Storage Rearrangement (Preliminary Version). 392-401 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FiatMRW95">BibTeX</a></font> <li><a name="Arora95" href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>: Reductions, Codes, PCPs, and Inapproximability. 404-413 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Arora95">BibTeX</a></font> <li><a name="Furer95" href="../../indices/a-tree/f/F=uuml=rer:Martin.html">Martin Fürer</a>: Improved Hardness Results for Approximating the Chromatic Number. 414-421 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Furer95">BibTeX</a></font> <li><a name="BellareGS95" href="../../indices/a-tree/b/Bellare:Mihir.html">Mihir Bellare</a>, <a href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: Free Bits, PCPs and Non-Approximability - Towards Tight Results. 422-431 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BellareGS95">BibTeX</a></font> <li><a name="BellareCHKS95" href="../../indices/a-tree/b/Bellare:Mihir.html">Mihir Bellare</a>, <a href="../../indices/a-tree/c/Coppersmith:Don.html">Don Coppersmith</a>, <a href="../../indices/a-tree/h/H=aring=stad:Johan.html">Johan Håstad</a>, <a href="../../indices/a-tree/k/Kiwi:Marcos_A=.html">Marcos A. Kiwi</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>: Linearity Testing in Characteristic Two. 432-441 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BellareCHKS95">BibTeX</a></font> <li><a name="BeigelE95" href="../../indices/a-tree/b/Beigel:Richard.html">Richard Beigel</a>, <a href="../../indices/a-tree/e/Eppstein:David.html">David Eppstein</a>: 3-Coloring in Time O(1.3446<sup>n</sup>): A No-MIS Algorithm. 444-452 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BeigelE95">BibTeX</a></font> <li><a name="HenzingerHK95" href="../../indices/a-tree/h/Henzinger:Monika_Rauch.html">Monika Rauch Henzinger</a>, <a href="../../indices/a-tree/h/Henzinger:Thomas_A=.html">Thomas A. Henzinger</a>, <a href="../../indices/a-tree/k/Kopke:Peter_W=.html">Peter W. Kopke</a>: Computing Simulations on Finite and Infinite Graphs. 453-462 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HenzingerHK95">BibTeX</a></font> <li><a name="Subramanian95" href="../../indices/a-tree/s/Subramanian:C=_R=.html">C. R. Subramanian</a>: Minimum Coloring Random and Semi-Random Graphs in Polynomial Expected Time. 463-472 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Subramanian95">BibTeX</a></font> <li><a name="AjtaiMW95" href="../../indices/a-tree/a/Ajtai:Mikl=oacute=s.html">Miklós Ajtai</a>, <a href="../../indices/a-tree/m/Megiddo:Nimrod.html">Nimrod Megiddo</a>, <a href="../../indices/a-tree/w/Waarts:Orli.html">Orli Waarts</a>: Improved Algorithms and Analysis for Secretary Problems and Generalizations. 473-482 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AjtaiMW95">BibTeX</a></font> <li><a name="Latombe95" href="../../indices/a-tree/l/Latombe:Jean=Claude.html">Jean-Claude Latombe</a>: Controllability, Recognizability, and Complexity Issues in Robot Motion Planning. 484-500 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Latombe95">BibTeX</a></font> <li><a name="OrlitskyR95" href="../../indices/a-tree/o/Orlitsky:Alon.html">Alon Orlitsky</a>, <a href="../../indices/a-tree/r/Roche:James_R=.html">James R. Roche</a>: Coding for Computing. 502-511 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/OrlitskyR95">BibTeX</a></font> <li><a name="AlonEL95" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/e/Edmonds:Jeff.html">Jeff Edmonds</a>, <a href="../../indices/a-tree/l/Luby:Michael.html">Michael Luby</a>: Linear Time Erasure Codes with Nearly Optimal Recovery (Extended Abstract). 512-519 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonEL95">BibTeX</a></font> <li><a name="BuhrmanFT95" href="../../indices/a-tree/b/Buhrman:Harry.html">Harry Buhrman</a>, <a href="../../indices/a-tree/f/Fortnow:Lance.html">Lance Fortnow</a>, <a href="../../indices/a-tree/t/Torenvliet:Leen.html">Leen Torenvliet</a>: Using Autoreducibility to Separate Complexity Classes. 520-527 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BuhrmanFT95">BibTeX</a></font> <li><a name="Watrous95" href="../../indices/a-tree/w/Watrous:John.html">John Watrous</a>: On One-Dimensional Quantum Cellular Automata. 528-537 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Watrous95">BibTeX</a></font> <li><a name="Impagliazzo95" href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>: Hard-Core Distributions for Somewhat Hard Problems. 538-545 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Impagliazzo95">BibTeX</a></font> <li><a name="MihailKR95" href="../../indices/a-tree/m/Mihail:Milena.html">Milena Mihail</a>, <a href="../../indices/a-tree/k/Kaklamanis:Christos.html">Christos Kaklamanis</a>, <a href="../../indices/a-tree/r/Rao:Satish.html">Satish Rao</a>: Efficient Access to Optical Bandwidth - Wavelength Routing on Directed Fiber Trees, Rings, and Trees of Rings. 548-557 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MihailKR95">BibTeX</a></font> <li><a name="ColeMS95" href="../../indices/a-tree/c/Cole:Richard.html">Richard Cole</a>, <a href="../../indices/a-tree/m/Maggs:Bruce_M=.html">Bruce M. Maggs</a>, <a href="../../indices/a-tree/s/Sitaraman:Ramesh_K=.html">Ramesh K. Sitaraman</a>: Routing on Butterfly Networks with Random Faults. 558-570 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ColeMS95">BibTeX</a></font> <li><a name="BeigelHK95" href="../../indices/a-tree/b/Beigel:Richard.html">Richard Beigel</a>, <a href="../../indices/a-tree/h/Hurwood:William.html">William Hurwood</a>, <a href="../../indices/a-tree/k/Kahale:Nabil.html">Nabil Kahale</a>: Fault Diagnosis in a Flash. 571-580 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BeigelHK95">BibTeX</a></font> <li><a name="HanennhalliP95" href="../../indices/a-tree/h/Hannenhalli:Sridhar.html">Sridhar Hannenhalli</a>, <a href="../../indices/a-tree/p/Pevzner:Pavel_A=.html">Pavel A. Pevzner</a>: Transforming Men into Mice (Polynomial Algorithm for Genomic Distance Problem). 581-592 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HanennhalliP95">BibTeX</a></font> <li><a name="Beals95" href="../../indices/a-tree/b/Beals:Robert.html">Robert Beals</a>: Algorithms for Matrix Groups and the Tits Alternative. 593-602 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Beals95">BibTeX</a></font> <li><a name="FerraginaG95" href="../../indices/a-tree/f/Ferragina:Paolo.html">Paolo Ferragina</a>, <a href="../../indices/a-tree/g/Grossi:Roberto.html">Roberto Grossi</a>: Optimal On-Line Search and Sublinear Time Update in String Matching. 604-612 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FerraginaG95">BibTeX</a></font> <li><a name="MargaritisS95" href="../../indices/a-tree/m/Margaritis:Dimitris.html">Dimitris Margaritis</a>, <a href="../../indices/a-tree/s/Skiena:Steven.html">Steven Skiena</a>: Reconstructing Strings from Substrings in Rounds. 613-620 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MargaritisS95">BibTeX</a></font> <li><a name="KarpWZ95" href="../../indices/a-tree/k/Karp:Richard_M=.html">Richard M. Karp</a>, <a href="../../indices/a-tree/w/Waarts:Orli.html">Orli Waarts</a>, <a href="../../indices/a-tree/z/Zweig:Geoffrey.html">Geoffrey Zweig</a>: The Bit Vector Intersection Problem (Preliminary Version). 621-630 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KarpWZ95">BibTeX</a></font> <li><a name="Kosaraju95" href="../../indices/a-tree/k/Kosaraju:S=_Rao.html">S. Rao Kosaraju</a>: Faster Algorithms for the Construction of Parameterized Suffix Trees (Preliminary Version). 631-637 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Kosaraju95">BibTeX</a></font> <li><a name="GrigniKP95" href="../../indices/a-tree/g/Grigni:Michelangelo.html">Michelangelo Grigni</a>, <a href="../../indices/a-tree/k/Koutsoupias:Elias.html">Elias Koutsoupias</a>, <a href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: An Approximation Scheme for Planar Graph TSP. 640-645 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GrigniKP95">BibTeX</a></font> <li><a name="Okasaki95" href="../../indices/a-tree/o/Okasaki:Chris.html">Chris Okasaki</a>: Amortization, Lazy Evaluation, and Persistence: Lists with Catenation via Lazy Linking. 646-654 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Okasaki95">BibTeX</a></font> <li><a name="Andersson95" href="../../indices/a-tree/a/Andersson:Arne.html">Arne Andersson</a>: Sublogarithmic Searching without Multiplications. 655-663 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Andersson95">BibTeX</a></font> <li><a name="HenzingerK95" href="../../indices/a-tree/h/Henzinger:Monika_Rauch.html">Monika Rauch Henzinger</a>, <a href="../../indices/a-tree/k/King:Valerie.html">Valerie King</a>: Fully Dynamic Biconnectivity and Transitive Closure. 664-672 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HenzingerK95">BibTeX</a></font> <li><a name="BeimelGP95" href="../../indices/a-tree/b/Beimel:Amos.html">Amos Beimel</a>, <a href="../../indices/a-tree/g/G=aacute=l:Anna.html">Anna Gál</a>, <a href="../../indices/a-tree/p/Paterson:Mike.html">Mike Paterson</a>: Lower Bounds for Monotone Span Programs. 674-681 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BeimelGP95">BibTeX</a></font> <li><a name="KrauseP95" href="../../indices/a-tree/k/Krause:Matthias.html">Matthias Krause</a>, <a href="../../indices/a-tree/p/Pudl=aacute=k:Pavel.html">Pavel Pudlák</a>: On Computing Boolean Functions by Sparse Real Polynomials. 682-691 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KrauseP95">BibTeX</a></font> <li><a name="BeameIP95" href="../../indices/a-tree/b/Beame:Paul.html">Paul Beame</a>, <a href="../../indices/a-tree/i/Impagliazzo:Russell.html">Russell Impagliazzo</a>, <a href="../../indices/a-tree/p/Pitassi:Toniann.html">Toniann Pitassi</a>: Improved Depth Lower Vounds for Small Distance Connectivity. 692-701 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BeameIP95">BibTeX</a></font> <li><a name="KuttenP95" href="../../indices/a-tree/k/Kutten:Shay.html">Shay Kutten</a>, <a href="../../indices/a-tree/p/Peleg:David.html">David Peleg</a>: Tight Fault Locality (Extended Abstract). 704-713 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KuttenP95">BibTeX</a></font> <li><a name="Schenk95" href="../../indices/a-tree/s/Schenk:Eric.html">Eric Schenk</a>: Faster Approximate Agreement with Multi-Writer Registers. 714-723 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Schenk95">BibTeX</a></font> <li><a name="GalilMY95" href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/m/Mayer:Alain_J=.html">Alain J. Mayer</a>, <a href="../../indices/a-tree/y/Yung:Moti.html">Moti Yung</a>: Resolving Message Complexity of Byzantine Agreement and beyond. 724-733 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GalilMY95">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:26 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
