focs82.html
Click here to view the file
or
click here to download the file
File contents
<html><head><title>23. FOCS 1982: Chicago, Illinois</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>23. <a href="index.html">FOCS</a> 1982: Chicago, Illinois</h1> 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, 3-5 November 1982. IEEE Computer Society <ul> <li><a name="ChandraSV82" href="../../indices/a-tree/c/Chandra:Ashok_K=.html">Ashok K. Chandra</a>, <a href="../../indices/a-tree/s/Stockmeyer:Larry_J=.html">Larry J. Stockmeyer</a>, <a href="../../indices/a-tree/v/Vishkin:Uzi.html">Uzi Vishkin</a>: A Complexity Theory for Unbounded Fan-In Parallelism. 1-13 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChandraSV82">BibTeX</a></font> <li><a name="Papadimitriou82" href="../../indices/a-tree/p/Papadimitriou:Christos_H=.html">Christos H. Papadimitriou</a>: On the Complexity of Unique Solutions. 14-20 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Papadimitriou82">BibTeX</a></font> <li><a name="Huynh82" href="../../indices/a-tree/h/Huynh:Thiet=Dung.html">Thiet-Dung Huynh</a>: Deciding the Inequivalence of Context-Free Grammars with 1-Letter Terminal Alphabet is Sigma_2^P-Complete. 21-31 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Huynh82">BibTeX</a></font> <li><a name="Lagarias82" href="../../indices/a-tree/l/Lagarias:J=_C=.html">J. C. Lagarias</a>: The Computational Complexity of Simultaneous Diophantine Approximation Problems. 32-39 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Lagarias82">BibTeX</a></font> <li><a name="VaziraniV82" href="../../indices/a-tree/v/Vazirani:Umesh_V=.html">Umesh V. Vazirani</a>, <a href="../../indices/a-tree/v/Vazirani:Vijay_V=.html">Vijay V. Vazirani</a>: A Natural Encoding Scheme Proved Probabilistic Polynomial Complete. 40-44 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/VaziraniV82">BibTeX</a></font> <li><a name="ReischS82" href="../../indices/a-tree/r/Reisch:Stefan.html">Stefan Reisch</a>, <a href="../../indices/a-tree/s/Schnitger:Georg.html">Georg Schnitger</a>: Three Applications of Kolmogorov-Complexity. 45-52 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ReischS82">BibTeX</a></font> <li><a name="Paul82" href="../../indices/a-tree/p/Paul:Wolfgang_J=.html">Wolfgang J. Paul</a>: On-Line Simulation of k+1 Tapes by k Tapes Requires Nonlinear Time. 53-56 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Paul82">BibTeX</a></font> <li><a name="Kaltofen82" href="../../indices/a-tree/k/Kaltofen:Erich.html">Erich Kaltofen</a>: A Polynomial-Time Reduction from Bivariate to Univariate Integral Polynomial Factorization. 57-64 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Kaltofen82">BibTeX</a></font> <li><a name="BorodinGH82" href="../../indices/a-tree/b/Borodin:Allan.html">Allan Borodin</a>, <a href="../../indices/a-tree/g/Gathen:Joachim_von_zur.html">Joachim von zur Gathen</a>, <a href="../../indices/a-tree/h/Hopcroft:John_E=.html">John E. Hopcroft</a>: Fast Parallel Matrix and GCD Computations. 65-71 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BorodinGH82">BibTeX</a></font> <li><a name="Sturtivant82" href="../../indices/a-tree/s/Sturtivant:Carl.html">Carl Sturtivant</a>: Generalised Symmetries of Polynomials in Algebraic Complexity. 72-79 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Sturtivant82">BibTeX</a></font> <li><a name="ChorLR82" href="../../indices/a-tree/c/Chor:Benny.html">Benny Chor</a>, <a href="../../indices/a-tree/l/Leiserson:Charles_E=.html">Charles E. Leiserson</a>, <a href="../../indices/a-tree/r/Rivest:Ronald_L=.html">Ronald L. Rivest</a>: An Application of Number Theory to the Organization of Raster-Graphics Memory (Extended Abstract). 92-99 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChorLR82">BibTeX</a></font> <li><a name="AdlemanM82" href="../../indices/a-tree/a/Adleman:Leonard_M=.html">Leonard M. Adleman</a>, <a href="../../indices/a-tree/m/McDonnell:Robert.html">Robert McDonnell</a>: An Application of Higher Reciprocity to Computational Number Theory (Abstract). 100-106 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/AdlemanM82">BibTeX</a></font> <li><a name="Karmarkar82" href="../../indices/a-tree/k/Karmarkar:Narendra.html">Narendra Karmarkar</a>: Probabilistic Analysis of Some Bin-Packing Problems. 107-111 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Karmarkar82">BibTeX</a></font> <li><a name="BlumM82" href="../../indices/a-tree/b/Blum:Manuel.html">Manuel Blum</a>, <a href="../../indices/a-tree/m/Micali:Silvio.html">Silvio Micali</a>: How to Generate Cryptographically Strong Sequences of Pseudo Random Bits. 112-117 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BlumM82">BibTeX</a></font> <li><a name="GalilHLSW82" href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/h/Hoffmann:Christoph_M=.html">Christoph M. Hoffmann</a>, <a href="../../indices/a-tree/l/Luks:Eugene_M=.html">Eugene M. Luks</a>, <a href="../../indices/a-tree/s/Schnorr:Claus=Peter.html">Claus-Peter Schnorr</a>, <a href="../../indices/a-tree/w/Weber:Andreas.html">Andreas Weber</a>: An O(n^3 log n) Deterministic and an O(n^3) Probabilistic Isomorphism Test for Trivalent Graphs. 118-125 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GalilHLSW82">BibTeX</a></font> <li><a name="Jerrum82" href="../../indices/a-tree/j/Jerrum:Mark.html">Mark Jerrum</a>: A Compact Representation for Permutation Groups. 126-133 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Jerrum82">BibTeX</a></font> <li><a name="GoldwasserMT82" href="../../indices/a-tree/g/Goldwasser:Shafi.html">Shafi Goldwasser</a>, <a href="../../indices/a-tree/m/Micali:Silvio.html">Silvio Micali</a>, <a href="../../indices/a-tree/t/Tong:Po.html">Po Tong</a>: Why and How to Establish a Private Code on a Public Network (Extended Abstract). 134-144 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GoldwasserMT82">BibTeX</a></font> <li><a name="Shamir82" href="../../indices/a-tree/s/Shamir:Adi.html">Adi Shamir</a>: A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Cryptosystem. 145-152 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Shamir82">BibTeX</a></font> <li><a name="Plumstead82" href="../../indices/a-tree/p/Plumstead:Joan_B=.html">Joan B. Plumstead</a>: Inferring a Sequence Generated by a Linear Congruence. 153-159 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Plumstead82">BibTeX</a></font> <li><a name="FredmanKS82" href="../../indices/a-tree/f/Fredman:Michael_L=.html">Michael L. Fredman</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>: Storing a Sparse Table with O(1) Worst Case Access Time. 165-169 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/FredmanKS82">BibTeX</a></font> <li><a name="Mehlhorn82" href="../../indices/a-tree/m/Mehlhorn:Kurt.html">Kurt Mehlhorn</a>: On the Program Size of Perfect and Universal Hash Functions. 170-175 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Mehlhorn82">BibTeX</a></font> <li><a name="Vardi82" href="../../indices/a-tree/v/Vardi:Moshe_Y=.html">Moshe Y. Vardi</a>: On Decomposition of Relational Databases. 176-185 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Vardi82">BibTeX</a></font> <li><a name="ODunlaingY82" href="../../indices/a-tree/=/=Oacute==D=uacute=nlaing:Colm.html">Colm Ó'Dúnlaing</a>, <a href="../../indices/a-tree/y/Yap:Chee=Keng.html">Chee-Keng Yap</a>: Generic Transformation of Data Structures. 186-195 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ODunlaingY82">BibTeX</a></font> <li><a name="DolevRS82" href="../../indices/a-tree/d/Dolev:Danny.html">Danny Dolev</a>, <a href="../../indices/a-tree/r/Reischuk:R=uuml=diger.html">Rüdiger Reischuk</a>, <a href="../../indices/a-tree/s/Strong:H=_Raymond.html">H. Raymond Strong</a>: `Eventual' Is Earlier than `Immediate'. 196-203 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/DolevRS82">BibTeX</a></font> <li><a name="Halpern82" href="../../indices/a-tree/h/Halpern:Joseph_Y=.html">Joseph Y. Halpern</a>: Deterministic Process Logic Is Elementary. 204-216 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Halpern82">BibTeX</a></font> <li><a name="QueilleS82" href="../../indices/a-tree/q/Queille:Jean=Pierre.html">Jean-Pierre Queille</a>, <a href="../../indices/a-tree/s/Sifakis:Joseph.html">Joseph Sifakis</a>: A Temporal Logic to Deal with Fairness in Transition Systems. 217-225 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/QueilleS82">BibTeX</a></font> <li><a name="Iwama82" href="../../indices/a-tree/i/Iwama:Kazuo.html">Kazuo Iwama</a>: On Equations Including String Variables. 226-235 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Iwama82">BibTeX</a></font> <li><a name="BeauquierL82" href="../../indices/a-tree/b/Beauquier:Joffroy.html">Joffroy Beauquier</a>, <a href="../../indices/a-tree/l/Latteux:Michel.html">Michel Latteux</a>: Substitution of Bounded Rational Cone. 236-243 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/BeauquierL82">BibTeX</a></font> <li><a name="JohnsonV82" href="../../indices/a-tree/j/Johnson:Donald_B=.html">Donald B. Johnson</a>, <a href="../../indices/a-tree/v/Venkatesan:Shankar_M=.html">Shankar M. Venkatesan</a>: Parallel Algorithms for Minimum Cuts and Maximum Flows in Planar Networks (Preliminary Version). 244-254 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/JohnsonV82">BibTeX</a></font> <li><a name="GalilMG82" href="../../indices/a-tree/g/Galil:Zvi.html">Zvi Galil</a>, <a href="../../indices/a-tree/m/Micali:Silvio.html">Silvio Micali</a>, <a href="../../indices/a-tree/g/Gabow:Harold_N=.html">Harold N. Gabow</a>: Priority Queues with Variable Priority and an O(EV log V) Algorithm for Finding a Maximal Weighted Matching in General Graphs. 255-261 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/GalilMG82">BibTeX</a></font> <li><a name="ChungMST82" href="../../indices/a-tree/c/Chung:Moon=Jung.html">Moon-Jung Chung</a>, <a href="../../indices/a-tree/m/Makedon:Fillia.html">Fillia Makedon</a>, <a href="../../indices/a-tree/s/Sudborough:Ivan_Hal.html">Ivan Hal Sudborough</a>, <a href="../../indices/a-tree/t/Turner:Jonathan_S=.html">Jonathan S. Turner</a>: Polynomial Time Algorithms for the Min Cut Problem on Degree Restricted Trees. 262-271 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/ChungMST82">BibTeX</a></font> <li><a name="Stout82" href="../../indices/a-tree/s/Stout:Quentin_F=.html">Quentin F. Stout</a>: Using Clerks in Parallel Processing. 272-279 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Stout82">BibTeX</a></font> <li><a name="HopcroftJW82" href="../../indices/a-tree/h/Hopcroft:John_E=.html">John E. Hopcroft</a>, <a href="../../indices/a-tree/j/Joseph:Deborah.html">Deborah Joseph</a>, <a href="../../indices/a-tree/w/Whitesides:Sue.html">Sue Whitesides</a>: On the Movement of Robot Arms in 2-Dimensional Bounded Regions. 280-289 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/HopcroftJW82">BibTeX</a></font> <li><a name="Reif82" href="../../indices/a-tree/r/Reif:John_H=.html">John H. Reif</a>: Parallel Time O(log N) Acceptance of Deterministic CFLs. 290-296 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Reif82">BibTeX</a></font> <li><a name="LeightonL82" href="../../indices/a-tree/l/Leighton:Frank_Thomson.html">Frank Thomson Leighton</a>, <a href="../../indices/a-tree/l/Leiserson:Charles_E=.html">Charles E. Leiserson</a>: Wafer-Scale Integration of Systolic Arrays (Extended Abstract). 297-311 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/LeightonL82">BibTeX</a></font> <li><a name="KarmarkarK82" href="../../indices/a-tree/k/Karmarkar:Narendra.html">Narendra Karmarkar</a>, <a href="../../indices/a-tree/k/Karp:Richard_M=.html">Richard M. Karp</a>: An Efficient Approximation Scheme for the One-Dimensional Bin-Packing Problem. 312-320 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/KarmarkarK82">BibTeX</a></font> <li><a name="Ursic82" href="../../indices/a-tree/u/Ursic:Silvio.html">Silvio Ursic</a>: The Ellipsoid Algorithm for Linear Inequalities in Exact Arithmetic. 321-326 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ursic82">BibTeX</a></font> <li><a name="YamnitskyL82" href="../../indices/a-tree/y/Yamnitsky:Boris.html">Boris Yamnitsky</a>, <a href="../../indices/a-tree/l/Levin:Leonid_A=.html">Leonid A. Levin</a>: An Old Linear Programming Algorithm Runs in Polynomial Time. 327-328 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/YamnitskyL82">BibTeX</a></font> <li><a name="Megiddo82" href="../../indices/a-tree/m/Megiddo:Nimrod.html">Nimrod Megiddo</a>: Linear-Time Algorithms for Linear Programming in R^3 and Related Problems. 329-338 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Megiddo82">BibTeX</a></font> <li><a name="Chazelle82" href="../../indices/a-tree/c/Chazelle:Bernard.html">Bernard Chazelle</a>: A Theorem on Polygon Cutting with Applications. 339-349 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Chazelle82">BibTeX</a></font> <li><a name="PreparataL82" href="../../indices/a-tree/p/Preparata:Franco_P=.html">Franco P. Preparata</a>, <a href="../../indices/a-tree/l/Lipski_Jr=:Witold.html">Witold Lipski Jr.</a>: Three Layers Are Enough. 350-357 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/PreparataL82">BibTeX</a></font> <li><a name="Lengauer82" href="../../indices/a-tree/l/Lengauer:Thomas.html">Thomas Lengauer</a>: The Complexity of Compacting Hierarchically Specified Layouts of Integrated Circuits (Preliminary Version). 358-368 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Lengauer82">BibTeX</a></font> <li><a name="Ramachandran82" href="../../indices/a-tree/r/Ramachandran:Vijaya.html">Vijaya Ramachandran</a>: On Driving Many Long Lines in a VLSI Layout. 369-378 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Ramachandran82">BibTeX</a></font> <li><a name="Kedem82" href="../../indices/a-tree/k/Kedem:Zvi_M=.html">Zvi M. Kedem</a>: Optimal Allocation of Computational Resources in VLSI. 379-385 <font size="-3"><a href="http://dblp.uni-trier.de/rec/bibtex/conf/focs/Kedem82">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:24 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
