focs92.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>33. FOCS 1992: Pittsburgh, Pennsylvania</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>33. <a href="index.html">FOCS</a> 1992: Pittsburgh, Pennsylvania</h1> 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, 24-27 October 1992. IEEE Computer Society <ul> <li><a name="AroraS92" href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>, <a href="../../indices/a-tree/s/Safra:Shmuel.html">Shmuel Safra</a>: Probabilistic Checking of Proofs; A New Characterization of NP. 2-13 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AroraS92">BibTeX</a></font> <li><a name="AroraLMSS92" href="../../indices/a-tree/a/Arora:Sanjeev.html">Sanjeev Arora</a>, <a href="../../indices/a-tree/l/Lund:Carsten.html">Carsten Lund</a>, <a href="../../indices/a-tree/m/Motwani:Rajeev.html">Rajeev Motwani</a>, <a href="../../indices/a-tree/s/Sudan:Madhu.html">Madhu Sudan</a>, <a href="../../indices/a-tree/s/Szegedy:Mario.html">Mario Szegedy</a>: Proof Verification and Hardness of Approximation Problems. 14-23 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AroraLMSS92">BibTeX</a></font> <li><a name="NisanSW92" href="../../indices/a-tree/n/Nisan:Noam.html">Noam Nisan</a>, <a href="../../indices/a-tree/s/Szemer=eacute=di:Endre.html">Endre Szemerédi</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: Undirected Connectivity in O(log ^1.5 n) Space. 24-29 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/NisanSW92">BibTeX</a></font> <li><a name="FennerFK92" href="../../indices/a-tree/f/Fenner:Stephen_A=.html">Stephen A. Fenner</a>, <a href="../../indices/a-tree/f/Fortnow:Lance.html">Lance Fortnow</a>, <a href="../../indices/a-tree/k/Kurtz:Stuart_A=.html">Stuart A. Kurtz</a>: The Isomorphism Conjecture Holds Relative to an Oracle. 30-39 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FennerFK92">BibTeX</a></font> <li><a name="BuchsbaumST92" href="../../indices/a-tree/b/Buchsbaum:Adam_L=.html">Adam L. Buchsbaum</a>, <a href="../../indices/a-tree/s/Sundar:Rajamani.html">Rajamani Sundar</a>, <a href="../../indices/a-tree/t/Tarjan:Robert_Endre.html">Robert Endre Tarjan</a>: Data Structural Bootstrapping, Linear Path Compression, and Catenable Heap Ordered Double Ended Queues. 40-49 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BuchsbaumST92">BibTeX</a></font> <li><a name="Rauch92" href="../../indices/a-tree/r/Rauch:Monika.html">Monika Rauch</a>: Fully Dynamic Biconnectivity in Graphs. 50-59 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Rauch92">BibTeX</a></font> <li><a name="EppsteinGIN92" href="../../indices/a-tree/e/Eppstein:David.html">David Eppstein</a>, <a href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/i/Italiano:Giuseppe_F=.html">Giuseppe F. Italiano</a>, <a href="../../indices/a-tree/n/Nissenzweig:Amnon.html">Amnon Nissenzweig</a>: Sparsification-A Technique for Speeding up Dynamic Graph Algorithms (Extended Abstract). 60-69 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/EppsteinGIN92">BibTeX</a></font> <li><a name="Hsu92" href="../../indices/a-tree/h/Hsu:Tsan=sheng.html">Tsan-sheng Hsu</a>: On Four-Connecting a Triconnected Graph (Extended Abstract). 70-79 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Hsu92">BibTeX</a></font> <li><a name="AgarwalEM92" href="../../indices/a-tree/a/Agarwal:Pankaj_K=.html">Pankaj K. Agarwal</a>, <a href="../../indices/a-tree/e/Eppstein:David.html">David Eppstein</a>, <a href="../../indices/a-tree/m/Matousek:Jir=iacute=.html">Jirí Matousek</a>: Dynamic Half-Space Reporting, Geometric Optimization, and Minimum Spanning Trees. 80-89 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AgarwalEM92">BibTeX</a></font> <li><a name="Mulmuley92" href="../../indices/a-tree/m/Mulmuley:Ketan.html">Ketan Mulmuley</a>: Randomized Geometric Algorithms and Pseudo-Random Generators (Extended Abstract). 90-100 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Mulmuley92">BibTeX</a></font> <li><a name="Kant92" href="../../indices/a-tree/k/Kant:Goos.html">Goos Kant</a>: Drawing Planar Graphs Using the lmc-Ordering (Extended Abstract). 101-110 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Kant92">BibTeX</a></font> <li><a name="Luks92" href="../../indices/a-tree/l/Luks:Eugene_M=.html">Eugene M. Luks</a>: Computing in Solvable Matrix Groups. 111-120 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Luks92">BibTeX</a></font> <li><a name="Giesbrecht92" href="../../indices/a-tree/g/Giesbrecht:Mark.html">Mark Giesbrecht</a>: Fast Algorithms for Matrix Normal Forms. 121-130 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Giesbrecht92">BibTeX</a></font> <li><a name="BiniP92" href="../../indices/a-tree/b/Bini:Dario.html">Dario Bini</a>, <a href="../../indices/a-tree/p/Pan:Victor_Y=.html">Victor Y. Pan</a>: Improved Parallel Polynomial Division and Its Extensions. 131-136 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BiniP92">BibTeX</a></font> <li><a name="AspnesW92" href="../../indices/a-tree/a/Aspnes:James.html">James Aspnes</a>, <a href="../../indices/a-tree/w/Waarts:Orli.html">Orli Waarts</a>: Randomized Consensus in Expected O(n log ^2 n) Operations Per Processor. 137-146 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AspnesW92">BibTeX</a></font> <li><a name="AumannR92" href="../../indices/a-tree/a/Aumann:Yonatan.html">Yonatan Aumann</a>, <a href="../../indices/a-tree/r/Rabin:Michael_O=.html">Michael O. Rabin</a>: Clock Construction in Fully Asynchronous Parallel Systems and PRAM Simulation (Extended Abstract). 147-156 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AumannR92">BibTeX</a></font> <li><a name="JayantiCT92" href="../../indices/a-tree/j/Jayanti:Prasad.html">Prasad Jayanti</a>, <a href="../../indices/a-tree/c/Chandra:Tushar_Deepak.html">Tushar Deepak Chandra</a>, <a href="../../indices/a-tree/t/Toueg:Sam.html">Sam Toueg</a>: Fault-tolerant Wait-free Shared Objects. 157-166 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/JayantiCT92">BibTeX</a></font> <li><a name="GradelM92" href="../../indices/a-tree/g/Gr=auml=del:Erich.html">Erich Grädel</a>, <a href="../../indices/a-tree/m/McColm:Gregory_L=.html">Gregory L. McColm</a>: Hierarchies in Transitive Closure Logic, Stratified Datalog and Infinitary Logic. 167-176 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GradelM92">BibTeX</a></font> <li><a name="AlurH92" href="../../indices/a-tree/a/Alur:Rajeev.html">Rajeev Alur</a>, <a href="../../indices/a-tree/h/Henzinger:Thomas_A=.html">Thomas A. Henzinger</a>: Back to the Future: Towards a Theory of Timed Regular Languages. 177-186 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlurH92">BibTeX</a></font> <li><a name="PitassiU92" href="../../indices/a-tree/p/Pitassi:Toniann.html">Toniann Pitassi</a>, <a href="../../indices/a-tree/u/Urquhart:Alasdair.html">Alasdair Urquhart</a>: The Complexity of the Hajós Calculus. 187-196 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PitassiU92">BibTeX</a></font> <li><a name="BlumKRS92" href="../../indices/a-tree/b/Blum:Avrim.html">Avrim Blum</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>, <a href="../../indices/a-tree/s/Saks:Michael_E=.html">Michael E. Saks</a>: A Decomposition Theorem and Bounds for Randomized Server Problems. 197-207 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BlumKRS92">BibTeX</a></font> <li><a name="KarlinPR92" href="../../indices/a-tree/k/Karlin:Anna_R=.html">Anna R. Karlin</a>, <a href="../../indices/a-tree/p/Phillips:Steven_J=.html">Steven J. Phillips</a>, <a href="../../indices/a-tree/r/Raghavan:Prabhakar.html">Prabhakar Raghavan</a>: Markov Paging (Extended Abstract). 208-217 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KarlinPR92">BibTeX</a></font> <li><a name="AzarBK92" href="../../indices/a-tree/a/Azar:Yossi.html">Yossi Azar</a>, <a href="../../indices/a-tree/b/Broder:Andrei_Z=.html">Andrei Z. Broder</a>, <a href="../../indices/a-tree/k/Karlin:Anna_R=.html">Anna R. Karlin</a>: On-line Load Balancing (Extended Abstract). 218-225 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AzarBK92">BibTeX</a></font> <li><a name="PlaxtonPS92" href="../../indices/a-tree/p/Plaxton:C=_Greg.html">C. Greg Plaxton</a>, <a href="../../indices/a-tree/p/Poonen:Bjorn.html">Bjorn Poonen</a>, <a href="../../indices/a-tree/s/Suel:Torsten.html">Torsten Suel</a>: Improved Lower Bounds for Shellsort. 226-235 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PlaxtonPS92">BibTeX</a></font> <li><a name="MiltersenPT92" href="../../indices/a-tree/m/Miltersen:Peter_Bro.html">Peter Bro Miltersen</a>, <a href="../../indices/a-tree/p/Paterson:Mike.html">Mike Paterson</a>, <a href="../../indices/a-tree/t/Tarui:Jun.html">Jun Tarui</a>: The Asymptotic Complexity of Merging Networks. 236-246 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MiltersenPT92">BibTeX</a></font> <li><a name="GalilP92" href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/p/Park:Kunsoo.html">Kunsoo Park</a>: Truly Alphabet-Independent Two-Dimensional Pattern Matching. 247-256 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GalilP92">BibTeX</a></font> <li><a name="DubinerZ92" href="../../indices/a-tree/d/Dubiner:Moshe.html">Moshe Dubiner</a>, <a href="../../indices/a-tree/z/Zwick:Uri.html">Uri Zwick</a>: Amplification and Percolation. 258-267 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DubinerZ92">BibTeX</a></font> <li><a name="Yao92" href="../../indices/a-tree/y/Yao:Andrew_Chi=Chih.html">Andrew Chi-Chih Yao</a>: Algebraic Decision Trees and Euler Characteristics. 268-277 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Yao92">BibTeX</a></font> <li><a name="Grolmusz92" href="../../indices/a-tree/g/Grolmusz:Vince.html">Vince Grolmusz</a>: Separating the Communication Complexities of MOD m and MOD p Circuits. 278-287 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Grolmusz92">BibTeX</a></font> <li><a name="CoppersmithS92" href="../../indices/a-tree/c/Coppersmith:Don.html">Don Coppersmith</a>, <a href="../../indices/a-tree/s/Schieber:Baruch.html">Baruch Schieber</a>: Lower Bounds on the Depth of Monotone Arithmetic Computations (Extended Summary). 288-295 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/CoppersmithS92">BibTeX</a></font> <li><a name="Kahale92" href="../../indices/a-tree/k/Kahale:Nabil.html">Nabil Kahale</a>: On the Second Eigenvalue and Linear Expansion of Regular Graphs. 296-303 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Kahale92">BibTeX</a></font> <li><a name="RabinovichSW92" href="../../indices/a-tree/r/Rabinovich:Yuri.html">Yuri Rabinovich</a>, <a href="../../indices/a-tree/s/Sinclair:Alistair.html">Alistair Sinclair</a>, <a href="../../indices/a-tree/w/Wigderson:Avi.html">Avi Wigderson</a>: Quadratic Dynamical Systems (Preliminary Version). 304-313 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/RabinovichSW92">BibTeX</a></font> <li><a name="Friedman92" href="../../indices/a-tree/f/Friedman:Joel.html">Joel Friedman</a>: On the Bit Extraction Problem. 314-319 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Friedman92">BibTeX</a></font> <li><a name="JerrumV92" href="../../indices/a-tree/j/Jerrum:Mark.html">Mark Jerrum</a>, <a href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>: A Mildly Exponential Approximation Algorithm for the Permanent. 320-326 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/JerrumV92">BibTeX</a></font> <li><a name="El-YanivFKT92" href="../../indices/a-tree/e/El=Yaniv:Ran.html">Ran El-Yaniv</a>, <a href="../../indices/a-tree/f/Fiat:Amos.html">Amos Fiat</a>, <a href="../../indices/a-tree/k/Karp:Richard_M=.html">Richard M. Karp</a>, <a href="../../indices/a-tree/t/Turpin:G=.html">G. Turpin</a>: Competitive Analysis of Financial Games. 327-333 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/El-YanivFKT92">BibTeX</a></font> <li><a name="AlonKRS92" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/k/Kalai:Gil.html">Gil Kalai</a>, <a href="../../indices/a-tree/r/Ricklin:Moty.html">Moty Ricklin</a>, <a href="../../indices/a-tree/s/Stockmeyer:Larry_J=.html">Larry J. Stockmeyer</a>: Lower Bounds on the Competitive Ratio for Mobile User Tracking and Distributed Job Scheduling (Extended Abstract). 334-343 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonKRS92">BibTeX</a></font> <li><a name="BartalR92" href="../../indices/a-tree/b/Bartal:Yair.html">Yair Bartal</a>, <a href="../../indices/a-tree/r/Ros=eacute=n:Adi.html">Adi Rosén</a>: The Distributed k-Server Problem-A Competitive Distributed Translator for k-Server Algorithms. 344-353 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BartalR92">BibTeX</a></font> <li><a name="MarcinkowskiP92" href="../../indices/a-tree/m/Marcinkowski:Jerzy.html">Jerzy Marcinkowski</a>, <a href="../../indices/a-tree/p/Pacholski:Leszek.html">Leszek Pacholski</a>: Undecidability of the Horn-Clause Implication Problem. 354-362 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MarcinkowskiP92">BibTeX</a></font> <li><a name="KozenPS92" href="../../indices/a-tree/k/Kozen:Dexter.html">Dexter Kozen</a>, <a href="../../indices/a-tree/p/Palsberg:Jens.html">Jens Palsberg</a>, <a href="../../indices/a-tree/s/Schwartzbach:Michael_I=.html">Michael I. Schwartzbach</a>: Efficient Inference of Partial Types. 363-371 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KozenPS92">BibTeX</a></font> <li><a name="BusscheGAG92" href="../../indices/a-tree/b/Bussche:Jan_Van_den.html">Jan Van den Bussche</a>, <a href="../../indices/a-tree/g/Gucht:Dirk_Van.html">Dirk Van Gucht</a>, <a href="../../indices/a-tree/a/Andries:Marc.html">Marc Andries</a>, <a href="../../indices/a-tree/g/Gyssens:Marc.html">Marc Gyssens</a>: On the Completeness of Object-Creating Query Languages (Extended Abstract). 372-379 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BusscheGAG92">BibTeX</a></font> <li><a name="LenhofS92" href="../../indices/a-tree/l/Lenhof:Hans=Peter.html">Hans-Peter Lenhof</a>, <a href="../../indices/a-tree/s/Smid:Michiel_H=_M=.html">Michiel H. M. Smid</a>: Enumerating the k Closest Pairs Optimally. 380-386 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LenhofS92">BibTeX</a></font> <li><a name="Clarkson92" href="../../indices/a-tree/c/Clarkson:Kenneth_L=.html">Kenneth L. Clarkson</a>: Safe and Effective Determinant Evaluation. 387-395 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Clarkson92">BibTeX</a></font> <li><a name="KatohTI92" href="../../indices/a-tree/k/Katoh:Naoki.html">Naoki Katoh</a>, <a href="../../indices/a-tree/t/Tokuyama:Takeshi.html">Takeshi Tokuyama</a>, <a href="../../indices/a-tree/i/Iwano:Kazuo.html">Kazuo Iwano</a>: On Minimum and Maximum Spanning Trees of Linearly Moving Points. 396-405 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KatohTI92">BibTeX</a></font> <li><a name="BlumG92" href="../../indices/a-tree/b/Blum:Manuel.html">Manuel Blum</a>, <a href="../../indices/a-tree/g/Goldreich:Oded.html">Oded Goldreich</a>: Towards a Computational Theory of Statistical Tests (Extended Abstract). 406-416 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BlumG92">BibTeX</a></font> <li><a name="AlonGMN92" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/m/Margalit:Oded.html">Oded Margalit</a>, <a href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>: Witnesses for Boolean Matrix Multiplication and for Shortest Paths. 417-426 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonGMN92">BibTeX</a></font> <li><a name="SantisP92" href="../../indices/a-tree/s/Santis:Alfredo_De.html">Alfredo De Santis</a>, <a href="../../indices/a-tree/p/Persiano:Giuseppe.html">Giuseppe Persiano</a>: Zero-Knowledge Proofs of Knowledge Without Interaction (Extended Abstract). 427-436 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/SantisP92">BibTeX</a></font> <li><a name="Yap92" href="../../indices/a-tree/y/Yap:Chee=Keng.html">Chee-Keng Yap</a>: Fast Unimodular Reduction: Planar Integer Lattices (Extended Abstract). 437-446 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Yap92">BibTeX</a></font> <li><a name="Blomer92" href="../../indices/a-tree/b/Bl=ouml=mer:Johannes.html">Johannes Blömer</a>: How to Denest Ramanujan's Nested Radicals. 447-456 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Blomer92">BibTeX</a></font> <li><a name="Eberly92" href="../../indices/a-tree/e/Eberly:Wayne.html">Wayne Eberly</a>: On Efficient Band Matrix Arithmetic. 457-463 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Eberly92">BibTeX</a></font> <li><a name="Gartner92" href="../../indices/a-tree/g/G=auml=rtner:Bernd.html">Bernd Gärtner</a>: A Subexponential Algorithm for Abstract Optimization Problems. 464-472 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Gartner92">BibTeX</a></font> <li><a name="AlonDLRY92" href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/d/Duke:Richard_A=.html">Richard A. Duke</a>, <a href="../../indices/a-tree/l/Lefmann:Hanno.html">Hanno Lefmann</a>, <a href="../../indices/a-tree/r/R=ouml=dl:Vojtech.html">Vojtech Rödl</a>, <a href="../../indices/a-tree/y/Yuster:Raphael.html">Raphael Yuster</a>: The Algorithmic Aspects of the Regularity Lemma (Extended Abstract). 473-481 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AlonDLRY92">BibTeX</a></font> <li><a name="LovaszS92" href="../../indices/a-tree/l/Lov=aacute=sz:L=aacute=szl=oacute=.html">László Lovász</a>, <a href="../../indices/a-tree/s/Simonovits:Mikl=oacute=s.html">Miklós Simonovits</a>: On the Randomized Complexity of Volume and Diameter. 482-491 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LovaszS92">BibTeX</a></font> <li><a name="HelmboldLL92" href="../../indices/a-tree/h/Helmbold:David_P=.html">David P. Helmbold</a>, <a href="../../indices/a-tree/l/Littlestone:Nick.html">Nick Littlestone</a>, <a href="../../indices/a-tree/l/Long:Philip_M=.html">Philip M. Long</a>: Apple Tasting and Nearly One-Sided Learning. 493-502 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HelmboldLL92">BibTeX</a></font> <li><a name="ArLRS92" href="../../indices/a-tree/a/Ar:Sigal.html">Sigal Ar</a>, <a href="../../indices/a-tree/l/Lipton:Richard_J=.html">Richard J. Lipton</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>: Reconstructing Algebraic Functions from Mixed Data. 503-512 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ArLRS92">BibTeX</a></font> <li><a name="BshoutyC92" href="../../indices/a-tree/b/Bshouty:Nader_H=.html">Nader H. Bshouty</a>, <a href="../../indices/a-tree/c/Cleve:Richard.html">Richard Cleve</a>: On the Exact Learning of Formulas in Parallel (Extended Abstract). 513-522 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BshoutyC92">BibTeX</a></font> <li><a name="AizensteinHP92" href="../../indices/a-tree/a/Aizenstein:Howard.html">Howard Aizenstein</a>, <a href="../../indices/a-tree/h/Hellerstein:Lisa.html">Lisa Hellerstein</a>, <a href="../../indices/a-tree/p/Pitt:Leonard.html">Leonard Pitt</a>: Read-Thrice DNF Is Hard to Learn With Membership and Equivalence Queries. 523-532 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AizensteinHP92">BibTeX</a></font> <li><a name="Tamaki92" href="../../indices/a-tree/t/Tamaki:Hisao.html">Hisao Tamaki</a>: Efficient Self-Embedding of Butterfly Networks with Random Faults. 533-541 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Tamaki92">BibTeX</a></font> <li><a name="LeightonMS92" href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</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>: On the Fault Tolerance of Some Popular Bounded-Degree Networks. 542-552 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LeightonMS92">BibTeX</a></font> <li><a name="FeigeR92" href="../../indices/a-tree/f/Feige:Uriel.html">Uriel Feige</a>, <a href="../../indices/a-tree/r/Raghavan:Prabhakar.html">Prabhakar Raghavan</a>: Exact Analysis of Hot-Potato Routing (Extended Abstract). 553-562 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FeigeR92">BibTeX</a></font> <li><a name="FelperinRU92" href="../../indices/a-tree/f/Felperin:Sergio_A=.html">Sergio A. Felperin</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>: A Theory of Wormhole Routing in Parallel Computers (Extended Abstract). 563-572 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FelperinRU92">BibTeX</a></font> <li><a name="MitchellPA92" href="../../indices/a-tree/m/Mitchell:Joseph_S=_B=.html">Joseph S. B. Mitchell</a>, <a href="../../indices/a-tree/p/Piatko:Christine_D=.html">Christine D. Piatko</a>, <a href="../../indices/a-tree/a/Arkin:Esther_M=.html">Esther M. Arkin</a>: Computing a Shortest k-Link Path in a Polygon. 573-582 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/MitchellPA92">BibTeX</a></font> <li><a name="AggarwalBKKS92" href="../../indices/a-tree/a/Aggarwal:Alok.html">Alok Aggarwal</a>, <a href="../../indices/a-tree/b/Bar=Noy:Amotz.html">Amotz Bar-Noy</a>, <a href="../../indices/a-tree/k/Khuller:Samir.html">Samir Khuller</a>, <a href="../../indices/a-tree/k/Kravets:Dina.html">Dina Kravets</a>, <a href="../../indices/a-tree/s/Schieber:Baruch.html">Baruch Schieber</a>: Efficient Minimum Cost Matching Using Quadrangle Inequality. 583-592 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AggarwalBKKS92">BibTeX</a></font> <li><a name="Wagener92" href="../../indices/a-tree/w/Wagener:Hubert.html">Hubert Wagener</a>: Optimal Parallel Hull Construction for Simple Polygons in \calO(log log n) Time. 593-599 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Wagener92">BibTeX</a></font> <li><a name="ColeH92" href="../../indices/a-tree/c/Cole:Richard.html">Richard Cole</a>, <a href="../../indices/a-tree/h/Hariharan:Ramesh.html">Ramesh Hariharan</a>: Tighter Bounds on the Exact Complexity of String Matching (Extended Abstract). 600-609 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ColeH92">BibTeX</a></font> <li><a name="KenyonK92" href="../../indices/a-tree/k/Kenyon:Claire.html">Claire Kenyon</a>, <a href="../../indices/a-tree/k/Kenyon:Richard.html">Richard Kenyon</a>: Tiling a Polygon with Rectangles. 610-619 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KenyonK92">BibTeX</a></font> <li><a name="ChvatalR92" href="../../indices/a-tree/c/Chv=aacute=tal:Vasek.html">Vasek Chvátal</a>, <a href="../../indices/a-tree/r/Reed:B=.html">B. Reed</a>: Mick Gets Some (the Odds Are on His Side). 620-627 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChvatalR92">BibTeX</a></font> <li><a name="HagerupR92" href="../../indices/a-tree/h/Hagerup:Torben.html">Torben Hagerup</a>, <a href="../../indices/a-tree/r/Raman:Rajeev.html">Rajeev Raman</a>: Waste Makes Haste: Tight Bounds for Loose Parallel Sorting. 628-637 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HagerupR92">BibTeX</a></font> <li><a name="ChaudhuriR92" href="../../indices/a-tree/c/Chaudhuri:Shiva.html">Shiva Chaudhuri</a>, <a href="../../indices/a-tree/r/Radhakrishnan:Jaikumar.html">Jaikumar Radhakrishnan</a>: The Complexity of Parallel Prefix Problems on Small Domains. 638-647 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChaudhuriR92">BibTeX</a></font> <li><a name="Cohen92" href="../../indices/a-tree/c/Cohen:Edith.html">Edith Cohen</a>: Approximate Max Flow on Small Depth Networks. 648-658 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Cohen92">BibTeX</a></font> <li><a name="Radzik92" href="../../indices/a-tree/r/Radzik:Tomasz.html">Tomasz Radzik</a>: Newton's Method for Fractional Combinatorial Optimization. 659-669 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Radzik92">BibTeX</a></font> <li><a name="ConfortiC92" href="../../indices/a-tree/c/Conforti:Michele.html">Michele Conforti</a>, <a href="../../indices/a-tree/c/Cornu=eacute=jols:G=eacute=rard.html">Gérard Cornuéjols</a>: A Class of Logic Problems Solvable by Linear Programming. 670-675 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ConfortiC92">BibTeX</a></font> <li><a name="Toledo92" href="../../indices/a-tree/t/Toledo:Sivan.html">Sivan Toledo</a>: Maximizing Non-Linear Concave Functions in Fixed Dimension. 676-685 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Toledo92">BibTeX</a></font> <li><a name="AjtaiKS92" href="../../indices/a-tree/a/Ajtai:Mikl=oacute=s.html">Miklós Ajtai</a>, <a href="../../indices/a-tree/k/Koml=oacute=s:J=aacute=nos.html">János Komlós</a>, <a href="../../indices/a-tree/s/Szemer=eacute=di:Endre.html">Endre Szemerédi</a>: Halvers and Expanders. 686-692 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AjtaiKS92">BibTeX</a></font> <li><a name="AjtaiABCHNS92" href="../../indices/a-tree/a/Ajtai:Mikl=oacute=s.html">Miklós Ajtai</a>, <a href="../../indices/a-tree/a/Alon:Noga.html">Noga Alon</a>, <a href="../../indices/a-tree/b/Bruck:Jehoshua.html">Jehoshua Bruck</a>, <a href="../../indices/a-tree/c/Cypher:Robert.html">Robert Cypher</a>, <a href="../../indices/a-tree/h/Ho:Ching=Tien.html">Ching-Tien Ho</a>, <a href="../../indices/a-tree/n/Naor:Moni.html">Moni Naor</a>, <a href="../../indices/a-tree/s/Szemer=eacute=di:Endre.html">Endre Szemerédi</a>: Fault Tolerant Graphs, Perfect Hash Functions and Disjoint Paths. 693-702 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AjtaiABCHNS92">BibTeX</a></font> <li><a name="PanRT92" href="../../indices/a-tree/p/Pan:Victor_Y=.html">Victor Y. Pan</a>, <a href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>, <a href="../../indices/a-tree/t/Tate:Stephen_R=.html">Stephen R. Tate</a>: The Power of Combining the Techiques of Algebraic and Numerical Computing: Improved Approximate Multipoint Polynomial Evaluation and Improved Multipole Algorithms. 703-713 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PanRT92">BibTeX</a></font> <li><a name="KaltofenP92" href="../../indices/a-tree/k/Kaltofen:Erich.html">Erich Kaltofen</a>, <a href="../../indices/a-tree/p/Pan:Victor_Y=.html">Victor Y. Pan</a>: Processor-Efficient Parallel Solution of Linear Systems II: The Positive Characteristic and Singular Cases (Extended Abstract). 714-723 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KaltofenP92">BibTeX</a></font> <li><a name="Schulman92" href="../../indices/a-tree/s/Schulman:Leonard_J=.html">Leonard J. Schulman</a>: Communication on Noisy Channels: A Coding Theorem for Computation. 724-733 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Schulman92">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
