Valid HTML 4.0! Valid CSS!
%%% -*-BibTeX-*-
%%% ====================================================================
%%%  BibTeX-file{
%%%     author          = "Nelson H. F. Beebe",
%%%     version         = "2.06",
%%%     date            = "14 October 2017",
%%%     time            = "08:48:20 MDT",
%%%     filename        = "focs1980.bib",
%%%     address         = "University of Utah
%%%                        Department of Mathematics, 110 LCB
%%%                        155 S 1400 E RM 233
%%%                        Salt Lake City, UT 84112-0090
%%%                        USA",
%%%     telephone       = "+1 801 581 5254",
%%%     FAX             = "+1 801 581 4148",
%%%     URL             = "http://www.math.utah.edu/~beebe",
%%%     checksum        = "12215 2895 10807 104884",
%%%     email           = "beebe at math.utah.edu, beebe at acm.org,
%%%                        beebe at computer.org (Internet)",
%%%     codetable       = "ISO/ASCII",
%%%     keywords        = "bibliography; BibTeX; Foundations of Computer
%%%                        Science (FOCS)",
%%%     license         = "public domain",
%%%     supported       = "yes",
%%%     docstring       = "This is a bibliography of publications in the
%%%                        annual IEEE symposia on the Foundations of
%%%                        Computer Science (CODEN ASFPDV, ISSN
%%%                        0272-5428) for the decade 1980--1989.
%%%
%%%                        At version 2.06, the year coverage looked like
%%%                        this:
%%%
%%%                             1980 (   1)    1984 (  61)    1988 (  59)
%%%                             1981 (   1)    1985 (   1)    1989 (  99)
%%%                             1982 (   2)    1986 (   1)
%%%                             1983 (   1)    1987 (   2)
%%%
%%%                             InProceedings:  218
%%%                             Proceedings:     10
%%%
%%%                             Total entries:  228
%%%
%%%                        The checksum field above contains a CRC-16
%%%                        checksum as the first value, followed by the
%%%                        equivalent of the standard UNIX wc (word
%%%                        count) utility output of lines, words, and
%%%                        characters.  This is produced by Robert
%%%                        Solovay's checksum utility.",
%%%  }
%%% ====================================================================
%%% ====================================================================
%%% Acknowledgement abbreviations:
@String{ack-nhfb = "Nelson H. F. Beebe,
                    University of Utah,
                    Department of Mathematics, 110 LCB,
                    155 S 1400 E RM 233,
                    Salt Lake City, UT 84112-0090, USA,
                    Tel: +1 801 581 5254,
                    FAX: +1 801 585 1640, +1 801 581 4148,
                    e-mail: \path|beebe@math.utah.edu|,
                            \path|beebe@acm.org|,
                            \path|beebe@computer.org| (Internet),
                    URL: \path|http://www.math.utah.edu/~beebe/|"}

%%% ====================================================================
%%% Publisher abbreviations:
@String{pub-IEEE                = "IEEE Computer Society Press"}

@String{pub-IEEE:adr            = "1109 Spring Street, Suite 300,
                                  Silver Spring, MD 20910, USA"}

%%% ====================================================================
%%% Bibliography entries:
@InProceedings{Blum:1982:HGC,
  author =       "Manuel Blum and Silvio Micali",
  title =        "How to Generate Cryptographically Strong Sequences of
                 Pseudo-Random Bits",
  crossref =     "IEEE:1982:ASF",
  pages =        "112--117",
  year =         "1982",
  DOI =          "https://doi.org/10.1109/SFCS.1982.72",
  bibdate =      "Wed Dec 21 06:47:00 2011",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/cryptography.bib;
                 http://www.math.utah.edu/pub/tex/bib/focs1980.bib;
                 http://www.math.utah.edu/pub/tex/bib/prng.bib",
  acknowledgement = ack-nhfb,
  xxpages =      "464--479",
}

@InProceedings{Beame:1984:LDC,
  author =       "P. W. Beame and S. A. Cook and H. J. Hoover",
  title =        "Log Depth Circuits for Division and Related Problems",
  crossref =     "IEEE:1984:ASF",
  pages =        "1--6",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kannan:1984:SPA,
  author =       "R. Kannan and G. Miller and L. Rudolph",
  title =        "Sublinear Parallel Algorithm for Computing the
                 Greatest Common Divisor of Two Integers",
  crossref =     "IEEE:1984:ASF",
  pages =        "7--11",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Anonymous:1984:ASF,
  author =       "Anonymous",
  title =        "{25th Annual Symposium on Foundations of Computer
                 Science}",
  crossref =     "IEEE:1984:ASF",
  pages =        "i--xii",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Tarjan:1984:FBC,
  author =       "R. E. Tarjan and U. Vishkin",
  title =        "Finding Biconnected Components and Computing Tree
                 Functions in Logarithmic Parallel Time",
  crossref =     "IEEE:1984:ASF",
  pages =        "12--20",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Eberly:1984:VFP,
  author =       "W. Eberly",
  title =        "Very Fast Parallel Matrix and Polynomial Arithmetic",
  crossref =     "IEEE:1984:ASF",
  pages =        "21--30",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{vonzurGathen:1984:PP,
  author =       "J. von zur Gathen",
  title =        "Parallel Powering",
  crossref =     "IEEE:1984:ASF",
  pages =        "31--36",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Fiat:1984:PAN,
  author =       "A. Fiat and A. Shamir",
  title =        "Polymorphic Arrays: {A} Novel {VLSI} Layout for
                 Systolic Computers",
  crossref =     "IEEE:1984:ASF",
  pages =        "37--45",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Ibarra:1984:DSA,
  author =       "O. H. Ibarra and M. A. Palis and S. M. Kim",
  title =        "Designing Systolic Algorithms Using Sequential
                 Machines",
  crossref =     "IEEE:1984:ASF",
  pages =        "46--55",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{MeyeraufderHeide:1984:LSP,
  author =       "F. {Meyer auf der Heide} and R. Reischuk",
  title =        "On the Limits to Speed Up Parallel Machines By Large
                 Hardware and Unbounded Communication",
  crossref =     "IEEE:1984:ASF",
  pages =        "56--64",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Cole:1984:RRE,
  author =       "R. Cole and A. Siegel",
  title =        "River Routing Every Which Way, But Loose",
  crossref =     "IEEE:1984:ASF",
  pages =        "65--73",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Heath:1984:EPG,
  author =       "L. Heath",
  title =        "Embedding Planar Graphs in Seven Pages",
  crossref =     "IEEE:1984:ASF",
  pages =        "74--83",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Papadimitriou:1984:CTT,
  author =       "C. H. Papadimitriou and J. D. Ullman",
  title =        "A Communication-Time Tradeoff",
  crossref =     "IEEE:1984:ASF",
  pages =        "84--88",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Aggarwal:1984:CSX,
  author =       "A. Aggarwal",
  title =        "A Comparative Study of {X}-Tree, Pyramid and Related
                 Machines",
  crossref =     "IEEE:1984:ASF",
  pages =        "89--99",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Gamal:1984:IDC,
  author =       "A. El Gamal and A. Orlitsky",
  title =        "Interactive Data Compression",
  crossref =     "IEEE:1984:ASF",
  pages =        "100--108",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Tiwari:1984:LBC,
  author =       "P. Tiwari",
  title =        "Lower Bounds on Communication Complexity in
                 Distributed Computer Networks",
  crossref =     "IEEE:1984:ASF",
  pages =        "109--117",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Paturi:1984:PCC,
  author =       "R. Paturi and J. Simon",
  title =        "Probabilistic Communication Complexity",
  crossref =     "IEEE:1984:ASF",
  pages =        "118--126",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Pippenger:1984:PCL,
  author =       "N. Pippenger",
  title =        "Parallel Communication With Limited Buffers",
  crossref =     "IEEE:1984:ASF",
  pages =        "127--136",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Itai:1984:MTA,
  author =       "A. Itai and M. Rodeh",
  title =        "The Multi-Tree Approach to Reliability in Distributed
                 Networks",
  crossref =     "IEEE:1984:ASF",
  pages =        "137--147",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Sullivan:1984:PTA,
  author =       "G. Sullivan",
  title =        "A Polynomial Time Algorithm for Fault Diagnosability",
  crossref =     "IEEE:1984:ASF",
  pages =        "148--156",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Broder:1984:FCM,
  author =       "A. Z. Broder and D. Dolev",
  title =        "Flipping Coins in Many Pockets ({Byzantine} Agreement
                 on Uniformly Random Values)",
  crossref =     "IEEE:1984:ASF",
  pages =        "157--170",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Upfal:1984:HSM,
  author =       "E. Upfal and A. Wigderson",
  title =        "How to Share Memory in a Distributed System",
  crossref =     "IEEE:1984:ASF",
  pages =        "171--180",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Bui:1984:GBA,
  author =       "Thang Bui and S. Chaudhuri and T. Leighton and M.
                 Sipser",
  title =        "Graph Bisection Algorithms With Good Average Case
                 Behavior",
  crossref =     "IEEE:1984:ASF",
  pages =        "181--192",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Shor:1984:ACA,
  author =       "P. W. Shor",
  title =        "The Average-Case Analysis of Some On-Line Algorithms
                 for Bin Packing",
  crossref =     "IEEE:1984:ASF",
  pages =        "193--200",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Komlos:1984:LVS,
  author =       "J. Komlos",
  title =        "Linear Verification for Spanning Trees",
  crossref =     "IEEE:1984:ASF",
  pages =        "201--206",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Mishra:1984:EAF,
  author =       "B. Mishra",
  title =        "An Efficient Algorithm to Find All `Bidirectional'
                 Edges of an Undirected Graph",
  crossref =     "IEEE:1984:ASF",
  pages =        "207--216",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Stallmann:1984:APA,
  author =       "M. Stallmann and H. N. Gabow",
  title =        "An Augmenting Path Algorithm for the Parity Problem on
                 Linear Matroids",
  crossref =     "IEEE:1984:ASF",
  pages =        "217--228",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Babai:1984:CMG,
  author =       "L. Babai and E. Szemeredi",
  title =        "On the Complexity of Matrix Group Problems {I}",
  crossref =     "IEEE:1984:ASF",
  pages =        "229--240",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kornhauser:1984:CPM,
  author =       "D. Kornhauser and G. Miller and P. Spirakis",
  title =        "Coordinating Pebble Motion on Graphs, the Diameter of
                 Permutation Groups, and Applications",
  crossref =     "IEEE:1984:ASF",
  pages =        "241--250",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kaminski:1984:MPR,
  author =       "M. Kaminski",
  title =        "Multiplication of Polynomials Over the Ring of
                 Integers",
  crossref =     "IEEE:1984:ASF",
  pages =        "251--254",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Cole:1984:SSN,
  author =       "R. Cole",
  title =        "Slowing Down Sorting Networks to Obtain Faster Sorting
                 Algorithm",
  crossref =     "IEEE:1984:ASF",
  pages =        "255--260",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Blum:1984:ERF,
  author =       "L. Blum and M. Shub",
  title =        "Evaluating Rational Functions: Infinite Precision Is
                 Finite Cost and Tractable on Average",
  crossref =     "IEEE:1984:ASF",
  pages =        "261--267",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Fagin:1984:MTA,
  author =       "R. Fagin and J. Y. Halpern and M. Y. Vardi",
  title =        "A Model-Theoretic Analysis of Knowledge: Preliminary
                 Report",
  crossref =     "IEEE:1984:ASF",
  pages =        "268--278",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Mulmuley:1984:SCF,
  author =       "K. Mulmuley",
  title =        "A Semantic Characterization of Full Abstraction for
                 Typed Lambda Calculi",
  crossref =     "IEEE:1984:ASF",
  pages =        "279--288",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Mitchell:1984:SMS,
  author =       "J. C. Mitchell",
  title =        "Semantic Models for Second-Order Lambda Calculus",
  crossref =     "IEEE:1984:ASF",
  pages =        "289--299",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Homer:1984:MDH,
  author =       "S. Homer",
  title =        "Minimal Degrees for Honest Polynomial Reducibilities",
  crossref =     "IEEE:1984:ASF",
  pages =        "300--307",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Balcazar:1984:SOU,
  author =       "J. Balcazar and R. Book and T. Long and U. Schoning
                 and A. Selman",
  title =        "Sparse Oracles and Uniform Complexity Classes",
  crossref =     "IEEE:1984:ASF",
  pages =        "308--311",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Hart:1984:NDS,
  author =       "S. Hart and M. Sharir",
  title =        "Nonlinearity of {Davenport--Schinzel} Sequences and of
                 a Generalized Path Compression Scheme",
  crossref =     "IEEE:1984:ASF",
  pages =        "313--319",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Alon:1984:EES,
  author =       "N. Alon and V. D. Milman",
  title =        "Eigenvalues, Expanders and Superconcentrators",
  crossref =     "IEEE:1984:ASF",
  pages =        "320--322",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Greenberg:1984:LBP,
  author =       "A. G. Greenberg and A. Weiss",
  title =        "A Lower Bound for Probabilistic Algorithms for Finite
                 State Machines",
  crossref =     "IEEE:1984:ASF",
  pages =        "323--331",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Moran:1984:ART,
  author =       "S. Moran and M. Snir and U. Manber",
  title =        "Applications of {Ramsey}'s Theorem to Decision Trees
                 Complexity",
  crossref =     "IEEE:1984:ASF",
  pages =        "332--337",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Fredman:1984:FHT,
  author =       "M. L. Fredman and R. E. Tarjan",
  title =        "{Fibonacci} Heaps and Their Uses in Improved Network
                 Optimization Algorithms",
  crossref =     "IEEE:1984:ASF",
  pages =        "338--346",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Gabow:1984:EIG,
  author =       "H. N. Gabow and Z. Galil and T. H. Spencer",
  title =        "Efficient Implementation of Graph Algorithms Using
                 Contraction",
  crossref =     "IEEE:1984:ASF",
  pages =        "347--357",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Chazelle:1984:CFT,
  author =       "B. Chazelle",
  title =        "Computing on a Free Tree Via Complexity-Preserving
                 Mappings",
  crossref =     "IEEE:1984:ASF",
  pages =        "358--368",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Munro:1984:IDS,
  author =       "J. I. Munro",
  title =        "An Implicit Data Structure for the Dictionary Problem
                 That Runs in Polylog Time",
  crossref =     "IEEE:1984:ASF",
  pages =        "369--374",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Fischer:1984:FPQ,
  author =       "M. J. Fischer and M. S. Paterson",
  title =        "{Fishspear}: {A} Priority Queue Algorithm",
  crossref =     "IEEE:1984:ASF",
  pages =        "375--386",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Dobkin:1984:SSI,
  author =       "D. P. Dobkin and H. Edelsbrunner",
  title =        "Space Searching for Intersecting Objects",
  crossref =     "IEEE:1984:ASF",
  pages =        "387--392",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Imai:1984:DSI,
  author =       "H. Imai and T. Asano",
  title =        "Dynamic Segment Intersection Search With
                 Applications",
  crossref =     "IEEE:1984:ASF",
  pages =        "393--402",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Vaidya:1984:FAA,
  author =       "P. M. Vaidya",
  title =        "A Fast Approximation Algorithm for Minimum Spanning
                 Trees in {$K$}-Dimensional Space",
  crossref =     "IEEE:1984:ASF",
  pages =        "403--407",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Chang:1984:PSP,
  author =       "J. S. Chang and C. K. Yap",
  title =        "A Polynomial Solution for Potato-Peeling and Other
                 Polygon Inclusion and Enclosure Problems",
  crossref =     "IEEE:1984:ASF",
  pages =        "408--416",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Sedgewick:1984:SPE,
  author =       "R. Sedgewick and J. S. Vitter",
  title =        "Shortest Paths in {Euclidean} Graphs",
  crossref =     "IEEE:1984:ASF",
  pages =        "417--424",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Blum:1984:IUC,
  author =       "M. Blum",
  title =        "Independent Unbiased Coin Flips From a Correlated
                 Biased Source: {A} Finite State {Markov} Chain",
  crossref =     "IEEE:1984:ASF",
  pages =        "425--433",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Santha:1984:GQR,
  author =       "M. Santha and U. V. Vazirani",
  title =        "Generating Quasi-Random Sequences From Slightly-Random
                 Sources",
  crossref =     "IEEE:1984:ASF",
  pages =        "434--440",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Goldwasser:1984:SSS,
  author =       "S. Goldwasser and S. Micali and R. L. Rivest",
  title =        "A ``Paradoxical'' Solution to the Signature Problem",
  crossref =     "IEEE:1984:ASF",
  pages =        "441--448",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Alexi:1984:RRB,
  author =       "W. Alexi and B. Chor and O. Goldreich and C. P.
                 Schnorr",
  title =        "{RSA\slash Rabin} Bits are {$1/2 + 1 \mbox{Poly} (\log
                 N)$} Secure",
  crossref =     "IEEE:1984:ASF",
  pages =        "449--457",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Vazirani:1984:ESP,
  author =       "U. V. Vazirani and V. V. Vazirani",
  title =        "Efficient and Secure Pseudo-Random Number Generation",
  crossref =     "IEEE:1984:ASF",
  pages =        "458--463",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Goldreich:1984:HCR,
  author =       "O. Goldreich and S. Goldwasser and S. Micali",
  title =        "How to Construct {Randolli} Functions",
  crossref =     "IEEE:1984:ASF",
  pages =        "464--479",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Frieze:1984:LCG,
  author =       "A. M. Frieze and R. Kannan and J. C. Lagarias",
  title =        "Linear Congruential Generators Do Not Produce Random
                 Sequences",
  crossref =     "IEEE:1984:ASF",
  pages =        "480--484",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Pitt:1984:CPI,
  author =       "L. Pitt",
  title =        "A Characterization of Probabilistic Inference",
  crossref =     "IEEE:1984:ASF",
  pages =        "485--494",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Grollmann:1984:CMP,
  author =       "J. Grollmann and A. L. Selman",
  title =        "Complexity Measures for Public-Key Cryptosystems",
  crossref =     "IEEE:1984:ASF",
  pages =        "495--503",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Friedman:1984:CSM,
  author =       "J. Friedman",
  title =        "Constructing {$O(n \log n)$} Size Monotone Formulae
                 for the $k$-th Elementary Symmetric Polynomial of $n$
                 {Boolean} Variables",
  crossref =     "IEEE:1984:ASF",
  pages =        "506--515",
  year =         "1984",
  bibdate =      "Thu Apr 5 06:13:39 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Stern:1987:SLC,
  author =       "J. Stern",
  title =        "Secret linear congruential generators are not
                 cryptographically secure",
  crossref =     "IEEE:1987:ASF",
  pages =        "421--426",
  year =         "1987",
  bibdate =      "Wed Dec 21 07:47:04 2011",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib;
                 http://www.math.utah.edu/pub/tex/bib/prng.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Nisan:1988:HVR,
  author =       "N. Nisan and A. Wigderson",
  title =        "Hardness vs. randomness",
  crossref =     "IEEE:1988:ASF",
  pages =        "2--11",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Goldreich:1988:EPG,
  author =       "O. Goldreich and H. Krawczyk and M. Luby",
  title =        "On the existence of pseudorandom generators",
  crossref =     "IEEE:1988:ASF",
  pages =        "12--24",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kilian:1988:ZKL,
  author =       "J. Kilian",
  title =        "Zero-knowledge with log-space verifiers",
  crossref =     "IEEE:1988:ASF",
  pages =        "25--35",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Levin:1988:HMP,
  author =       "L. A. Levin",
  title =        "Homogeneous measures and polynomial time invariants",
  crossref =     "IEEE:1988:ASF",
  pages =        "36--41",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Crepeau:1988:AOT,
  author =       "C. Crepeau and J. Kilian",
  title =        "Achieving oblivious transfer using weakened security
                 assumptions",
  crossref =     "IEEE:1988:ASF",
  pages =        "42--52",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Mansour:1988:LBI,
  author =       "Y. Mansour and B. Schieber and P. Tiwari",
  title =        "Lower bounds for integer greatest common divisor
                 computations",
  crossref =     "IEEE:1988:ASF",
  pages =        "54--63",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Bshouty:1988:LBM,
  author =       "N. H. Bshouty",
  title =        "A lower bound for matrix multiplication",
  crossref =     "IEEE:1988:ASF",
  pages =        "64--67",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kahn:1988:IVB,
  author =       "J. Kahn and G. Kalai and N. Linial",
  title =        "The influence of variables on {Boolean} functions",
  crossref =     "IEEE:1988:ASF",
  pages =        "68--80",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Lovasz:1988:LMF,
  author =       "L. Lovasz and M. Saks",
  title =        "Lattices, {M{\"o}bius} functions and communications
                 complexity",
  crossref =     "IEEE:1988:ASF",
  pages =        "81--90",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Yao:1988:NOT,
  author =       "A. C.-C. Yao",
  title =        "Near-optimal time-space tradeoff for element
                 distinctness",
  crossref =     "IEEE:1988:ASF",
  pages =        "91--97",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Haussler:1988:PFR,
  author =       "D. Haussler and N. Littlestone and M. K. Warmuth",
  title =        "Predicting $(0, 1)$-functions on randomly drawn
                 points",
  crossref =     "IEEE:1988:ASF",
  pages =        "100--109",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{DeSantis:1988:LPP,
  author =       "A. DeSantis and G. Markowsky and M. N. Wegman",
  title =        "Learning probabilistic prediction functions",
  crossref =     "IEEE:1988:ASF",
  pages =        "110--119",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Linial:1988:RLV,
  author =       "N. Linial and Y. Mansour and R. L. Rivest",
  title =        "Results on learnability and the {Vapnik--Chervonenkis}
                 dimension",
  crossref =     "IEEE:1988:ASF",
  pages =        "120--129",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Gasarch:1988:LQ,
  author =       "W. I. Gasarch",
  title =        "Learning via queries",
  crossref =     "IEEE:1988:ASF",
  pages =        "130--137",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Komlos:1988:ECA,
  author =       "J. Komlos and R. Paturi",
  title =        "Effect of connectivity in associative memory models",
  crossref =     "IEEE:1988:ASF",
  pages =        "138--147",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Klein:1988:EPA,
  author =       "P. N. Klein",
  title =        "Efficient parallel algorithms for chordal graphs",
  crossref =     "IEEE:1988:ASF",
  pages =        "150--161",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Luby:1988:RRP,
  author =       "M. Luby",
  title =        "Removing randomness in parallel computation without a
                 processor penalty",
  crossref =     "IEEE:1988:ASF",
  pages =        "162--173",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Goldberg:1988:STP,
  author =       "A. V. Goldberg and S. A. Plotkin and P. M. Vaidya",
  title =        "Sublinear-time parallel algorithms for matching and
                 related problems",
  crossref =     "IEEE:1988:ASF",
  pages =        "174--185",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Dahlhaus:1988:OPA,
  author =       "E. Dahlhaus and P. Hajnal and M. Karpinski",
  title =        "Optimal parallel algorithm for the {Hamiltonian} cycle
                 problem on dense graphs",
  crossref =     "IEEE:1988:ASF",
  pages =        "186--193",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Alon:1988:PCA,
  author =       "N. Alon and Y. Azar",
  title =        "Parallel comparison algorithms for approximation
                 problems",
  crossref =     "IEEE:1988:ASF",
  pages =        "194--203",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Awerbuch:1988:DNF,
  author =       "B. Awerbuch and M. Sipser",
  title =        "Dynamic networks are as fast as static networks",
  crossref =     "IEEE:1988:ASF",
  pages =        "206--219",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kock:1988:ISN,
  author =       "R. R. Kock",
  title =        "Increasing the size of a network by a constant factor
                 can increase performance by more than a constant
                 factor",
  crossref =     "IEEE:1988:ASF",
  pages =        "221--230",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Awerbuch:1988:EFD,
  author =       "B. Awerbuch",
  title =        "On the effects of feedback in dynamic network
                 protocols",
  crossref =     "IEEE:1988:ASF",
  pages =        "231--245",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Moses:1988:CTR,
  author =       "Y. Moses and O. Waarts",
  title =        "Coordinated traversal: $(t+1)$-round {Byzantine}
                 agreement in polynomial time",
  crossref =     "IEEE:1988:ASF",
  pages =        "246--255",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Leighton:1988:UPR,
  author =       "T. Leighton and B. Maggs and S. Rao",
  title =        "Universal packet routing algorithms",
  crossref =     "IEEE:1988:ASF",
  pages =        "256--269",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Babai:1988:FMP,
  author =       "L. Babai and E. M. Luks and A. Seress",
  title =        "Fast management of permutation groups",
  crossref =     "IEEE:1988:ASF",
  pages =        "272--282",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Shoup:1988:NAF,
  author =       "V. Shoup",
  title =        "New algorithms for finding irreducible polynomials
                 over finite fields",
  crossref =     "IEEE:1988:ASF",
  pages =        "283--290",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Renegar:1988:FPA,
  author =       "J. Renegar",
  title =        "A faster {PSPACE} algorithm for deciding the
                 existential theory of the reals",
  crossref =     "IEEE:1988:ASF",
  pages =        "291--295",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kaltofen:1988:CPG,
  author =       "E. Kaltofen and B. Trager",
  title =        "Computing with polynomials given by black boxes for
                 their evaluations: greatest common divisors,
                 factorization, separation of numerators and
                 denominators",
  crossref =     "IEEE:1988:ASF",
  pages =        "296--305",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Canny:1988:CKP,
  author =       "J. Canny and J. Reif and B. Donald and P. Xavier",
  title =        "On the complexity of kinodynamic planning",
  crossref =     "IEEE:1988:ASF",
  pages =        "306--316",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Safra:1988:CA,
  author =       "S. Safra",
  title =        "On the complexity of $\omega$-automata",
  crossref =     "IEEE:1988:ASF",
  pages =        "319--327",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Emerson:1988:CTA,
  author =       "E. A. Emerson and C. S. Jutla",
  title =        "The complexity of tree automata and logics of
                 programs",
  crossref =     "IEEE:1988:ASF",
  pages =        "328--337",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Courcoubetis:1988:VTP,
  author =       "C. Courcoubetis and M. Yannakakis",
  title =        "Verifying temporal properties of finite-state
                 probabilistic programs",
  crossref =     "IEEE:1988:ASF",
  pages =        "338--345",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Ajtai:1988:CPP,
  author =       "M. Ajtai",
  title =        "The complexity of the pigeonhole principle",
  crossref =     "IEEE:1988:ASF",
  pages =        "346--355",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Ajtai:1988:RHD,
  author =       "M. Ajtai and R. Fagin",
  title =        "Reachability is harder for directed than for
                 undirected finite graphs",
  crossref =     "IEEE:1988:ASF",
  pages =        "358--367",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Ong:1988:FAM,
  author =       "C.-H. L. Ong",
  title =        "Fully abstract models of the lazy lambda calculus",
  crossref =     "IEEE:1988:ASF",
  pages =        "368--376",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{McAllester:1988:NFS,
  author =       "D. McAllester and P. Panangaden and V. Shanbhogue",
  title =        "Nonexpressibility of fairness and signaling",
  crossref =     "IEEE:1988:ASF",
  pages =        "377--386",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Blum:1988:TCR,
  author =       "L. Blum and M. Shub and S. Smale",
  title =        "On a theory of computation over the real numbers; {NP}
                 completeness, recursive functions and universal
                 machines",
  crossref =     "IEEE:1988:ASF",
  pages =        "387--397",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Motwani:1988:CRG,
  author =       "R. Motwani and A. Raghunathan and H. Saran",
  title =        "Constructive results from graph minors: linkless
                 embeddings",
  crossref =     "IEEE:1988:ASF",
  pages =        "398--409",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Dagum:1988:PPG,
  author =       "P. Dagum and M. Luby and M. Mihail and U. Vazirani",
  title =        "Polytopes, permanents and graphs with large factors",
  crossref =     "IEEE:1988:ASF",
  pages =        "412--421",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Leighton:1988:AMF,
  author =       "T. Leighton and S. Rao",
  title =        "An approximate max-flow min-cut theorem for uniform
                 multicommodity flow problems with applications to
                 approximation algorithms",
  crossref =     "IEEE:1988:ASF",
  pages =        "422--431",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Goldberg:1988:CAG,
  author =       "A. V. Goldberg and S. A. Plotkin and E. Tardos",
  title =        "Combinatorial algorithms for the generalized
                 circulation problem",
  crossref =     "IEEE:1988:ASF",
  pages =        "432--443",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Goldschmidt:1988:PAK,
  author =       "O. Goldschmidt and D. S. Hochbaum",
  title =        "Polynomial algorithm for the $k$-cut problem",
  crossref =     "IEEE:1988:ASF",
  pages =        "444--451",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Clarkson:1988:VAL,
  author =       "K. L. Clarkson",
  title =        "A {Las Vegas} algorithm for linear programming when
                 the dimension is small",
  crossref =     "IEEE:1988:ASF",
  pages =        "452--456",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Malitz:1988:GGP,
  author =       "S. M. Malitz",
  title =        "Genus $g$ graphs have pagenumber {$O(\sqrt{g})$}",
  crossref =     "IEEE:1988:ASF",
  pages =        "458--468",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Bhatt:1988:TWG,
  author =       "S. Bhatt and Jin-Yi Cai",
  title =        "Take a walk, grow a tree",
  crossref =     "IEEE:1988:ASF",
  pages =        "469--478",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Broder:1988:BCT,
  author =       "A. Z. Broder and A. R. Karlin",
  title =        "Bounds on the cover time",
  crossref =     "IEEE:1988:ASF",
  pages =        "479--487",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Eppstein:1988:SDP,
  author =       "D. Eppstein and Z. Galil and R. Giancarlo",
  title =        "Speeding up dynamic programming",
  crossref =     "IEEE:1988:ASF",
  pages =        "488--496",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Aggarwal:1988:NSM,
  author =       "A. Aggarwal and J. Park",
  title =        "Notes on searching in multidimensional monotone
                 arrays",
  crossref =     "IEEE:1988:ASF",
  pages =        "497--512",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Fredman:1988:TS,
  author =       "M. L. Fredman and D. L. Goldsmith",
  title =        "Three stacks",
  crossref =     "IEEE:1988:ASF",
  pages =        "514--523",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Dietzfelbinger:1988:DPH,
  author =       "M. Dietzfelbinger and A. Karlin and K. Mehlhorn and F.
                 M. auf der Heide and H. Rohnert and R. E. Tarjan",
  title =        "Dynamic perfect hashing: upper and lower bounds",
  crossref =     "IEEE:1988:ASF",
  pages =        "524--531",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Ben-Amram:1988:PVA,
  author =       "A. M. Ben-Amram and Z. Galil",
  title =        "On pointers versus addresses",
  crossref =     "IEEE:1988:ASF",
  pages =        "532--538",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Chazelle:1988:DVR,
  author =       "B. Chazelle and J. Friedman",
  title =        "A deterministic view of random sampling and its use in
                 geometry",
  crossref =     "IEEE:1988:ASF",
  pages =        "539--549",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Overmars:1988:NUB,
  author =       "M. H. Overmars and Chee-Keng Yap",
  title =        "New upper bounds in {Klee}'s measure problem",
  crossref =     "IEEE:1988:ASF",
  pages =        "550--556",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Preparata:1988:FDT,
  author =       "F. P. Preparata and R. Tamassia",
  title =        "Fully dynamic techniques for point location and
                 transitive closure in planar structures",
  crossref =     "IEEE:1988:ASF",
  pages =        "558--567",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Clarkson:1988:CCB,
  author =       "K. L. Clarkson and H. Edelsbrunner and L. J. Guibas
                 and M. Sharir and E. Welzl",
  title =        "Combinatorial complexity bounds for arrangements of
                 curves and surfaces",
  crossref =     "IEEE:1988:ASF",
  pages =        "568--579",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Mulmuley:1988:FPP,
  author =       "K. Mulmuley",
  title =        "A fast planar partition algorithm. {I}",
  crossref =     "IEEE:1988:ASF",
  pages =        "580--589",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Chazelle:1988:OAI,
  author =       "B. Chazelle and H. Edelsbrunner",
  title =        "An optimal algorithm for intersecting line segments in
                 the plane",
  crossref =     "IEEE:1988:ASF",
  pages =        "590--600",
  year =         "1988",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Berger:1989:SWI,
  author =       "B. Berger and J. Rompel",
  title =        "Simulating ($\log^c n$)-wise independence in {NC}",
  crossref =     "IEEE:1989:ASF",
  pages =        "2--7",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Motwani:1989:PMY,
  author =       "R. Motwani and J. Naor and M. Naor",
  title =        "The probabilistic method yields deterministic parallel
                 algorithms",
  crossref =     "IEEE:1989:ASF",
  pages =        "8--13",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Cohen:1989:DDA,
  author =       "A. Cohen and A. Wigderson",
  title =        "Dispersers, deterministic amplification, and weak
                 random sources",
  crossref =     "IEEE:1989:ASF",
  pages =        "14--19",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Siegel:1989:UCF,
  author =       "A. Siegel",
  title =        "On universal classes of fast high performance hash
                 functions, their time-space tradeoff, and their
                 applications",
  crossref =     "IEEE:1989:ASF",
  pages =        "20--25",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Schapire:1989:SWL,
  author =       "R. E. Schapire",
  title =        "The strength of weak learnability",
  crossref =     "IEEE:1989:ASF",
  pages =        "28--33",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Li:1989:TLS,
  author =       "M. Li and P. M. B. Vitanyi",
  title =        "A theory of learning simple concepts under simple
                 distributions and average case complexity for the
                 universal distribution",
  crossref =     "IEEE:1989:ASF",
  pages =        "34--39",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Haussler:1989:GPM,
  author =       "D. Haussler",
  title =        "Generalizing the {PAC} model: sample size bounds from
                 metric dimension-based uniform convergence results",
  crossref =     "IEEE:1989:ASF",
  pages =        "40--45",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Goldman:1989:LBR,
  author =       "S. A. Goldman and R. L. Rivest and R. E. Schapire",
  title =        "Learning binary relations and total orders",
  crossref =     "IEEE:1989:ASF",
  pages =        "46--51",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Berger:1989:ENA,
  author =       "B. Berger and J. Rompel and P. W. Shor",
  title =        "Efficient {NC} algorithms for set cover with
                 applications to learning and geometry",
  crossref =     "IEEE:1989:ASF",
  pages =        "54--59",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Marcotte:1989:FMA,
  author =       "O. Marcotte and S. Suri",
  title =        "Fast matching algorithms for points on a polygon",
  crossref =     "IEEE:1989:ASF",
  pages =        "60--65",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Frederickson:1989:EMP,
  author =       "G. N. Frederickson and D. J. Guan",
  title =        "Ensemble motion planning in trees",
  crossref =     "IEEE:1989:ASF",
  pages =        "66--71",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Pach:1989:UBN,
  author =       "J. Pach and W. Steiger and E. Szemeredi",
  title =        "An upper bound on the number of planar $k$-sets",
  crossref =     "IEEE:1989:ASF",
  pages =        "72--79",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Dickerson:1989:IAP,
  author =       "M. Dickerson",
  title =        "The inverse of an automorphism in polynomial time",
  crossref =     "IEEE:1989:ASF",
  pages =        "82--87",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{vonzurGathen:1989:TPP,
  author =       "J. von zur Gathen",
  title =        "Testing permutation polynomials",
  crossref =     "IEEE:1989:ASF",
  pages =        "88--92",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Babai:1989:CIR,
  author =       "L. Babai and L. Ronyai",
  title =        "Computing irreducible representations of finite
                 groups",
  crossref =     "IEEE:1989:ASF",
  pages =        "93--98",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Ronyai:1989:GGF,
  author =       "L. Ronyai",
  title =        "{Galois} groups and factoring polynomials over finite
                 fields",
  crossref =     "IEEE:1989:ASF",
  pages =        "99--104",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Gabow:1989:EAI,
  author =       "H. N. Gabow and Y. Xu",
  title =        "Efficient algorithms for independent assignment on
                 graphic and linear matroids",
  crossref =     "IEEE:1989:ASF",
  pages =        "106--111",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Miller:1989:FPG,
  author =       "G. L. Miller and J. Naor",
  title =        "Flow in planar graphs with multiple sources and
                 sinks",
  crossref =     "IEEE:1989:ASF",
  pages =        "112--117",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Cheriyan:1989:RMF,
  author =       "J. Cheriyan and T. Hagerup",
  title =        "A randomized maximum-flow algorithm",
  crossref =     "IEEE:1989:ASF",
  pages =        "118--123",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Linial:1989:GPC,
  author =       "N. Linial and U. Vazirani",
  title =        "Graph products and chromatic numbers",
  crossref =     "IEEE:1989:ASF",
  pages =        "124--128",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Ng:1989:LBS,
  author =       "C. Ng",
  title =        "Lower bounds for the stable marriage problem and its
                 variants",
  crossref =     "IEEE:1989:ASF",
  pages =        "129--133",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Hall:1989:ASC,
  author =       "L. A. Hall and D. B. Shmoys",
  title =        "Approximation schemes for constrained scheduling
                 problems",
  crossref =     "IEEE:1989:ASF",
  pages =        "134--139",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Ajtai:1989:DVF,
  author =       "M. Ajtai and Y. Gurevich",
  title =        "Datalog vs. first-order logic",
  crossref =     "IEEE:1989:ASF",
  pages =        "142--147",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Abadi:1989:DEF,
  author =       "M. Abadi and J. Y. Halpern",
  title =        "Decidability and expressiveness for first-order logics
                 of probability",
  crossref =     "IEEE:1989:ASF",
  pages =        "148--153",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Cook:1989:CBF,
  author =       "S. A. Cook and B. M. Kapron",
  title =        "Characterizations of the basic feasible functionals of
                 finite type",
  crossref =     "IEEE:1989:ASF",
  pages =        "154--159",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Pacholski:1989:LFC,
  author =       "L. Pacholski and W. Szwast",
  title =        "The $0$--$1$ law fails for the class of existential
                 second order {G{\"o}del} sentences with equality",
  crossref =     "IEEE:1989:ASF",
  pages =        "160--163",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Alur:1989:RTL,
  author =       "R. Alur and T. A. Henzinger",
  title =        "A really temporal logic",
  crossref =     "IEEE:1989:ASF",
  pages =        "164--169",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Russell:1989:FAN,
  author =       "J. R. Russell",
  title =        "Full abstraction for nondeterministic dataflow
                 networks",
  crossref =     "IEEE:1989:ASF",
  pages =        "170--175",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kosaraju:1989:ETP,
  author =       "S. R. Kosaraju",
  title =        "Efficient tree pattern matching",
  crossref =     "IEEE:1989:ASF",
  pages =        "178--183",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kosaraju:1989:PCT,
  author =       "S. R. Kosaraju",
  title =        "Pipelining computations in a tree of processors",
  crossref =     "IEEE:1989:ASF",
  pages =        "184--189",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Goodrich:1989:SPP,
  author =       "M. T. Goodrich and S. R. Kosaraju",
  title =        "Sorting on a parallel pointer machine with
                 applications to set expression evaluation",
  crossref =     "IEEE:1989:ASF",
  pages =        "190--195",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Berkman:1989:RTP,
  author =       "O. Berkman and U. Vishkin",
  title =        "Recursive *-tree parallel data-structure",
  crossref =     "IEEE:1989:ASF",
  pages =        "196--202",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Ko:1989:CCR,
  author =       "K.-I. Ko",
  title =        "Computational complexity of roots of real functions",
  crossref =     "IEEE:1989:ASF",
  pages =        "204--209",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Abrahamson:1989:CFP,
  author =       "K. R. Abrahamson and M. R. Fellows and J. A. Ellis and
                 M. E. Mata",
  title =        "On the complexity of fixed parameter problems",
  crossref =     "IEEE:1989:ASF",
  pages =        "210--215",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Krentel:1989:SLO,
  author =       "M. W. Krentel",
  title =        "Structure in locally optimal solutions",
  crossref =     "IEEE:1989:ASF",
  pages =        "216--221",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Impagliazzo:1989:DVS,
  author =       "R. Impagliazzo and G. Tardos",
  title =        "Decision versus search problems in super-polynomial
                 time",
  crossref =     "IEEE:1989:ASF",
  pages =        "222--227",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Impagliazzo:1989:OWF,
  author =       "R. Impagliazzo and M. Luby",
  title =        "One-way functions are essential for complexity based
                 cryptography",
  crossref =     "IEEE:1989:ASF",
  pages =        "230--235",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Impagliazzo:1989:ECS,
  author =       "R. Impagliazzo and M. Naor",
  title =        "Efficient cryptographic schemes provably as secure as
                 subset sum",
  crossref =     "IEEE:1989:ASF",
  pages =        "236--241",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kharitonov:1989:LBP,
  author =       "M. Kharitonov and A. V. Goldberg and M. Yung",
  title =        "Lower bounds for pseudorandom number generators",
  crossref =     "IEEE:1989:ASF",
  pages =        "242--247",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Impagliazzo:1989:HRR,
  author =       "R. Impagliazzo and D. Zuckerman",
  title =        "How to recycle random bits",
  crossref =     "IEEE:1989:ASF",
  pages =        "248--253",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Littlestone:1989:WMA,
  author =       "N. Littlestone and M. K. Warmuth",
  title =        "The weighted majority algorithm",
  crossref =     "IEEE:1989:ASF",
  pages =        "256--261",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Maass:1989:CLC,
  author =       "W. Maass and G. Turan",
  title =        "On the complexity of learning from counterexamples",
  crossref =     "IEEE:1989:ASF",
  pages =        "262--267",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Tseng:1989:ELP,
  author =       "W.-G. Tseng",
  title =        "The equivalence and learning of probabilistic
                 automata",
  crossref =     "IEEE:1989:ASF",
  pages =        "268--273",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Fiat:1989:PLP,
  author =       "A. Fiat and S. Moses and A. Shamir and I. Shimshoni
                 and G. Tardos",
  title =        "Planning and learning in permutation groups",
  crossref =     "IEEE:1989:ASF",
  pages =        "274--279",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Ramachandran:1989:OPA,
  author =       "V. Ramachandran and J. Reif",
  title =        "An optimal parallel algorithm for graph planarity",
  crossref =     "IEEE:1989:ASF",
  pages =        "282--287",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Khuller:1989:EPA,
  author =       "S. Khuller and B. Schieber",
  title =        "Efficient parallel algorithms for testing connectivity
                 and finding disjoint $s$--$t$ paths in graphs",
  crossref =     "IEEE:1989:ASF",
  pages =        "288--293",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kirousis:1989:PCS,
  author =       "L. Kirousis and M. Serna and P. Spirakis",
  title =        "The parallel complexity of the subgraph connectivity
                 problem",
  crossref =     "IEEE:1989:ASF",
  pages =        "294--299",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Khuller:1989:PEP,
  author =       "S. Khuller and S. G. Mitchell and V. V. Vazirani",
  title =        "Processor efficient parallel algorithms for the two
                 disjoint paths problem, and for finding a {Kuratowski}
                 homeomorph",
  crossref =     "IEEE:1989:ASF",
  pages =        "300--305",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Yao:1989:LBA,
  author =       "A. C.-C. Yao",
  title =        "Lower bounds for algebraic computation trees with
                 integer inputs",
  crossref =     "IEEE:1989:ASF",
  pages =        "308--313",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Landau:1989:SNR,
  author =       "S. Landau",
  title =        "Simplification of nested radicals",
  crossref =     "IEEE:1989:ASF",
  pages =        "314--319",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Just:1989:GCF,
  author =       "B. Just",
  title =        "Generalizing the continued fraction algorithm to
                 arbitrary dimensions",
  crossref =     "IEEE:1989:ASF",
  pages =        "320--324",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Mansour:1989:CAS,
  author =       "Y. Mansour and B. Schieber and P. Tiwari",
  title =        "The complexity of approximating the square root",
  crossref =     "IEEE:1989:ASF",
  pages =        "325--330",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Vaidya:1989:SLP,
  author =       "P. M. Vaidya",
  title =        "Speeding-up linear programming using fast matrix
                 multiplication",
  crossref =     "IEEE:1989:ASF",
  pages =        "332--337",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Vaidya:1989:NAM,
  author =       "P. M. Vaidya",
  title =        "A new algorithm for minimizing convex functions over
                 convex sets",
  crossref =     "IEEE:1989:ASF",
  pages =        "338--343",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Driscoll:1989:AFA,
  author =       "J. R. Driscoll and D. M. {Healy, Jr.}",
  title =        "Asymptotically fast algorithms for spherical and
                 related transforms",
  crossref =     "IEEE:1989:ASF",
  pages =        "344--349",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Goldberg:1989:IPM,
  author =       "A. V. Goldberg and D. B. Shmoys and S. A. Plotkin and
                 E. Tardos",
  title =        "Interior-point methods in parallel computation",
  crossref =     "IEEE:1989:ASF",
  pages =        "350--355",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Awerbuch:1989:PEE,
  author =       "B. Awerbuch and Y. Mansour and N. Shavit",
  title =        "Polynomial end-to-end communication",
  crossref =     "IEEE:1989:ASF",
  pages =        "358--363",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Awerbuch:1989:NDL,
  author =       "B. Awerbuch and M. Luby and A. V. Goldberg and S. A.
                 Plotkin",
  title =        "Network decomposition and locality in distributed
                 computation",
  crossref =     "IEEE:1989:ASF",
  pages =        "364--369",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Afek:1989:ULB,
  author =       "Y. Afek and E. Gafni and M. Ricklin",
  title =        "Upper and lower bounds for routing schemes in dynamic
                 networks",
  crossref =     "IEEE:1989:ASF",
  pages =        "370--375",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Jiang:1989:SNN,
  author =       "T. Jiang",
  title =        "The synchronization of nonuniform networks of finite
                 automata",
  crossref =     "IEEE:1989:ASF",
  pages =        "376--381",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Leighton:1989:EMP,
  author =       "T. Leighton and B. Maggs",
  title =        "Expanders might be practical: fast algorithms for
                 routing around faults on multibutterflies",
  crossref =     "IEEE:1989:ASF",
  pages =        "384--389",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Herley:1989:ESS,
  author =       "K. T. Herley",
  title =        "Efficient simulations of small shared memories on
                 bounded degree networks",
  crossref =     "IEEE:1989:ASF",
  pages =        "390--395",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Plaxton:1989:NCS,
  author =       "C. G. Plaxton",
  title =        "On the network complexity of selection",
  crossref =     "IEEE:1989:ASF",
  pages =        "396--401",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Itkis:1989:PFV,
  author =       "G. Itkis and L. A. Levin",
  title =        "Power of fast {VLSI} models is insensitive to wires'
                 thinness",
  crossref =     "IEEE:1989:ASF",
  pages =        "402--407",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Berman:1989:TOD,
  author =       "P. Berman and J. A. Garay and K. J. Perry",
  title =        "Towards optimal distributed consensus",
  crossref =     "IEEE:1989:ASF",
  pages =        "410--415",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kushilevitz:1989:PCC,
  author =       "E. Kushilevitz",
  title =        "Privacy and communication complexity",
  crossref =     "IEEE:1989:ASF",
  pages =        "416--421",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Chor:1989:SAE,
  author =       "B. Chor and L. Moscovici",
  title =        "Solvability in asynchronous environments",
  crossref =     "IEEE:1989:ASF",
  pages =        "422--427",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Dolev:1989:MCC,
  author =       "D. Dolev and T. Feder",
  title =        "Multiparty communication complexity",
  crossref =     "IEEE:1989:ASF",
  pages =        "428--433",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Battista:1989:IPT,
  author =       "G. Di Battista and R. Tamassia",
  title =        "Incremental planarity testing",
  crossref =     "IEEE:1989:ASF",
  pages =        "436--441",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Broder:1989:GRS,
  author =       "A. Broder",
  title =        "Generating random spanning trees",
  crossref =     "IEEE:1989:ASF",
  pages =        "442--447",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Frederickson:1989:UCG,
  author =       "G. N. Frederickson",
  title =        "Using cellular graph embeddings in solving all pairs
                 shortest paths problems",
  crossref =     "IEEE:1989:ASF",
  pages =        "448--453",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Dahlhaus:1989:EPA,
  author =       "E. Dahlhaus and M. Karpinski",
  title =        "An efficient parallel algorithm for the minimal
                 elimination ordering ({MEO}) of an arbitrary graph",
  crossref =     "IEEE:1989:ASF",
  pages =        "454--459",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Condon:1989:CSB,
  author =       "A. Condon and R. J. Lipton",
  title =        "On the complexity of space bounded interactive
                 proofs",
  crossref =     "IEEE:1989:ASF",
  pages =        "462--467",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Beaver:1989:MCF,
  author =       "D. Beaver and S. Goldwasser",
  title =        "Multiparty computation with faulty majority",
  crossref =     "IEEE:1989:ASF",
  pages =        "468--473",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kilian:1989:MRZ,
  author =       "J. Kilian and S. Micali and R. Ostrovsky",
  title =        "Minimum resource zero knowledge proofs",
  crossref =     "IEEE:1989:ASF",
  pages =        "474--479",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Dwork:1989:PWP,
  author =       "C. Dwork and L. Stockmeyer",
  title =        "On the power of $2$-way probabilistic finite state
                 automata",
  crossref =     "IEEE:1989:ASF",
  pages =        "480--485",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Dobkin:1989:DCM,
  author =       "D. Dobkin and S. Suri",
  title =        "Dynamically computing the maxima of decomposable
                 functions, with applications",
  crossref =     "IEEE:1989:ASF",
  pages =        "488--493",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Fortune:1989:SMP,
  author =       "S. Fortune",
  title =        "Stable maintenance of point set triangulations in two
                 dimensions",
  crossref =     "IEEE:1989:ASF",
  pages =        "494--499",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Milenkovic:1989:DPG,
  author =       "V. Milenkovic",
  title =        "Double precision geometry: a general technique for
                 calculating line and segment intersections using
                 rounded arithmetic",
  crossref =     "IEEE:1989:ASF",
  pages =        "500--505",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Kuchem:1989:AOT,
  author =       "R. Kuchem and D. Wagner and F. Wagner",
  title =        "Area-optimal three-layer channel routing",
  crossref =     "IEEE:1989:ASF",
  pages =        "506--511",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Toda:1989:CPP,
  author =       "S. Toda",
  title =        "On the computational power of {PP} and (+){P}",
  crossref =     "IEEE:1989:ASF",
  pages =        "514--519",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Fellows:1989:AMN,
  author =       "M. R. Fellows and M. A. Langston",
  title =        "An analogue of the {Myhill-Nerode} theorem and its use
                 in computing finite-basis characterizations",
  crossref =     "IEEE:1989:ASF",
  pages =        "520--525",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Mihail:1989:CCM,
  author =       "M. Mihail",
  title =        "Conductance and convergence of {Markov} chains --- a
                 combinatorial treatment of expanders",
  crossref =     "IEEE:1989:ASF",
  pages =        "526--531",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Cai:1989:LBC,
  author =       "J.-Y. Cai",
  title =        "Lower bounds for constant depth circuits in the
                 presence of help bits",
  crossref =     "IEEE:1989:ASF",
  pages =        "532--537",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Aragon:1989:RST,
  author =       "C. R. Aragon and R. G. Seidel",
  title =        "Randomized search trees",
  crossref =     "IEEE:1989:ASF",
  pages =        "540--545",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Mehlhorn:1989:CGR,
  author =       "K. Mehlhorn and S. Naher and M. Rauch",
  title =        "On the complexity of a game related to the dictionary
                 problem",
  crossref =     "IEEE:1989:ASF",
  pages =        "546--548",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Jacobson:1989:SES,
  author =       "G. Jacobson",
  title =        "Space-efficient static trees and graphs",
  crossref =     "IEEE:1989:ASF",
  pages =        "549--554",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Sundar:1989:TTC,
  author =       "R. Sundar",
  title =        "Twists, turns, cascades, deque conjecture, and
                 scanning theorem",
  crossref =     "IEEE:1989:ASF",
  pages =        "555--559",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Raz:1989:PCC,
  author =       "R. Raz and A. Wigderson",
  title =        "Probabilistic communication complexity of {Boolean}
                 relations",
  crossref =     "IEEE:1989:ASF",
  pages =        "562--567",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Cai:1989:SSC,
  author =       "J.-Y. Cai and R. J. Lipton",
  title =        "Subquadratic simulations of circuits by branching
                 programs",
  crossref =     "IEEE:1989:ASF",
  pages =        "568--573",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Linial:1989:CDC,
  author =       "N. Linial and Y. Mansour and N. Nisan",
  title =        "Constant depth circuits, {Fourier} transform, and
                 learnability",
  crossref =     "IEEE:1989:ASF",
  pages =        "574--579",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Allender:1989:NPT,
  author =       "E. Allender",
  title =        "A note on the power of threshold circuits",
  crossref =     "IEEE:1989:ASF",
  pages =        "580--584",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Chazelle:1989:OAI,
  author =       "B. Chazelle",
  title =        "An optimal algorithm for intersecting
                 three-dimensional convex polyhedra",
  crossref =     "IEEE:1989:ASF",
  pages =        "586--591",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Mulmuley:1989:ORF,
  author =       "K. Mulmuley",
  title =        "On obstructions in relation to a fixed viewpoint",
  crossref =     "IEEE:1989:ASF",
  pages =        "592--597",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Overmars:1989:OSH,
  author =       "M. Overmars and M. Sharir",
  title =        "Output-sensitive hidden surface removal",
  crossref =     "IEEE:1989:ASF",
  pages =        "598--603",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Hansen:1989:AAG,
  author =       "M. D. Hansen",
  title =        "Approximation algorithms for geometric embeddings in
                 the plane with applications to parallel processing
                 problems",
  crossref =     "IEEE:1989:ASF",
  pages =        "604--609",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Cai:1989:OLB,
  author =       "J.-Y. Cai and M. Furer and N. Immerman",
  title =        "An optimal lower bound on the number of variables for
                 graph identification",
  crossref =     "IEEE:1989:ASF",
  pages =        "612--617",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

@InProceedings{Liskiewicz:1989:RCA,
  author =       "M. Liskiewicz and K. Lorys",
  title =        "On reversal complexity for alternating {Turing}
                 machines",
  crossref =     "IEEE:1989:ASF",
  pages =        "618--623",
  year =         "1989",
  bibdate =      "Thu Apr 5 06:13:40 MDT 2001",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  acknowledgement = ack-nhfb,
}

%%% ====================================================================
%%% Cross-referenced entries must come last:
@Proceedings{IEEE:1980:ASF,
  editor =       "{IEEE}",
  booktitle =    "21st annual Symposium on Foundations of Computer
                 Science: October 13--15, 1980, Syracuse, New York",
  title =        "21st annual Symposium on Foundations of Computer
                 Science: October 13--15, 1980, Syracuse, New York",
  publisher =    pub-IEEE,
  address =      pub-IEEE:adr,
  pages =        "vi + 421",
  year =         "1980",
  CODEN =        "ASFPDV",
  ISBN =         "????",
  ISBN-13 =      "????",
  ISSN =         "0272-5428",
  LCCN =         "QA76.6 .S95 1980; TK7885.A1 S92 1980",
  bibdate =      "Thu Dec 3 07:11:18 MST 1998",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  note =         "Formerly called the Annual Symposium on Switching and
                 Automata Theory. IEEE catalog no. 80CH1498-5.",
  acknowledgement = ack-nhfb,
  keywords =     "electronic data processing --- congresses; electronic
                 digital computers --- programming --- congresses;
                 algorithms --- congresses; electronic data processing
                 --- congresses; electronic digital computers ---
                 programming --- congresses; machine theory ---
                 congresses; switching theory --- congresses; automata
                 --- congresses",
}

@Proceedings{IEEE:1981:ASF,
  editor =       "{IEEE}",
  booktitle =    "22nd Annual Symposium on Foundations of Computer
                 Science: October 28--30, 1981, [Nashville, Tennessee:
                 papers]",
  title =        "22nd Annual Symposium on Foundations of Computer
                 Science: October 28--30, 1981, [Nashville, Tennessee:
                 papers]",
  publisher =    pub-IEEE,
  address =      pub-IEEE:adr,
  pages =        "ix + 429",
  year =         "1981",
  CODEN =        "ASFPDV",
  ISBN =         "????",
  ISBN-13 =      "????",
  ISSN =         "0272-5428",
  LCCN =         "TK7885.A1 S92 1981; QA76.6 .S95 1981",
  bibdate =      "Thu Dec 3 07:11:18 MST 1998",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  note =         "Formerly called the Annual Symposium on Switching and
                 Automata Theory. IEEE catalog no. 81CH1695-6.",
  acknowledgement = ack-nhfb,
  keywords =     "electronic data processing --- congresses; electronic
                 digital computers --- programming --- congresses;
                 machine theory --- congresses; switching theory ---
                 congresses; automata --- congresses; machine theory ---
                 congresses; electronic data processing --- congresses;
                 electronic digital computers --- programming ---
                 congresses",
}

@Proceedings{IEEE:1982:ASF,
  editor =       "{IEEE}",
  booktitle =    "23rd annual Symposium on Foundations of Computer
                 Science, November 3--5, 1982, Chicago, Illinois",
  title =        "23rd annual Symposium on Foundations of Computer
                 Science, November 3--5, 1982, Chicago, Illinois",
  publisher =    pub-IEEE,
  address =      pub-IEEE:adr,
  pages =        "vii + 387",
  year =         "1982",
  CODEN =        "ASFPDV",
  ISBN =         "????",
  ISBN-13 =      "????",
  ISSN =         "0272-5428",
  LCCN =         "QA76.6 .S95 1982",
  bibdate =      "Thu Dec 3 07:11:18 MST 1998",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  note =         "IEEE catalog no. 82CH1806-9. IEEE Computer Society
                 order no. 440.",
  acknowledgement = ack-nhfb,
  keywords =     "electronic data processing --- congresses; electronic
                 digital computers --- programming --- congresses;
                 machine theory --- congresses",
}

@Proceedings{IEEE:1983:ASF,
  editor =       "{IEEE}",
  booktitle =    "24th Annual Symposium on Foundations of Computer
                 Science: November 7--9, 1983, Tucson, Arizona",
  title =        "24th Annual Symposium on Foundations of Computer
                 Science: November 7--9, 1983, Tucson, Arizona",
  publisher =    pub-IEEE,
  address =      pub-IEEE:adr,
  pages =        "xii + 477",
  year =         "1983",
  CODEN =        "ASFPDV",
  ISBN =         "0-8186-0508-1",
  ISBN-13 =      "978-0-8186-0508-6",
  ISSN =         "0272-5428",
  LCCN =         "QA76.6 .S95 1983",
  bibdate =      "Thu Dec 3 07:11:18 MST 1998",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  note =         "IEEE catalog no. 83CH1938-0.",
  acknowledgement = ack-nhfb,
  keywords =     "electronic data processing --- congresses; electronic
                 digital computers --- programming --- congresses;
                 algorithms --- congresses; computational complexity ---
                 congresses",
}

@Proceedings{IEEE:1984:ASF,
  editor =       "{IEEE}",
  booktitle =    "25th annual Symposium on Foundations of Computer
                 Science, October 24--26, 1984, Singer Island, Florida",
  title =        "25th annual Symposium on Foundations of Computer
                 Science, October 24--26, 1984, Singer Island, Florida",
  publisher =    pub-IEEE,
  address =      pub-IEEE:adr,
  pages =        "xii + 518",
  year =         "1984",
  CODEN =        "ASFPDV",
  ISBN =         "0-8186-8591-3, 0-8186-0591-X (paperback),
                 0-8186-4591-1 (microfiche)",
  ISBN-13 =      "978-0-8186-8591-0, 978-0-8186-0591-8 (paperback),
                 978-0-8186-4591-4 (microfiche)",
  ISSN =         "0272-5428",
  LCCN =         "QA 76 S979 1984",
  bibdate =      "Thu Dec 3 07:11:18 MST 1998",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  note =         "IEEE catalog no. 84CH2085-9.",
  acknowledgement = ack-nhfb,
  keywords =     "electronic data processing --- congresses; electronic
                 digital computers --- programming --- congresses;
                 machine theory --- congresses",
}

@Proceedings{IEEE:1985:ASF,
  editor =       "{IEEE}",
  booktitle =    "26th annual Symposium on Foundations of Computer
                 Science, October 21--23, 1985, Portland, Oregon",
  title =        "26th annual Symposium on Foundations of Computer
                 Science, October 21--23, 1985, Portland, Oregon",
  publisher =    pub-IEEE,
  address =      pub-IEEE:adr,
  pages =        "xii + 552",
  year =         "1985",
  CODEN =        "ASFPDV",
  ISBN =         "0-8186-4644-6 (microfiche), 0-8186-8644-8 (casebound),
                 0-8186-0644-4 (paperback)",
  ISBN-13 =      "978-0-8186-4644-7 (microfiche), 978-0-8186-8644-3
                 (casebound), 978-0-8186-0644-1 (paperback)",
  ISSN =         "0272-5428",
  LCCN =         "QA 76 S979 1985",
  bibdate =      "Thu Dec 3 07:11:18 MST 1998",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  note =         "IEEE catalog no. 85CH2224-4. IEEE Computer Society
                 order no. 644.",
  acknowledgement = ack-nhfb,
  keywords =     "electronic data processing --- congresses; electronic
                 digital computers --- programming --- congresses;
                 machine theory --- congresses",
}

@Proceedings{IEEE:1986:ASF,
  editor =       "{IEEE}",
  booktitle =    "27th annual Symposium on Foundations of Computer
                 Science, October 27--29, 1986, Toronto, ON, Canada",
  title =        "27th annual Symposium on Foundations of Computer
                 Science, October 27--29, 1986, Toronto, {ON}, Canada",
  publisher =    pub-IEEE,
  address =      pub-IEEE:adr,
  pages =        "xiv + 517",
  year =         "1986",
  CODEN =        "ASFPDV",
  ISBN =         "0-8186-0740-8 (paperback), 0-8186-4740-X (microfiche),
                 0-8186-8740-1 (casebound)",
  ISBN-13 =      "978-0-8186-0740-0 (paperback), 978-0-8186-4740-6
                 (microfiche), 978-0-8186-8740-2 (casebound)",
  ISSN =         "0272-5428",
  LCCN =         "QA 76 S979 1986",
  bibdate =      "Thu Dec 3 07:11:18 MST 1998",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  note =         "IEEE catalog no. 86CH2354-9. IEEE Computer Society
                 order no. 740.",
  acknowledgement = ack-nhfb,
  keywords =     "electronic data processing --- congresses; machine
                 theory --- congresses; electronic digital computers ---
                 programming --- congresses",
}

@Proceedings{IEEE:1987:ASF,
  editor =       "{IEEE}",
  booktitle =    "28th annual Symposium on Foundations of Computer
                 Science, October 12--14, 1987, Los Angeles,
                 California",
  title =        "28th annual Symposium on Foundations of Computer
                 Science, October 12--14, 1987, Los Angeles,
                 California",
  publisher =    pub-IEEE,
  address =      pub-IEEE:adr,
  pages =        "xiv + 498",
  year =         "1987",
  CODEN =        "ASFPDV",
  ISBN =         "0-8186-0807-2, 0-8186-4807-4 (microfiche),
                 0-8186-8807-6 (casebound)",
  ISBN-13 =      "978-0-8186-0807-0, 978-0-8186-4807-6 (microfiche),
                 978-0-8186-8807-2 (casebound)",
  ISSN =         "0272-5428",
  LCCN =         "QA 76 S979 1987",
  bibdate =      "Thu Dec 3 07:11:18 MST 1998",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  note =         "IEEE Catalog no. 87CH2471-1. Computer Society order
                 number 807.",
  acknowledgement = ack-nhfb,
  keywords =     "electronic data processing --- congresses",
}

@Proceedings{IEEE:1988:ASF,
  editor =       "{IEEE}",
  booktitle =    "29th annual Symposium on Foundations of Computer
                 Science, October 24--26, 1988, White Plains, New York",
  title =        "29th annual Symposium on Foundations of Computer
                 Science, October 24--26, 1988, White Plains, New York",
  publisher =    pub-IEEE,
  address =      pub-IEEE:adr,
  pages =        "x + 614",
  year =         "1988",
  CODEN =        "ASFPDV",
  ISBN =         "0-8186-0877-3 (paperback), 0-8186-4877-5 (microfiche),
                 0-8186-8877-7 (hard)",
  ISBN-13 =      "978-0-8186-0877-3 (paperback), 978-0-8186-4877-9
                 (microfiche), 978-0-8186-8877-5 (hard)",
  ISSN =         "0272-5428",
  LCCN =         "QA 76 S979 1988",
  bibdate =      "Thu Dec 3 07:11:18 MST 1998",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  note =         "IEEE catalog no. 88CH2652-6. Computer Society order
                 no. 877.",
  acknowledgement = ack-nhfb,
  keywords =     "electronic data processing --- congresses",
}

@Proceedings{IEEE:1989:ASF,
  editor =       "{IEEE}",
  booktitle =    "30th annual Symposium on Foundations of Computer
                 Science, October 30--November 1, 1989, Research
                 Triangle Park, North Carolina",
  title =        "30th annual Symposium on Foundations of Computer
                 Science, October 30--November 1, 1989, Research
                 Triangle Park, North Carolina",
  publisher =    pub-IEEE,
  address =      pub-IEEE:adr,
  pages =        "xvii + 632",
  year =         "1989",
  CODEN =        "ASFPDV",
  ISBN =         "0-8186-1982-1 (casebound), 0-8186-5982-3
                 (microfiche)",
  ISBN-13 =      "978-0-8186-1982-3 (casebound), 978-0-8186-5982-9
                 (microfiche)",
  ISSN =         "0272-5428",
  LCCN =         "QA 76 S979 1989; TK7885.A1 S92 1989",
  bibdate =      "Thu Dec 3 07:11:18 MST 1998",
  bibsource =    "http://www.math.utah.edu/pub/tex/bib/focs1980.bib",
  note =         "Formerly called the Annual Symposium on Switching and
                 Automata Theory. IEEE catalog no. 89CH2808-4. Computer
                 Society order no. 1982.",
  acknowledgement = ack-nhfb,
  keywords =     "electronic data processing --- congresses;
                 computational complexity --- congresses; electronic
                 data processing --- congresses; machine theory ---
                 congresses",
}