@string{JACM = "J. ACM"}

@InProceedings{Karp:Luby:Meyer:92,
    Author = Karp #&# Luby #&# Fmadh,
    Title = "Efficient {PRAM} Simulation on a Distributed Memory Machine",
    BookTitle = stoc92,
    Year = 1992,
    Pages = {318-326},
}

@InProceedings{Dietzfelbinger:Gil:Matias:Pippenger:92,
    Ordinal = 95,
    Author = Dietzfelbinger #&# Gil #&# Matias #&# Pippenger,
    Title = "Polynomial Hash Functions Are Reliable",
    Booktitle = icalp92,
    Pages = "235-246",
    Month = jul,
    Year = 1992
}


@UnPublished{Karp:Luby:Meyer:91:Manuscript,
    Author = Karp #&# Luby #&# Fmadh,
    Title = "Efficient {PRAM} Simulation on a Distributed Memory Machine",
    Year = 1991,
    Month = Dec,
    Note = "Manuscript, to appear",
}

@Article{Ramakrishna:Larson:89,
    Author = Ramakrishna #&# Larson,
    Title = "File Organization Using Composite Perfect Hashing",
    Year = 1989,
    Journal = tods,
    Volume = 14,
    Number = 9,
    Pages = "231-263",
}


@InProceedings{Cellis:Larson:Munro:85,
    Ordinal = 155,
    Author = Cellis #&# Larson #&# Munro,
    Title = "Robin Hood Hashing",
    Year = 1985,
    Month = Oct,
    BookTitle = focs85,
    Pages = "281-288",
}

@InProceedings{Ranade:Bhatt:Johnson:88,
    Author = Ranade #&# Bhatt #&# Johnsson,
    Title = "The Fluent Abstract Machine",
    Year = 1988,
    BookTitle = "Proc.\ of the 5th MIT Conference on Advanced Research in {VLSI}",
    Pages = "71--93",
}

%   CrossRef = "FOCS88",
@InProceedings{Shoup:88,
    Ordinal = 72,
    Author = Shoup,
    Title = "New Algorithms for Finding Irreducible Polynomials over Finite Fields",
    BookTitle = focs88,
    Year = 1988,
    Pages = "283-290",
    Abstract = {
        We present a new algorithm for finding an irreducible
        polynomial of specified degree over a finite field. Our
        algorithm is determinstic and it runs in polynomial time for
        fields of small characteristic. We in fact prove the stronger
        result that the problem of finding irreducible polynomials over
        a finite field $K$ is determinsitc polynomial time reducible to
        the problem of factoring polynomials over the prime field of
        $K$.
    },
}

@InProceedings{BBGSV:89,
    Ordinal = 81,
    Author = Berkman #&# Breslauer #&# Galil #&# Schieber #&# Vishkin,
    Title = "Highly Parallelizable Problems",
    Year = 1989,
    BookTitle = stoc89,
    Pages = "309-319",
}

@Article{Schieber:Vishkin:88,
    Author = Schieber #&# Vishkin,
    Title = "On finding lowest common ancestors:
        simplification and parallelization",
    Journal= sicomp,
    Volume = "17",
    Number = 6,
    Year = "1988",
    Pages = "1253-1262"
}

@InProceedings{DM:89,
    Ordinal = 63,
    Author = Dietzfelbinger #&# Fmadh,
    Title = "An Optimal Parallel Dictionary",
    Year = 1989,
    BookTitle = spaa89,
    Pages = "360-368",
}

@TechReport{DM:89:Report,
    Ordinal = 156,
    Author = Dietzfelbinger #&# Fmadh,
    Title = "An Optimal Parallel Dictionary",
    Year = 1989,
    Month = Apr,
    Institution = paderborn,
}

%   CrossRef = "ICALP90",
@InProceedings{DM:90,
    Ordinal = 45,
    Author = Dietzfelbinger #&# Fmadh,
    Title = "A New Universal Class of Hash Functions and Dynamic hashing
            in Real Time",
    BookTitle = icalp90,
    Pages = {6-19},
    Year = 1990,
}

%   CrossRef = "STOC90",
@InProceedings{DM:90a,
    Ordinal = 32,
    Author = Dietzfelbinger #&# Fmadh,
    Title = "How to Distribute a Dictionary in a Complete Network",
    BookTitle = stoc90,
    Year = 1990,
    Comment = "Manuscript -- needs work! (copy from stoc?)",
}

%   CrossRef = "STOC90",
@InProceedings{Gil:Meyer:Wigderson:90,
    Ordinal = 62,
    Author = Gil #&# Fmadh #&# Wigderson,
    Title = {Not All Keys Can be Hashed in Constant Time},
    BookTitle = stoc90,
    Year = 1990,
    Pages = {244-253},
}

%   CrossRef = "STOC90",
@InProceedings{Fredman:Willard:90,
    Ordinal = 219,
    Author = Fredman #&# Willard,
    BookTitle = stoc90,
    Title = "BLASTING Through The Information Theoretic Barrier With FUSION TREES",
    Pages = "1-7",
    Year = 1990,
}

%   CrossRef = "FOCS90",
@InProceedings{Fredman:Willard:FOCS:90,
    Title = "Trans-dichotomous Algorithms for Minimum Spanning Trees and Shortest
        Paths",
    Author = Fredman #&# Willard,
    BookTitle = focs90,
    Pages = "719-725",
    Year = 1990,
}

@InProceedings{Willard:92,
    Author = Willard,
    Title = "Applications of the Fusion Tree Method to Computational Geometry and Searching",
    BookTitle = soda92,
    Pages = "286-295",
    Year = 1992,
}

@Misc{Gil:90,
    Author = Gil,
    Title = "Fast Load Balancing on {PRAM}",
    Year = 1990,
    Month = "Manuscript, November",
    Note = "Also in the Third {IEEE} Symposium on Parallel and Distributed Processing (SPDP '91)",
}

@InProceedings{Shannon:89,
    Ordinal = 90,
    Author = Shannon,
    Title = {Optimal On-line Load Balancing},
    Year = 1989,
    BookTitle = spaa89,
    Pages = "235-245",
}

@InProceedings{Broder:Karlin:90,
    Author = Broder #&# Karlin,
    Title = "Multilevel Adaptive Hashing",
    Year = 1990,
    BookTitle = soda90,
    Place = {San Francisco},
}

@Misc{Hagerup:Private:90,
    Author = Hagerup,
    Title = "Private Communication",
    Year = 1990,
}

@Misc{Hagerup:Private:Oct:90,
    Author = Hagerup,
    Title = "Private Communication",
    Year = 1990,
    Month = oct,
}

@Misc{Hagerup:Private:Nov:90,
    Author = Hagerup,
    Title = "Private Communication",
    Year = 1990,
    Month = nov,
}

@Article{Hagerup:87,
    Author = Hagerup,
    Title = "Towards Optimal Parallel Bucket Sorting",
    Year = 1987,
    Journal = infocomp,
    Volume = 75,
    Pages = "39-51",
}

@InProceedings{Hagerup:Revolution:92,
    Author = Hagerup,
    Title = "The Log-Star Revolution",
    Year = 1992,
    Pages = "259-278",
    BookTitle = stacs92,
}

@InProceedings{Hagerup:Simulations:92,
    Author = Hagerup,
    Title = "Fast and Optimal Simulations between {CRCW} {PRAM}s",
    Year = 1992,
    Pages = "45--56",
    BookTitle = stacs92,
}

@Article{Carter:Wegman:79,
    Ordinal = 67,
    Author = Carter #&# Wegman,
    Title = "Universal Classes of Hash Functions",
    Year = 1979,
    Journal = jcss,
    Volume = 18,
    Pages = "143-154",
}

@InProceedings{Wegman:Carter:79,
    Ordinal = 73,
    Author = Wegman #&# Carter,
    Title = "New Classes and Applications of Hash Functions",
    Year = 1979,
    BookTitle = focs79,
    Pages = "175-182",
    Keywords = "Hashing, universal",
}

@Article{Wegman:Carter:81,
    Ordinal = 96,
    Author = Wegman #&# Carter,
    Title = "New Hash Functions and their Use in Authentication and Set Equality",
    Year = 1981,
    Journal = jcss,
    Volume = 22,
    Pages = "265-279",
    Keywords = "Hashing, universal",
}

@InProceedings{Markowsky:Carter:Wegman,
    Ordinal = 68,
    Author = Markowsky #&# Carter #&# Wegman,
    Title = "Analysis of a Universal Class of Hash Functions",
    Year = 1978,
    BookTitle = MFCS78,
    pages = "345-354",
    Keywords = "Hashing, universal",
}

@Article{Karp:Rabin:87,
    Ordinal = 235,
    Author = Karp #&# Rabin,
    Title = "Efficient Randomized Pattern-Matching Algorithms",
    Year = 1987,
    Journal = IBMJRD,
    Volume = 31,
    Pages = "249-260",
}

@Article{Vishkin:83,
    Author = Vishkin,
    Title = "Implementation of Simultaneous Memory Address Access in Models that Forbid it",
    Year = 1983,
    Journal = jalg,
    Volume = 4,
    Pages = "45-50",
}

@Article{Cole:Vishkin:86,
    Author = Cole #&# Vishkin,
    Title = "Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking",
    Year = 1986,
    Journal = inf&ctrl,
    Volume = 70,
    Pages = "32-53",
}

@InProceedings{Cole:Vishkin:FOCS:86,
    Ordinal = 31,
    Author = Cole #&# Vishkin,
    Title = "Approximate and Exact Parallel Scheduling with Applications to List, Tree and Graph Problems",
    Year = 1986,
    BookTitle = focs86,
    Pages = "478-491",
}

@Article{Cole:Vishkin:88,
    Author = Cole #&# Vishkin,
    Title = "Approximate Parallel Scheduling. {P}art {I}: The Basic Technique with Applications to Optimal Parallel List Ranking in Logarithmic Time",
    Year = 1988,
    Month = Feb,
    Journal = sicomp,
    Volume = 17,
    Number = 1,
    Pages = "128-142",
}

@Article{Cole:Vishkin:88:Centroid,
    Ordinal = 130,
    Author = Cole #&# Vishkin,
    Title = "The Accelerated Centroid Decomposition Technique for Optimal Parallel Tree Evaluation in Logarithmic Time",
    Year = 1988,
    Journal = algorithmica,
    Pages = "329-346",
}

@Article{Cole:Vishkin:89,
    Ordinal = 34,
    Author = Cole #&# Vishkin,
    Title = "Faster Optimal Parallel Prefix Sums and List Ranking",
    Year = 1989,
    Journal = infocomp,
    Volume = 81,
    Pages = "334-352",
}

@InProceedings{Cole:86,
    Author = Cole,
    Title = "Parallel Merge Sort",
    Year = 1986,
    BookTitle = focs86,
    Pages = "511-516",
}

@InProceedings{Vishkin:84,
    Ordinal = 132,
    Author = Vishkin,
    Title = "Randomized Speed-ups in Parallel Computations",
    Year = 1984,
    BookTitle = stoc84,
    Pages = "230-239",
}

@Book{Mehlhorn:Book:I,
    Ordinal = 66,
    Author = Mehlhorn,
    Title = "Data Structures and Algorithms {I}: Sorting and Searching",
    Year = 1984,
    Publisher = "Springer-Verlag, Berlin Heidelberg",
    Note = "EATCS Monographs on Theoretical Computer Science",
}

@Article{Vishkin:84b,
    Ordinal = 123,
    Author = Vishkin,
    Title = "A Parallel-Design Distributed-Implementation (PDDI) General Purpose Computer",
    Year = 1984,
    Journal = tcs,
    Volume = 32,
    Pages = "157-172",
    Keyword = "Simulation, emulation",
}

@Article{Mehlhorn:Vishkin:84,
    Ordinal = 64,
    Author = Mehlhorn #&# Vishkin,
    Title = "Randomized and Deterministic Simulations of {PRAM}s by Parallel Machines with Restricted Granularity of Parallel Memories",
    Year = 1984,
    Journal = acta,
    Volume = 21,
    Pages = "339-374",
}

@InProceedings{Luby:85,
    Author = Luby,
    Title = "A Simple Parallel Algorithm for the Maximal Independent Set Problem",
    Year = 1985,
    BookTitle = stoc85,
    Pages = "1-10",
}

@Article{Luby:86,
    Author = Luby,
    Title = "A Simple Parallel Algorithm for the Maximal Independent Set Problem",
    Year = 1986,
    Journal = sicomp,
    Volume = 15,
    Number = 4,
    Pages = "1036-1053",
}

%   CrossRef = "FOCS88",
@InProceedings{Luby:88,
    Author = Luby,
    Title = "Removing Randomness in Parallel Computation Without a Processor Penalty",
    BookTitle = focs88,
    Year = 1988,
    Pages = "162-173",
}

@InProceedings{Reif:85,
    Author = Reif,
    Title = "An Optimal Parallel Algorithm for Integer Sorting",
    Year = 1985,
    BookTitle = focs85,
    Pages = "496-503",
    Note = "With S. Rajasekaran, SIAM J. Comput., Vol. 18, No. 3, pp. 594-607, June 1989",
}

@Article{Sen:90,
    Ordinal = 212,
    Author = Sen,
    Title = "Finding an Approximate Median with High Probability in Constant Parallel Time",
    Year = 1990,
    Month = Mar,
    Journal = ipl,
    Volume = 34,
    Pages = "77--80",
}

@Article{Reif:Sen:94,
    Author = Reif #&# Sen,
    Title = "Randomized Algorithms for Binary Search and Load
    Balancing on Fixed Connection Networks with Geometric Applications",
    Year = 1994,
    Month = jun,
    Journal = ipl,
    Volume = 23,
    Number = 3,
    Pages = "633-651",
}

@UnPublished{Rajasekaran:Sen:91a,
    Author = Rajasekaran #&# Sen,
    Title = "On Parallel Integer Sorting",
    Year = 1991,
    Note = "Manuscript",
}

@InCollection{Rajasekaran:Sen:91,
    Ordinal = 211,
    Author = Rajasekaran #&# Sen,
    Title = "Random Sampling Techniques and Parallel Algorithms Design",
    Year = 1991,
    BookTitle = "Synthesis of Parallel Algorithms",
    Editor = Reif,
    Publisher = "Morgan Kaufmann",
}



@Article{Rajasekaran:Reif:89,
    Author = Rajasekaran #&# Reif,
    Title = "Optimal and Sublogarithmic Time Randomized Parallel Sorting Algorithms",
    Year = 1989,
    Journal = sicomp,
    Volume = 18,
    Pages = "594-607",
}

@Article{Spirakis:88,
    Ordinal = 147,
    Author = Spirakis,
    Title = "Optimal Parallel Randomized Algorithms for Sparse Addition and Identification",
    Year = 1988,
    Journal = infocomp,
    Volume = 76,
    Pages = "1-12",
}

@Article{Sprugnoli:77,
    Author = Sprugnoli,
    Title = "Perfect hash functions: a single probe retrieval method for
        static sets",
    Year = 1977,
    Journal = cacm,
    Volume = 20,
    Pages = "841-850",
}

@Article{FKS:84,
    Ordinal = 50,
    Author = Fredman #&# Komlos #&# Szemeredi,
    Title = "Storing a Sparse Table with ${O}(1)$ Worst Case Access Time",
    Year = 1984,
    Month = Jul,
    Journal = jacm,
    Volume = 31,
    Number = 3,
    Pages = "538-544",
}

@InProceedings{Awerbuch:Israeli:Shiloach:84,
    Author = Awerbuch #&# Israeli #&# Shiloach,
    Title = "Finding Euler Circuits in Logarithmic Parallel Time",
    Year = 1984,
    BookTitle = stoc84,
    Pages = "249-257",
    Place = "Washington, D.C.",
}

@Article{Hirschberg:78,
    Author = Hirschberg,
    Title = "Fast Parallel Sorting Algorithms",
    Year = 1978,
    Journal = cacm,
    Volume = 21,
    Number = 8,
    Pages = "657-661",
}

@InProceedings{Reischuk:81,
    Ordinal = 136,
    Author = Reischuk,
    Title = "A Fast Probabilistic Parallel Sorting Algorithm",
    Year = 1981,
    BookTitle = focs81,
    Pages = "212-219",
    Place = "Nashville, Tennesse",
}

@Article{Reischuk:85,
    Ordinal = 137,
    Author = Reischuk,
    Title = "Probabilistic Parallel Algorithms for Sorting and Selection",
    Year = 1985,
    Month = May,
    Journal = sicomp,
    Volume = 14,
    Number = 2,
    Pages = "396--409",
}

@Article{Willard:86,
    Author = Willard,
    Title = "Log-logarithmic Selection Resolution Protocols in a Multiple Access Channel",
    Year = 1986,
    Journal = sicomp,
    Volume = 15,
    Pages = "468-477",
}

@Article{Yao,
    Ordinal = 15,
    Author = Yao,
    Title = "Should Tables Be Sorted?",
    Year = 1981,
    Month = Jul,
    Journal = jacm,
    Volume = 28,
    Number = 3,
    Pages = "615-628",
}

@InProceedings{Hagerup:88b,
    Author = Hagerup,
    Title = "Optimal Parallel Algorithms on Planar Graphs",
    Year = 1988,
    BookTitle = awoc88,
    Pages = "24-32",
}

@InProceedings{Attiya:Snir:88,
    Author = Attiya #&# Snir,
    Title = "Better Computing on the Anonymous Ring",
    Year = 1988,
    BookTitle = awoc88,
    Pages = "329-338",
}

@Article{Attiya:Snir:91,
    Ordinal = 121,
    Author = Attiya #&# Snir,
    Title = "Better Computing on the Anonymous Ring",
    Year = 1991,
    Journal = jalg,
    Volume = 12,
    Pages = "204-238",
}

@Article{Duris:Galil:91,
    Ordinal = 122,
    Author = Duris #&# Galil,
    Title = "Two Lower Bounds in Asynchronous Distributed Computation",
    Year = 1991,
    Journal = jcss,
    Volume = 42,
    Pages = "254-266",
}

@InProceedings{Attiya:Dolev:Gil:84,
    Author = Attiya #&# Dolev #&# Gil,
    Title = "Asynchronous Byzantine Consensus",
    Year = 1984,
    BookTitle = podc84,
}

@InProceedings{furer:88,
    Author = "Martin F\umlaut{u}rer",
    Title = "Universal Hashing in {VLSI}",
    Year = 1988,
    BookTitle = awoc88,
    Pages = "312-318",
}

@InProceedings{Anderson:Miller:88,
    Ordinal = 91,
    Author = Anderson #&# Miller,
    Title = "Deterministic Parallel List Ranking",
    Year = 1988,
    Month = Jun # / # Jul,
    BookTitle = awoc88,
    Pages = "81-90",
    Editor = Reif,
    Publisher = SV,
}

@TechReport{Anderson:Miller:OCPC:88,
    Author = Anderson #&# Miller,
    Title = "Optical Communication for Pointer Based Algorithms",
    Year = 1988,
    Institution = "Computer Science Department, University of
        Southern California, Los Angeles, CA 90089-0782 USA",
    Number = "CRI 88-14",
}

@Article{Anderson:Miller:90,
    Author = Anderson #&# Miller,
    Title = "Optimal Parallel Algorithms for List-Ranking",
    Year = 1990,
    Journal = ipl,
    Volume = 33,
    Pages = "269--273",
    Keywords = "Parallel Processing, analysis of alggorithms",
    Abstract = {
        In this paper we give a simple parallel algorithm for the
        list-ranking problem. The algorithm is randomized $O(\log n)$
        time, $n/\log n$ processor algorithm for the \EREW{} \PRAM{}.
        The algorithm is substantially simpler than other optimal
        algorithms for list ranking
    },
}

@InProceedings{Furer:87,
    Ordinal = 61,
    Author = "Martin F{\"{u}}rer",
    Title = "The Power of Randomness for Communication Complexity",
    Year = 1987,
    BookTitle = stoc87,
    Pages = "178-181",
}

@InProceedings{Li:Yesha:86,
    Ordinal = 28,
    Author =  Li #&# Yesha,
    Title = "New Lower Bounds for Parallel Computation",
    Year = 1986,
    BookTitle = stoc86,
    Pages = {177-187},
}

@Article{Li:Yesha:87,
    Author =  Li #&# Yesha,
    Title = "Separation and Lower Bounds for ROM and Nondeterministic Models of Parallel Computation",
    Year = 1987,
    Journal = infocomp,
    Volume = 73,
    Pages = "102-128",
}

@Article{Rajan:Ghosh:Gupta:89,
    Author = Rajan #&# Ghosh #&# Gupta,
    Title = "An Efficient Parallel Algorithm for Random Sampling",
    Year = 1989,
    Journal = ipl,
    Volume = 30,
    Pages = "265-268",
}

@Article{Chlebus:88,
    Author = Chlebus,
    Title = "A Parallel Bucket Sort",
    Year = 1988,
    Journal = ipl,
    Volume = 27,
    Pages = "57-61",
}

@Article{Chlebus:89,
    Author = Chlebus,
    Title = "Parallel Iterated Bucket Sort",
    Year = 1989,
    Journal = ipl,
    Volume = 31,
    Pages = "181-183",
}

@Article{Hagerup:89,
    Author = Hagerup,
    Title = "Hybridsort Revisited and Parallelized",
    Year = 1989,
    Journal = ipl,
    Volume = 32,
    Pages = "35-39",
}


@Article{Devroye:86,
    Ordinal = 93,
    Author = "Luc Devroye",
    Title = "A Note on the Height of Binary Search Trees",
    Year = 1986,
    Journal = jacm,
    Volume = 33,
    Pages = "489-498",
}

@InProceedings{Aho:Lee:86,
    Ordinal = 87,
    Author = Aho #&# "David Lee",
    Title = "Storing a Dynamic Sparse Table",
    Year = 1986,
    BookTitle = focs86,
    Pages = "55-60",
}

@InProceedings{Chlebus:Diks:Hagerup:Radzik:88,
    Ordinal = 125,
    Author = Chlebus #&# Diks #&# Hagerup #&# Radzik,
    Title = "Efficient Simulations between Concurrent-Read Concurrent-Write {PRAM} Models",
    Year = 1988,
    BookTitle = mfcs88,
    Pages = "231-239",
    Place = "Carlsbad, CSSR",
}

@InProceedings{Chlebus:Diks:Hagerup:Radzik:89,
    Ordinal = 49,
    Author = Chlebus #&# Diks #&# Hagerup #&# Radzik,
    Title = "New Simulations Between {CRCW} {PRAM}s",
    Year = 1989,
    BookTitle = fct89,
    Pages = "95-104",
    Place = "Szeged, Hungary",
}

@InProceedings{Karlin:Upfal:86,
    Ordinal = 117,
    Author = Karlin #&# Upfal,
    Title = "Parallel Hashing---an Efficient Implementation of Shared Memory",
    Year = 1986,
    Month = May,
    BookTitle = stoc86,
    Pages = "160-168",
}

%   CrossRef = "FOCS88",
@InProceedings{DKMMRT:88,
    Ordinal = 54,
    Author = Dietzfelbinger #&# Karlin #&# Mehlhorn #&# Fmadh #&# Rohnert #&# Tarjan,
    Title = "Dynamic Perfect Hashing: Upper and Lower Bounds",
    BookTitle = focs88,
    Year = 1988,
    Pages = "524-531",
    Note1 = "Revised Version: Tech. Report 77, University of Paderborn, FB 17 Mathematik-Informatik, 1991; to appear in {\em SIAM J. Comput.}",
    Note = "To appear in {\em SIAM J. Comput.}",
}

@TechReport{DKMMRT:91A,
    Ordinal = 86,
    Author = Dietzfelbinger #&# Karlin #&# Mehlhorn #&# Fmadh #&# Rohnert #&# Tarjan,
    Title = "Dynamic Perfect Hashing: Upper and Lower Bounds",
    Year = 1991,
    Month = Jan,
    Number = 70,
    Institution = paderborn,
    Note = "{\it Revised Version} of the paper of the same title that appeared in {\sl Proc. of the 29th IEEE FOCS}, 1988, pp. 524--531.",
}

@Article{DKMMRT:94,
    Ordinal = 86,
    Author = Dietzfelbinger #&# Karlin #&# Mehlhorn #&# Fmadh #&# Rohnert #&# Tarjan,
    Title = "Dynamic Perfect Hashing: Upper and Lower Bounds",
    Journal = sicomp,
    Year = 1994,
    Month = aug,
    Volume = 23,
    Number = 4,
    Note1 = "{\it Revised Version} of the paper of the same title that appeared in {\sl Proc. of the 29th IEEE FOCS}, 1988, pp. 524--531.",
}

@TechReport{Paul:Vishkin:Wagener:83:Report,
    Author = Paul #&# Vishkin #&# Wagener,
    Title = "Parallel computation on 2-3 trees",
    Year = 1983,
    Month = Apr,
    Number = 70,
    Institution = "Department of Computer Science, New York University",
}

@InProceedings{Paul:Vishkin:Wagener:83,
    Author =  Paul #&# Vishkin #&#  Wagener,
    Title = "Parallel Dictionaries on 2-3 Trees",
    Year = 1983,
    BookTitle = icalp83,
    Pages = "597-609",
}

@Book{AHU:74,
    Author = Aho #&# Hopcroft #&# Ullman,
    Title = "The Design and Analysis of Computer Algorithms",
    Year = 1974,
    Publisher = aw,
    Address = reading,
}

@Book{AHU:83,
    Ordinal = 232,
    Author = Aho #&# Hopcroft #&# Ullman,
    Title = "Data Structures and Algorithms",
    Year = 1983,
    Publisher = aw,
    Address = reading,
}


@InProceedings{Chandra:Fortune:Lipton:STOC83,
    Ordinal = 106,
    Author = Chandra #&# Fortune #&# Lipton,
    Title = "Unbounded Fan-in Circuits and Associative Functions",
    Year = 1983,
    BookTitle = stoc83,
    Pages = "52-60",
}

@Article{Chandra:Fortune:Lipton:85,
    Ordinal = 107,
    Author = Chandra #&# Fortune #&# Lipton,
    Title = "Unbounded Fan-in Circuits and Associative Functions",
    Year = 1985,
    Journal = jcss,
    Pages = "222-234",
}

@InProceedings{Schmidt:Siegel:89,
    Ordinal = 65,
    Author = Schmidt #&# Siegel,
    Title = "The Spatial Complexity of Oblivious $k$-probe Hash Functions",
    Year = 1989,
    BookTitle = stoc89,
}

%   CrossRef = "STOC90",
@InProceedings{Schmidt:Siegel:stoc90,
    Ordinal = 69,
    Author = Schmidt #&# Siegel,
    Title = "The Analysis of Closed Hashing under Limited Randomness",
    BookTitle = stoc90,
    Year = 1990,
}

%   CrossRef = "FOCS89",
@InProceedings{Siegel:89,
    Ordinal = 29,
    Author = Siegel,
    Title = "On Universal Classes of Fast High Performance Hash Functions, their Time-Space Tradeoff, and their Applications",
    BookTitle = focs89,
    Year = 1989,
    Pages = "20-25",
    Keywords = "Hashing, Expanders",
}

@InProceedings{Ajtai:Fredman:Komlos:83,
    Author = Ajtai #&# Fredman #&# Komlos,
    Title = "Hash Functions for Priority Queues",
    Year = 1983,
    BookTitle = focs83,
    Pages = "299-303",
}

@Article{Ajtai:Fredman:Komlos:84,
    Author = Ajtai #&# Fredman #&# Komlos,
    Title = "Hash Functions for Priority Queues",
    Year = 1984,
    Journal = inf&ctrl,
    Volume = 63,
    Number = 3,
    Pages = "217--225",
    Abstract = {
        The complexity of priority queue operations is analyzed with
        respect to the cell probe computational model of A. Yao [J.
        Assoc.\ Comput.\ Mach.\ 28 (1981), No.\ 3, 615--628]. A method
        utilizing families of hash functions is developed which permits
        priority queue operations to be implemented in constant
        worst-case time provided that a size constraint is satisfied.
        The minimum necessary size of a family of hash functions for
        computing the rank function is estimated and contrasted with
        the minimum size required for perfect hashing.
    },
}

@InProceedings{Galil:84,
    Author = Galil,
    Title = "Optimal Parallel Algorithms for String Matching",
    Year = 1984,
    BookTitle = stoc84,
    Pages = "240-248",
}

@Article{Eppstein:Galil:88,
    Ordinal = 166,
    Author = Eppstein #&# Galil,
    Title = "Parallel Algorithmic Techniques for Combinatorial Computation",
    Year = 1988,
    Journal = "Ann. Rev. Comput. Sci.",
    Volume = 3,
    Pages = "233-283",
}

@Article{Fisher:Ladner:80:WhatIsThis?,
    Author = "M. J. Fisher" #&# "Richard E. Ladner",
    Title = "Parallel Prefix Computation",
    Year = 1980,
    Journal = jacm,
    Volume = 27,
    Pages = "831-838",
}

@TechReport{Eckstein:79,
    Author = Eckstein,
    Title = "Simultaneous Memory Access",
    Year = 1979,
    Volume = "TR-79-6",
    Institution = "Computer Science Dept., Iowa State Univ.",
    Place = "Ames, Iowa",
}

@Article{Cook:Dwork:Reischuk:86,
    Author = Cook #&# Dwork #&# Reischuk,
    Title = "Upper and Lower Time Bounds for Parallel Random Access Machines Without Simultaneous Writes",
    Year = 1986,
    Journal = sicomp,
    Volume = 15,
    Pages = "87-97",
}

@InProceedings{Beame:Hastad:87,
    Author = Beame #&# Hastad,
    Title = "Optimal Bounds for Decision Problems on the {CRCW} {PRAM}",
    Year = 1987,
    BookTitle = stoc87,
    Pages = "83-93",
}

@Article{Beame:Hastad:89,
    Author = Beame #&# Hastad,
    Title = "Optimal Bounds for Decision Problems on the {CRCW} {PRAM}",
    Year = 1989,
    Month = Jul,
    Journal = jacm,
    Volume = 36,
    Number = 3,
    Pages = "643-670",
}

@InProceedings{Hastad:86,
    Author = Hastad,
    Title = "Almost Optimal Lower Bound for Small Depth Circuits",
    Year = 1986,
    BookTitle = stoc86,
    Pages = "6-20",
}

@InProceedings{Fich:Ragde:Wigderson:84,
    Ordinal = 44,
    Author = Fich #&# Ragde #&# Wigderson,
    Title = "Relations Between Concurrent-Write Models of Parallel Computation (preliminary version)",
    Year = 1984,
    BookTitle = podc84,
    Pages = "179--189",
}

@Article{Fich:Ragde:Wigderson:88a,
    Ordinal = 35,
    Author = Fich #&# Ragde #&# Wigderson,
    Title = "Relations Between Concurrent-Write Models of Parallel Computation",
    Year = 1988,
    Month = Jun,
    Journal = sicomp,
    Volume = 17,
    Pages = "606-627",
    Keywords = {Simulations, Emulations},
}

@Article{Fich:Ragde:Wigderson:88,
    Ordinal = 37,
    Author = Fich #&# Ragde #&# Wigderson,
    Title = "Simulations Among Concurrent-Write {PRAM}s",
    Year = 1988,
    Journal = algorithmica,
    Volume = 3,
    Pages = "43-51",
}

@InCollection{Fich:Meyer:Wigderson:86,
    Ordinal = 33,
    Author = Fich #&# Fmadh #&# Wigderson,
    Title = "Lower bounds for parallel random-access machines with unbounded shared memory",
    Year = 1986,
    BookTitle = "Advances in Computing Research",
    Publisher = "JAI Press",
    Keywords = {Simulations, Emulations, Lower Bound},
}

@Article{Kucera:82,
    Author = Kucera,
    Title = "Parallel Computation and Conflicts in Memory Access",
    Year = 1982,
    Journal = ipl,
    Volume = 14,
    Pages = "93-96",
}
@Book{Berge:73,
    Author = "C. Berge",
    Title = "Graphs and Hypergraphs",
    Year = "1973",
    Publisher = nh,
}


@Book{Wolfram:Book:91,
    Author = Wolfram,
    Title = "Mathematica : a system for doing mathematics by computer",
    Year = "1991",
    Publisher = aw,
    Address = reading,
    Edition = "2nd",
}

@Book{Graham:Knuth:Patashnik:89,
    Author = Graham #&# Knuth #&# Patashnik,
    Title = "Concrete Mathematics",
    Year = "1989",
    Month = may,
    Series = "A Foundation for Computer Science",
    Publisher = aw,
    Address = reading,
    ISBN = "0-201-14236-8",
    LIBRARY-Of-Congress = "QA39.2.G733 1988, 510--dc19, 88-3779 CIP",
    LIBRARY = "510 G74c",
    BARCODE = "1521627",
}

@Book{Knuth:Book:II:81,
    Author = Knuth,
    Title = "Seminumerical Algorithms",
    Year = "{\noopsort{1973c}}1981",
    Month = "10~" # jan,
    Series = "The Art of Computer Programming",
    Volume = 2,
    Edition = "Second",
    Publisher = aw,
    Address = reading,
}

@Book{Knuth:Book:III:73,
    Ordinal = 110,
    Author = Knuth,
    Title = "Sorting and Searching",
    Year = 1973,
    Series = "The Art of Computer Programming",
    Volume = 3,
    Publisher = aw,
    Address = reading,
}

@InProceedings{AKS:83,
    Author = Ajtai #&# Komlos #&# Szemeredi,
    Title = "An ${O}(n \log n)$ Sorting Network",
    Year = 1983,
    BookTitle = stoc83,
    Pages = "1-9",
}

@Article{Ajtai:Komlos:Szemeredi:78,
    Author = Ajtai #&# Komlos #&# Szemeredi,
    Title = "There is no fast single hashing function",
    Year = 1978,
    Journal = ipl,
    Volume = 7,
    Pages = "270-273",
}

@InProceedings{Leighton:84,
    Author = Leighton,
    Title = "Tight Bounds on the Complexity of Parallel Sorting",
    Year = 1984,
    BookTitle = stoc84,
    Pages = "71-80",
}

@InCollection{Mehlhorn:Tsakalidis:90,
    Author = Mehlhorn #&# Tsakalidis,
    Title = "Data Structures",
    Year = 1990,
    BookTitle = Handbook,
    Volume = "A",
    Pages = "301--341",
    Editor = van-Leeuwen,
    Publisher = "North-Holland, Amsterdam",
}

@InCollection{Karp:Ramachandran:90,
    Ordinal = 168,
    Author = Karp #&# Ramachandran,
    Title = "Parallel Algorithms for Shared-Memory Machines",
    Year = 1990,
    BookTitle = Handbook,
    Volume = "A",
    Pages = "869--941",
    Editor = van-Leeuwen,
    Publisher = "North-Holland, Amsterdam",
}

@TechReport{Karp:Ramachandran:88:TR,
    Ordinal = 167,
    Author = Karp #&# Ramachandran,
    Title = "A Survey of Parallel Algorithms for Shared-Memory Machines",
    Year = 1988,
    Number = "UCB/CSD 88/408",
    Institution = "Computer Science Division (EECS) U. C. Berkeley",
}

@Article{Kirkpatrick:Reisch:84,
    Author = Kirkpatrick #&# Reisch,
    Title = "Upper Bounds for Sorting Integers on Random Access Machines",
    Year = 1984,
    Journal = tcs,
    Volume = 28,
    Pages = "263-276",
}

@InProceedings{Paul:Simon:80,
    Author = Paul #&# Simon,
    Title = "Decision Trees and Random Access Machines",
    Year = 1980,
    BookTitle = "Symp. uber Logic und Algorithmik",
    Place = "Zurich",
}

@Article{Alt:Hagerup:Mehlhorn:Preparata:87,
    Author = Alt #&# Hagerup #&# Mehlhorn #&# Preparata,
    Title = "Deterministic Simulation of Idealized Parallel Computers on More Realistic Ones",
    Year = 1987,
    Journal = sicomp,
    Volume = 16,
    Pages = "808-835",
}

@InProceedings{Ranade:87,
    Ordinal = 118,
    Author = Ranade,
    Title = "How to Emulate Shared Memory",
    Year = 1987,
    BookTitle = focs87,
    Pages = "185-194",
}

@Article{Ranade:91,
    Ordinal = 119,
    Author = Ranade,
    Title = "How to Emulate Shared Memory",
    Year = 1991,
    Journal = jcss,
    Volume = 42,
    Pages = "307-326"
}

--Typo too, can you look it up?
@InProceedings{Manzini:Somalvico:91,
    Ordinal = 120,
    Author = "Giovanni Manzini" #&# "Marco Somalvico",
    Title = "Probabilistic Performance Analysis of Heuristic Search Using Parallel Hash Tables",
    Year = 1991,
}

@Article{Chernoff:52,
    Author = Chernoff,
    Title = "A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations",
    Year = 1952,
    Journal = "Annals of Math. Statistics",
    Volume = 23,
    Pages = "493-507",
}

@Article{Angluin:Valiant:79,
    Author = Angluin #&# Valiant,
    Title = "Fast Probabilistic Algorithms for Hamiltonian Paths and Matchings",
    Year = 1979,
    Journal = JCSS,
    Volume = 18,
    Pages = "155-193",
}

@InProceedings{Hagerup:Nowak:89,
    Ordinal = 92,
    Author = Hagerup #&# Nowak,
    Title = "Parallel Retrieval of Scattered Information",
    Year = 1989,
    BookTitle = icalp89,
    Pages = "439-450",
}

@InProceedings{Fich:I:K:K:K:93,
    Author = Fich #&# Impagliazzo #&# Russel #&# King #&# Kytylowski,
    Title = "Limits on the Power of Parallel Random Access Machines
        with Weak Forms of Write Conflict Resolution",
    Year = 1993,
    BookTitle = stacs93,
}

@InProceedings{Fich:K:L:K:R:92,
    Author = Fich #&# Kowaluk #&# Lyrys #&# Kutylowski #&# Ragde,
    Title = "Retrieval of scattered information by {EREW}, {CREW},
        and {CRCW} {PRAMs}",
    Year = 1992,
    BookTitle = swat92,
}

@InProceedings{Ragde:90,
    Ordinal = 94,
    Author = Ragde,
    Title = "The Parallel Simplicity of Compaction and Chaining",
    BookTitle = icalp90,
    Pages = {744-751},
    Year = 1990,
    Note1 = "To appear in {\em J. Algorithms}",
}

@Article{Ragde:93,
    Ordinal = 94,
    Author = Ragde,
    Title = "The Parallel Simplicity of Compaction and Chaining",
    Journal = jalg,
    Volume = 14,
    Pages = "371-380",
    Year =  1993,
}

@Article{Hagerup:Compaction:92,
    Author = Hagerup,
    Title = "On a Compaction Theorem of {R}agde",
    Journal = ipl,
    Volume = 43,
    Pages = "335-340",
    Month = oct,
    Year =  1992,
}

@InProceedings{Newman:Ragde:Wigderson:89,
    Ordinal = 59,
    Author = Newman #&# Ragde #&# Wigderson,
    Title = "Perfect Hashing, Graph Entropy, and Circuit Complexity",
    Year = 1989,
    BookTitle = "Proc. 5th IEEE Conference on Structure in Complexity Theory",
}

@Article{Galil:Giancarlo:88,
    Author = Galil #&# Giancarlo,
    Title = {Data Structures and Algorithms for Approximate String Matching},
    Year = 1988,
    Journal = jcmplx,
    Volume = 4,
    Pages = {33-72},
}

@Article{Apostolico:i:l:s:Vishkin:88,
    Ordinal = 237,
    Author = Apostolico #&# Iliopoulos #&# Landau #&# Schieber #&# Vishkin,
    Title = {Parallel Construction of a Suffix Tree},
    Year = 1988,
    Journal = Algorithmica,
    Volume = 3,
    Pages = {347-365},
}

@TechReport{Landau:Schieber:Vishkin:86,
    Author = Landau #&# Schieber #&# Vishkin,
    Title = {Parallel Construction of a Suffix Tree},
    Year = 1986,
    Number = {TR-53/86},
    Institution = {Department of Computer Science, Tel Aviv University},
    Note = {and also Proceedings of the 14th ICALP, Lecture notes in
Computer Science, Vol. 267, Springer-Verlag, Berlin, 1987, pp.
314-325},
}

@Article{Shiloach:Vishkin:82,
    Author = Shiloach #&# Vishkin,
    Title = {An ${O}(\log n)$ Parallel Connectivity Algorithm},
    Year = 1982,
    Journal = jalg,
    Volume = 3,
    Pages = {57-67},
}

@Article{Shiloach:Vishkin:82b,
    Author = Shiloach #&# Vishkin,
    Title = "An ${O}(n ^2 \log n)$ parallel {M}ax-{F}low algorithm",
    Year = 1982,
    Journal = jalg,
    Volume = 3,
    Pages = "128-146",
}

@Article{Shiloach:Vishkin:81,
    Author = Shiloach #&# Vishkin,
    Title = {Finding the Maximum, Merging, and Sorting in a Parallel
Computation Model},
    Year = 1981,
    Journal = jalg,
    Volume = 2,
    Pages = {88-102},
}

@Article{Brent:74,
    Author = Brent,
    Title = {The Parallel Evaluation of General Arithmetic Expressions},
    Year = 1974,
    Journal = jacm,
    Volume = 21,
    Pages = "201-208",
}

@Article{Brent:72,
    Author = Brent,
    Title = "Reducing the retrieval time of scatter storage techniques",
    Year = 1972,
    Month = Feb,
    Journal = cacm,
    Volume = 16,
    Number = 2,
    Pages = "105-109",
}

@InCollection{Apostolico:84,
    Author = Apostolico,
    Title = "The Myriad Virtues of Subword Trees",
    Year = 1984,
    BookTitle = "Combinatorial Algorithms on Words",
    Pages = {85-96},
    Editor = Apostolico #&# Galil,
    Publisher = sv,
    inote = "NATO ASI Series F, Vol. 12",
}

@InProceedings{Kruskal:Rudolph:Snir:88:CONF,
    Ordinal = 58,
    Author = Kruskal #&# Rudolph #&# Snir,
    Title = { A Complexity Theory of Efficient Parallel Algorithms},
    Year = 1988,
    BookTitle = icalp88,
    Pages = {333-346},
}

@Article{Kruskal:Rudolph:Snir:90,
    Ordinal = "58a",
    Author = Kruskal #&# Rudolph #&# Snir,
    Title = "A Complexity Theory of Efficient Parallel Algorithms",
    Year = 1990,
    Journal = tcs,
    Volume = 71,
    Pages = "95-132",
}

@TechReport{Bhatt:d:h:p:r:s:TR:89,
    Author = "P. C.P. Bhatt" #&# Diks #&# Hagerup #&# "V. C. Prasad" #&# Radzik #&# Saxena,
    Title = "Improved Deterministic Parallel Integer Sorting",
    Year = 1989,
    Month = Nov,
    Number = "15/1989",
    Institution = saarlandes,
}

@Article{Bhatt:d:h:p:r:s:91,
    Author = "P. C.P. Bhatt" #&# Diks #&# Hagerup #&# "V. C. Prasad" #&# Radzik #&# Saxena,
    Title = "Improved Deterministic Parallel Integer Sorting",
    Journal = infocomp,
    Year = 1991,
    Month = Nov,
    Volume = 94,
    Pages =  "29-47",
}

@Unpublished{Gil:Matias:93,
    Author = Gil #&# Matias,
    Title = "Fast Parallel Hashing",
    Year = 1992,
    Note = "Manuscript",
}

@UnPublished{Bern:k-r:s-89,
    Author = Bern #&# Karloff #&# Raghavan #&# Schieber,
    Title = "Fast Geometric Approximation Techniques and Geometric Embedding Problems",
    Year = 1989,
    Note = "Manuscript",
}

@UnPublished{Hagerup:Self:90,
    Ordinal = 52,
    Author = Hagerup,
    Title = "Self-Simulation on the {PRAM}",
    Year = 1990,
    Month = Oct,
    Note = "Manuscript",
}

@Article{Illingworth:Kittler:88,
    Author = Illingworth #&# Kittler,
    Title = {A Survey of the {H}ough Transform},
    Year = 1988,
    Journal = {Computer Vision, Graphics, and Image Processing},
    Volume = 44,
    Pages = {87-116},
}

@Article{Matias:Vishkin:JALG:91,
    Author = Matias #&# Vishkin,
    Title = "On Parallel Hashing and Integer Sorting",
    Year = 1991,
    Journal = jalg,
    Volume = 12,
    Number = 4,
    Pages = {573-606},
}

%   CrossRef = "ICALP90",
@InProceedings{Matias:Vishkin:90D,
    Author = Matias #&# Vishkin,
    Title = "On Parallel Hashing and Integer Sorting",
    BookTitle = icalp90,
    Year = 1990,
    Pages = {729-743},
    Note = "Also in TR-158/89, Eskenasy Inst. of Comp. Sci., Tel-Aviv Univ. Israel, Dec. 1989",
}

%   CrossRef = "ICALP90",
@InProceedings{Matias:Vishkin:ICALP:90,
    Author = Matias #&# Vishkin,
    Title = "On Parallel Hashing and Integer Sorting",
    BookTitle = icalp90,
    Year = 1990,
    Pages = {729-743},
}

@Misc{Vishkin:89,
    Ordinal = 83,
    Author = Vishkin,
    Title = "Research on Parallel Algorithms",
    Year = 1990,
    HowPublished = "UMIACS 1989 Annual Report",
}

@TechReport{Matias:Vishkin:89:TA,
    Author = Matias #&# Vishkin,
    Title = "On Parallel Hashing and Integer Sorting",
    Year = 1989,
    Month = Dec,
    Number = "158/89",
    Institution = Eskenasy,
    COMMENT = "Also in UMIACS-TR-90-13, Inst. for Advanced Computer Studies, Univ. of Maryland, Jan. 1990",
}

@TechReport{Matias:Vishkin:90:Maryland,
    Ordinal = 27,
    Author = Matias #&# Vishkin,
    Title = "On Parallel Hashing and Integer Sorting",
    Year = 1990,
    Month = Jan,
    Number = "UMIACS-TR-90-13",
    Institution = {Inst. for Advanced Computer Studies, University of
Maryland},
    Note = "Also in TR-158/89, Eskenasy Inst. of Computer Sciences, Tel-Aviv University, Dec. 1989",
}

@InProceedings{Beame:86,
    Author = Beame,
    Title = {Limits on the Power of Concurrent-Write Parallel Machines},
    Year = 1986,
    BookTitle = stoc86,
    Pages = {169-176},
}

@Article{Karp:Upfal:Wigderson:88,
    Ordinal = 79,
    Author = Karp #&# Upfal #&# Wigderson,
    Title = {The Complexity of Parallel Search},
    Year = 1988,
    Month = Apr,
    Journal = jcss,
    Volume = 36,
    Number = 2,
    Pages = {225-253},
}

%   CrossRef = "STOC90",
@InProceedings{Vishkin:90,
    Author = Vishkin,
    Title = {Deterministic Sampling---A New Technique for Fast Pattern Matching},
    BookTitle = stoc90,
    Year = 1990,
    Note1 = {Also to appear in SIAM J. Computing},
}

@InProceedings{Boppana:89,
    Author = Boppana,
    Title = "Optimal Separations Between Concurrent-Write Parallel Machines",
    Year = 1989,
    BookTitle = stoc89,
    Pages = "320-326",
}

@Article{Goldschlager:82,
    Author = Goldschlager,
    Title = "A Universal Interconnection Pattern for Parallel Computers",
    Year = 1982,
    Month = Jul,
    Journal = jacm,
    Volume = 29,
    Number = 4,
    Pages = "1073-1086",
}

@Book{Hofri:Book,
    Author = Hofri,
    Title = "Probabilistic Analysis of Algorithms",
    Year = 1987,
    Publisher = "Springer-Verlag New York Inc.",
}

@Article{Gonnet:Munro:84,
    Author = Gonnet #&# Munro,
    Title = "The Analysis of Linear Probing Sort by the Use of a New Mathematical Transform",
    Year = 1984,
    Journal = JALG,
    Volume = 5,
    Pages = "451-470",
}

@Article{Larson:83,
    Author = Larson,
    Title = "Analysis of Uniform Hashing",
    Year = 1983,
    Journal = jacm,
    Volume = 30,
    Pages = "805-819",
}

@Article{Mendelson:Yechiali:80,
    Author = Mendelson #&# Yechiali,
    Title = "A New Approach to the Analysis of Linear Hashing",
    Year = 1980,
    Journal = jacm,
    Volume = 27,
    Pages = "474-483",
}

@Article{Knuth:74,
    Author = Knuth,
    Title = "Computer Science and its Relationship to Mathematics",
    Year = 1974,
    Journal = "Am.\ Math.\ Monthly",
    Volume = 8,
    Pages = "323-343",
}

@InProceedings{Gonnet:Munro:77,
    Author = Gonnet #&# Munro,
    Title = "The Analysis of an Improved Hashing Technique",
    Year = 1977,
    BookTitle = stoc77,
    Pages = "113-121",
    Loacation = "Boulder, Colorado",
}

@Article{Gonnet:Munro:79,
    Author = Gonnet #&# Munro,
    Title = "Efficient Ordering of Hash Tables",
    Year = 1979,
    Month = Aug,
    Journal = sicomp,
    Volume = 8,
    Number = 3,
    Pages = "544-555",
}

@Conference{Sipser:83,
    Ordinal = 84,
    Author = Sipser,
    Title = "A Complexity Theoretic Approach to Randomness",
    Year = 1983,
    Month = Apr,
    BookTitle = stoc83,
    Pages = "330-335",
}

@Conference{Stockmeyer:83,
    Author = Stockmeyer,
    Title = "The Complexity of Approximate Counting",
    Year = 1983,
    Month = Apr,
    BookTitle = stoc83,
    Pages = {118-126},
}

@Article{Hagerup:Rub:90,
    Ordinal = 48,
    Author = Hagerup #&# Rub,
    Title = "A Guided Tour of Chernoff Bounds ",
    Year = "1989/90",
    Journal = ipl,
    Volume = 33,
    Pages = "305-308",
}

@Book{Kolchin:Sevastyanov:Chistyakov:78,
    Author = Kolchin #&# Sevastyanov #&# Chistyakov,
    Title = "Random Allocations",
    Year = 1978,
    Series = "Scripta Series in Mathematics",
    Publisher = "V. H. Winston \& Sons",
    Address = "1511 K St.\ N.W., Wasington, D.C.\ 2005",
}

@Article{Tarjan:Yao:79,
    Author = Tarjan #&# Yao,
    Title = "Storing a Sparse Table",
    Year = 1979,
    Month = Nov,
    Journal = cacm,
    Volume = 21,
    Pages = {606-611},
}

@InProceedings{Cook:83,
    Author = Cook,
    Title = "The Classification of Problems which have Fast Parallel Algorithms",
    Year = 1983,
    BookTitle = "Proc. 1983 Intern. FCT Conf. 158",
    Pages = "78-93",
    Publisher = sv,
}

@TechReport{Gil:Matias:91:UMIACS,
    Ordinal = 77,
    Author = Gil #&# Matias,
    Title = "Fast Hashing on a {PRAM}---Designing by Expectation",
    Year = 1991,
    Month = Apr,
    Number = "UMIACS-TR-91-64 CS-TR-2667",
    Institution = UMIACS,
}

@Article{Gil:Matias:94:IPL,
    Ordinal = 220,
    Author = Gil #&# Matias,
    Title = "Designing Algorithms by Expectations",
    Year = 1994,
    Journal = ipl,
    Volume = 51,
    Number = 1,
    Month1 = jul,
    Pages = "31-34",
}

@TechReport{Gil:Matias:91:UBC,
    Ordinal = 152,
    Author = Gil #&# Matias,
    Title = "Fast Hashing on a {PRAM}---Designing by Expectation",
    Year = 1991,
    Month = Jun,
    Number = "91-13",
    Institution = csubc,
}

%   CrossRef = "SODA91",
@InProceedings{Gil:Matias:91,
    Ordinal = 80,
    Author = Gil #&# Matias,
    Title = "Fast Hashing on a {PRAM}---Designing by Expectation",
    BookTitle = soda91,
    Year = 1991,
    Month = jan,
    Pages = "271-280",
}

@UnPublished{Gil:Matias:91a,
    Author = Gil #&# Matias,
    Title = "Fast Hashing on a {PRAM}",
    Year = 1991,
    Note = "Revised version",
}

@Article{Ragde:Steiger:Szemeredi:Wigderson:88,
    Ordinal = 25,
    Author = Ragde #&# Steiger #&# Szemeredi #&# Wigderson,
    Title = "The Parallel Complexity of Element Distinctness is {$\Omega(\sqrt{\log n})$}",
    Year = 1988,
    Month = Aug,
    Journal = siamjdisc,
    Volume = 1,
    Number = 3,
    Pages = {399-410},
    Keyword = {Simulations, emulations, lower bound, Element distinctness},
}

@UnPublished{Gil:Matias:90:old,
    Author = Gil #&# Matias,
    Title = "Fast and Efficient Simulations among {CRCW} Models",
    Year = 1990,
    Note = "In preparation",
}

@UnPublished{Gil:Matias:Vishkin:90,
    Author = Gil #&# Matias #&# Vishkin,
    Title = "A Fast Parallel Dictionary",
    Year = 1990,
    Note = "manuscript",
}

@UnPublished{Matias:Vishkin:90c,
    Author = Matias #&# Vishkin,
    Title = "Converting High Probability into Nearly-Constant Time---with Applications to Parallel Hashing",
    Year = 1990,
    Month = Nov,
    Note = "Extended Abstract (also in UMIACS-TR-91-65 CS-TR-2668 Uni. of Maryland",
}

@UnPublished{Gil:Matias:Polynomial:91,
    Author = Gil #&# Matias,
    Title = "Polynomial Hash Functions are Reliable",
    Year = 1991,
    Month = Aug,
    Note = "Manuscript",
}

@TechReport{Hagerup:Space:Allocation:91,
    Ordinal = 57,
    Author = Hagerup,
    Title = "Fast Parallel Space Allocation, Estimation and Integer Sorting",
    Year = 1991,
    Number = "03/91, SFB 124",
    Institution = saarlandes,
}

@UnPublished{Hagerup:Integer:Sorting:90,
    Ordinal = 53,
    Author = Hagerup,
    Title = "Constant-Time Parallel Integer Sorting",
    Year = 1990,
    Month = Nov,
    Note = "Manuscript",
}

%   CrossRef = "STOC91",
@InProceedings{Hagerup:Stoc:91,
    Author = Hagerup,
    Title = "Constant-Time Parallel Integer Sorting",
    BookTitle = stoc91,
    Year = 1991,
    Pages = "299-306",
}

@InProceedings{Albers:Hagerup:92,
    Ordinal = 210,
    Author = Albers #&# Hagerup,
    Title = "Improved Parallel Integer Sorting without Concurrent Writing",
    Year = 1992,
    Month = Jan,
    Pages = "463-472",
    BookTitle = soda92,
}

@Article{Gavril:75,
    Author = Gavril,
    Title = "Merging with Parallel Processors",
    Year = 1975,
    Month = Oct,
    Journal = cacm,
    Volume = 18,
    Number = 10,
    Pages = "588-591",
}

@InProceedings{Raman:90,
    Ordinal = 148,
    Author = Raman,
    Title = "The power of collision: Randomized parallel algorithms for chaining and integer sorting",
    Year = 1990,
    BookTitle = fsttcs90,
    Note = "Also in CS-TR-336, Univ. of Rochester, revised January 1991",
    Place = "Bangalore, India",
}

@InProceedings{Hagerup:icalp91,
    Ordinal = 56,
    Author = Hagerup,
    Title = "Fast Parallel Generation of Random Permutations",
    Year = 1991,
    BookTitle = icalp91,
    Pages = "405--416",
}

@UnPublished{Hagerup:manuscript:icalp91,
    Ordinal = 40,
    Author = Hagerup,
    Title = "Fast Parallel Generation of Random Permutations",
    Note = "Manuscript (Nov. 1990), also in ICALP '91, to appear",
    Year = 1991,
}

%Month = nov,
%Year = 1990,
@TechReport{Matias:Vishkin:91:Report,
    Ordinal = 76,
    Author = Matias #&# Vishkin,
    Title = "Converting High Probability into Nearly-Constant Time---with Applications to Parallel Hashing",
    Year = 1991,
    Month = Apr,
    Number = "UMIACS-TR-91-65, CS-TR-2668",
    Institution = umiacs,
}

%   CrossRef = "STOC91",
%   Note = "Also in UMIACS-TR-91-65, Inst. for Adv. Comp. Studies, Univ. of Maryland, April 1991",
@InProceedings{Matias:Vishkin:91,
    Author = Matias #&# Vishkin,
    Title = "Converting High Probability into Nearly-Constant Time---with Applications to Parallel Hashing",
    BookTitle = stoc91,
    Month = may,
    Year = 1991,
    Pages = "307-316",
    Note = "Also in UMIACS-TR-91-65, Institute for Advanced Computer Studies, Univ.\ of Maryland, April 1991",
}

%   CrossRef = "STOC91",
@InProceedings{Matias:Vishkin:91:stoc,
    Author = Matias #&# Vishkin,
    Title = "Converting High Probability into Nearly-Constant Time---with Applications to Parallel Hashing",
    BookTitle = stoc91,
    Pages = "307-316",
    Month = may,
    Year = 1991,
}

@InProceedings{Awerbuch:Shiloach:83,
    Author = Awerbuch #&# Shiloach,
    Title = "New Connectivity and {MSF} Algorithms for {U}ltracomputer and {PRAM}",
    Year = 1983,
    BookTitle = icpp83,
    Pages = "175-179",
}

@Book{Jaja:92,
    Author = Jaja,
    Title = "Introduction to Parallel Algorithms",
    Year = 1992,
    Publisher = aw,
}

@BOOK{Reif:93,
    EDITOR = Reif,
    TITLE = {A Synthesis of Parallel Algorithms},
    PUBLISHER = {Morgan-Kaufmann},
    YEAR = {1993},
    ADDRESS = {San Mateo, CA}
}

@Article{Valiant:75,
    Author = Valiant,
    Title = {Parallelism in Comparison Problems},
    Year = 1975,
    Journal = sicomp,
    Volume = 4,
    Pages = {348-355},
}

@Article{Kruskal:83,
    Author = Kruskal,
    Title = "Searching, merging, and sorting in parallel computation",
    Year = 1983,
    Journal = "IEEE Trans. on Comp",
    Volume = "C-32",
    Pages = "942-946",
}

%   CrossRef = "SODA91",
@InProceedings{MacKenzie:Stout:91,
    Author = MacKenzie #&# Stout,
    Title = "Ultra-Fast Expected Time Parallel Algorithms",
    BookTitle = soda91,
    Year = 1991,
    Pages = "414-423",
}

@TechReport{MacKenzie:Stout:91:Report,
    Ordinal = 151,
    Author = MacKenzie #&# Stout,
    Title = "Ultra-Fast Expected Time Parallel Algorithms",
    Year = 1991,
    Number = "115-91",
    Institution = eecsmichigan,
    Address = "Ann Arbor, Michigan 48109-2122, USA",
}

@InProceedings{Greenberg:Ladner:83,
    Author = Greenberg #&# Ladner,
    Title = "Estimating the multiplicity of conflicts in multiple access channels",
    Year = 1983,
    BookTitle = focs83,
    Pages = "384-392",
}

@Article{Greenberg:Flajolet:Ladner:87,
    Author = Greenberg #&# Flajolet #&# Ladner,
    Title = "Estimating the Multiplicity of Conflicts to Speed Their Resolution in Multiple Access Channels",
    Year = 1987,
    Journal = jacm,
    Volume = 34,
    Number = 2,
    Pages = "289-325",
}

@UnPublished{Gil:Matias:90a,
    Author = Gil #&# Matias,
    Title = "Leaders Election Without a Conflict Resolution Rule---Fast and Efficient Simulations among {CRCW} {PRAM}s",
    Year = 1990,
    Note = "Manuscript",
}

@UnPublished{Gil:Matias:90,
    Author = Gil #&# Matias,
    Title = "Fast and Efficient Simulations among {CRCW} Models",
    Year = 1990,
    Note = "Manuscript",
}

@UnPublished{Karp:89,
    Author = Karp,
    Title = "Probabilistic Analysis of Algorithms",
    Year = 1989,
    Note = "Class notes, Univ. California, Berkeley",
}

@Article{Goodrich:89,
    Author =  Goodrich,
    Title = "Triangulating a polygon in parallel",
    Journal= jalg,
    Volume= "10",
    Pages= "327-351",
    Year = "1989"
}


@InProceedings{Goodrich:91,
    Ordinal = 30,
    Author = Goodrich,
    Title = "Using Approximation Algorithms to Design Parallel Algorithms that May Ignore Processor Allocation",
    Year = 1991,
    BookTitle = focs91,
    Pages = "711-722",
}

@InProceedings{Raghavan:86,
    Ordinal = 176,
    Author = Raghavan,
    Title = "Probabilistic construction of deterministic algorithms: approximating packing integer programs",
    Year = 1986,
    BookTitle = focs86,
    Pages = "10-18",
}

@InProceedings{Miller:Reif:85,
    Ordinal = 133,
    Author = Miller #&# Reif,
    Title = "Parallel Tree Contraction and its Application",
    Year = 1985,
    BookTitle = focs85,
    Pages = "478-489",
}

@InProceedings{Hagerup:Radzik:90,
    Ordinal = 126,
    Author = Hagerup #&# Radzik,
    Title = "Every Robust {CRCW} {PRAM} Can Efficiently Simulate a {P}riority {PRAM}",
    Year = 1990,
    BookTitle = spaa90,
    Pages = {117-124},
}

@UnPublished{Borodin:Hopcroft:Paterson:Ruzzo:Tompa:80,
    Title = "Observations Concerning Synchronous Parallel Models of Computation",
    Author =  Borodin #&# Hopcroft #&# Paterson #&# Ruzzo #&# Tompa,
    Note = "Manuscript",
    Year = 1980
}

@PhdThesis{Gil:PhD:90,
    Author = Gil,
    Title = "Lower Bounds and Algorithms for Hashing and Parallel Processing",
    Year = 1990,
    Month = Nov,
    School = "The Hebrew University of Jerusalem",
    Address = "Givat Ram 91904, {J}erusalem, {I}srael",
}

@PhdThesis{Chaudhuri:PhD:91,
    Author = Chaudhuri,
    Title = "Lower Bounds for Parallel Computation",
    Year = 1991,
    School = "Rutgers University",
}

@InCollection{Rabin:76,
    Author = Rabin,
    Title = "Probabilistic Algorithms",
    Year = 1976,
    BookTitle = "Algorithms and Complexity: New Directions and Recent Results",
    Pages = {21--39},
    Editor = "J. F. Traub",
    Publisher = "Academic Press",
    Abstract = "Seminal paper advocating the use of randomized algorithms",
}

@Article{Grolmusz:Ragde:90,
    Ordinal = 1,
    Author = Grolmusz #&# Ragde,
    Title = "Incomparability in Parallel Computation",
    Year = 1990,
    Journal = dal,
    Volume = 29,
    Pages = {63--78},
    Keywords = {Simulations, Emulations},
    Abstract = {
        We consider the relative power of concurrent-write PRAMs when
        the number of processors (and input variables) is fixed at $n$,
        and infinite shared memory is allowed. Several different models
        (\Common{}, \Arbitrary{}, \Priority{}) have been used for
        algorithm design in the litreature; these models differ in
        their method of write conflict resolution. Recent work in
        separating the
        models~\cite{Fich:Ragde:Wigderson:84,li:yesha:86} has relied on
        further restrictions (limiting the size of memory or the power
        of processors); the only unrestricted results known concern the
        element distinctness
        problem~\cite{Fich:Meyer:Wigderson:86,Ragde:Steiger:Szemeredi:Wigderson:88}.
        In this paper we contribute further unrestricted results. We
        consider the \Collision{} model model, a natural generalization
        of the Ethernet~\cite{Greeberg:84}. Our main result is a lower
        bound of $\Omega(\log \log \log n)$ steps on \Collision{} for a
        problem that can be done in $O(1)$ steps on \Arbitraray{}. We
        use this result, together with a reduction perofrmed by means
        of Ramsey's theorem, to sho show that the powers of \Common{}
        and \Collision{} are incomparable. We also introduce a new and
        natural model, \Cancellation, and show that it is strictly less
        powerul than \Collision{} and incomparable with \Common{}. The
        proofs involved use combinatorial arguments, including
        Tur\'an's theorem for graphs and Erd\H{o}s-Rado intersecting
        set theorem.
    },
}

%
%
%
@InProceedings{Grolmusz:Ragde:87,
    Ordinal = 26,
    Author = Grolmusz #&# Ragde,
    Title = "Incomparability in Parallel Computation",
    Year = 1987,
    BookTitle = focs87,
    Pages = "89-98",
}

@InProceedings{Edmonds:91,
    Author = "J. Edmonds",
    Title = "Lower Bounds with Smaller Domain Size on Concurrent Write
        Parallel Machines",
    Year = 1991,
    BookTitle = "Proc. 6th Annual IEEE Conference on Structure in
        Complexity Theory",
}

@Article{Erdos:Rado:60,
    Author = " P. Erd\H{o}s and R. Rado",
    Title = {Intersection Theorems for Systems of Sets},
    Year = 1960,
    Journal = "J. London Math. Soc.",
    Volume = 35,
    Pages = "85--90",
}

@Article{Erdos:Tetali:90,
    Author = Erdos #&# Tetali,
    Title = {Representations of Integers as the Sum of $k$ Terms},
    Year = 1990,
    Journal = "Random Structures and Algorithms",
    Volume = 1,
    Pages = "245--261",
}

@Article{Erdos:Renyi:60,
    Author = Erdos #&# Renyi,
    Title = {On the Evolution of Random Graphs},
    Year = 1960,
    Journal = "Magyar. Tud. Akad. Mat. Kut. Int. K\H{o}zl.",
    Volume = 5,
    Pages = "17--61",
}

@InCollection{Erdos:Lovasz:75,
    Author = Erdos #&# Lovasz,
    Title = {Problems and Results on 3-Chromatic Hypergraphs and Some
        Related Questions},
    Year = 1975,
    BookTitle = "Infinite and Finite Sets",
    Editor = "A. Hajnal et al",
    Publisher = nh,
    Pages = "609--628",
}

@InCollection{Janson:Luczak:Rucinski:90,
    Author = Janson #&# Luczak #&# Rucinski,
    Title = {An Exponential Bound for the Probability of Nonexistence
        of a Specified Subgraph in a Random Graph},
    Year = 1990,
    BookTitle = {Random Graphs'87},
    Editor = "Karonski et al",
    Publisher = "John Wiley & Sons Ltd",
    Place = "Chichester",
    Pages = "73--87",
}

@Article{Ramsey:30,
    Author = "F.P. Ramsey",
    Title = {On A Problem of Formal Logic},
    Year = 1930,
    Journal = "Proc London Math. Soc.",
    Series = 2,
    Volume = 30,
    Pages = "264--286",
}


@Article{Winters:90,
    Ordinal = 3,
    Author = Winters,
    Title = {Minimal Perfect Hashing in Polynomial Time},
    Year = 1990,
    Journal = BIT,
    Volume = 30,
    Number = 2,
    Pages = "235--244",
    Abstract = {
        We present a universally applicable algorithm for generating
        minimal perfect hash functions. The method has (worst case)
        polynomial time complexity in units of bit operations. An
        adjunct algorithm for reducing parameter magnitudes in the
        generated hash functions is given. The probabilistic method
        makes hash functions parameter magnitutdes independent of
        argument (input keys) magnitudes.
    },
    Idea = "Use Chineese remainder theorem",
}

@Article{Berman:et:al:86,
    Ordinal = 4,
    Author = Berman #&# Bock #&# Dittert #&# ODonnel #&# Plank,
    Title = "Collections of Functions for Perfect Hashing",
    Year = 1986,
    Journal = sicomp,
    Volume = 15,
    Number = 2,
    Pages = "604--618",
    Abstract = {
        Hashing techniques for accessing a table without searching it
        are usually designed to perform efficiently on the average over
        all possible contents of the table. If the table contents are
        known in advance, we might be able to choose a hashing function
        with guaranteed efficient (worst-case) performance. Such a
        technique has been called `perfect hashing' by Sprugnoli and
        others. In this paper, we address the question of whether
        perfect hashing is feasible in principle as a general
        technique, or whether it must rely on special qualities of the
        contents of the table. We approach the question by counting the
        number of functions which must be searched to be sure of
        finding a perfect hashing function. We present upper and lower
        bounds on the size of this search space, with attention to the
        tradeoff between the size of the search space and the size of
        the hash table.
    },
}

@Article{Morrison:Shepp:Van-Wyk:87,
    Ordinal = 5,
    Author = Morrison #&# Shepp #&# Van-Wyk,
    Title = {A Queueing Analysis of Hashing with Lazy Deletion},
    Year = 1987,
    Journal = sicomp,
    Volume = 16,
    Number = 6,
    Pages = "1155--1164",
    Abstract = {
        Hashing with lazy deletion is a simple method for maintaining
        a dynamic dictionary: items are inserted and sought as usual in
        a separate-chaining hash table; however, items that no longer
        need to be in the data structure remain until a later insertion
        operation stumbles on them and removes them from the table.
        Because hashing with lazy deletion does not delete items as
        soon as possible, it keeps more items in the dictionary than
        methods that use more careful deletion strategies. On the other
        hand, its space overhead is much smaller than those more
        careful methods, so if the number of extra items is not too
        large, hashing with lazy deletion can be a practical algorithm
        when space is scarce. In this paper, we analyze the expected
        amount of excess space used by hashing with lazy deletion.
    },
    Review = {
        The Authors' analysis assumes that items arrive according to a
        time-homogeneous Poisson process and remain alive for an
        exponentially distributed duration, with all possible variables
        independent, thus giving rise to an $M/M/\infty$ queueing
        system. For this system they identify the following variables
        with operationally meaningful quantities: (1) the maximum
        number of customers in the system, under the limiting state
        distribution, over a given finite period, and (2) the joint
        distribution of the number in service and number of departures
        between successive arrivals. Recurrence equations for these
        are reduced (?) to expressions for them, in terms of the
        Charlier-Poisson polynomials. For a specific set of parameters
        the operational variables are estimated, and displayed in
        graphs. The analysis appears quite interesting and well done.
        Nevertheless, it leaves the following query unanswered: Since
        the analytical solution is quite opaque, and the required
        computations heavy (involving truncating the underlying
        distributions and calculating eigenvalues for large matrices),
        this reviewer wonders if a straightforward numerical solution
        by iteration of the recurrences would not have been at once
        faster and---at least for the person interested in the data
        structure, rather than the analysis---more illuminating. },
    Reviewer = {Hofri, Micha},
}

@Article{Mehlhorn:Naher:90,
    Ordinal = 100,
    Author = Mehlhorn #&# Naher,
    Title = "Bounded Ordered Dictionaries In ${O}(\log\log {N})$ Time and ${O}(n)$ Space",
    Year = 1990,
    Month = Aug,
    Journal = ipl,
    Volume = 35,
    Pages = "183-189",
}

@Article{Mehlhorn:Naher:Rauch:90,
    Ordinal = 6,
    Author = Mehlhorn #&# Naher #&# Rauch,
    Title = "On the Complexity of a Game Related to the Dictionary Problem",
    Year = 1990,
    Month = Oct,
    Journal = sicomp,
    Volume = 19,
    Number = 5,
    Pages = "902-906",
    Abstract = {
        A game on trees that is related to the dictionary problem is
        considered. There are two players, $A$ and $B$, which take
        turns. Player $A$ models the user of the dictionary and player
        $B$ models the implementation of it. At his turn, player $A$
        modifies the tree by adding new leaves and player $B$ modeifies
        the tree by replacing subtrees. The cost of an insertion is the
        depth of the new leaf and the cost of an update is the size of
        subtree replaced. The goal of player $A$ is to maximize cost
        and the goal of $B$ is to minimize it. It is shown that there
        is a strategy for player $A$, which forces a cost of $\Omega(n
        \log \log n)$ for an $n$-game, i.e., a game in which each
        player takes $n$ turns, and that there is a strategy for player
        $B$, which keeps that the cost within $O(n \log \log n)$.
    },
}

@Article{Schmidt:Siegel:90,
    Ordinal = 9,
    Author = Schmidt #&# Siegel,
    Title = {The Spatial Complexity of Oblivious $k$-probe Hash Functions},
    Year = 1990,
    Journal = sicomp,
    Volume = 19,
    Number = 5,
    Pages = "775--786",
    Abstract = {
        The problem of constructing a dense static hash-based lookup
        table $T$ for a set of $n$ elements belonging to a universe
        $U={0,1,2,\cdots,m-1}$ is considered. Nearly tight bounds on
        the spatial complexity of oblivious $O(1)$-probe hash functios,
        which are defined to depend solely on their search key
        argument, are provided. This establishes a significant gap
        between oblivious and nonoblivious search. In particular, the
        results include the following:
        \begin{itemize}
            \item A lower bound showing that oblivious $k$-probe hash
                functions require a program size of
                $\Omega((n/k^2)e^{-k} + \log \log m)$ bits, on average.
            \item A probabilistic construction of a family of
                oblivious $k$-probe hash functions that can be specified in
                $O(n e^{-k} + \log \log m)$ bits, which nearly matches the
                above lower bound.
            \item A variation of an explicit $O(1)$ time 1-probe (perfect)
                hash fucntion family that can be specified in
                $O(n + \log \log m)$ bits, which is tight to
                within a constant factor of the lower bound.
        \end{itemize}
    },
}

@Article{Pittel:Yu:88,
    Ordinal = 10,
    Author = Pittel #&# Yu,
    Title = "On Search Times for Early-insertion Coalesced Hashing",
    Year = 1988,
    Month = Jun,
    Journal = sicomp,
    Volume = 17,
    Number = 3,
    Pages = "492--503",
    Review = {
    The authors consider an early-insertion coalesced hashing algorithm,
    and analyze the search times. The algorithm, due to J. C. Vitter
    [Comm. ACM 25 (1982), no. 12, 911--926], was analyzed by W. C. Chen
    and Vitter [SIAM J. Comput. 12 (1983), no. 4, 667--676; MR 85g:68012]
    and by G. Knott~\cite{Knott:84}.
    In this note, the Authors obtain, for each key, the
    distribution of the length of the chain leading from the cell to
    which the key hashes to the actual location of the key. In addition,
    if $U\sb n$ is the maximum among all the $n$ chain lengths in a hash
    table of size $n/a$ holding $n$ keys (where $a\in(0,1]$ is constant),
    the Authors show that $U\sb n=\log\sb bn-2\log\sb b\log\sb b n+O\sb
    p(1)$, where $b=1/(1-e\sp {-a})$.
},
    Reviewer = {Devroye, Luc P.K},
}

@Article{Litwin:et:al:89,
    Ordinal = 11,
    Author = Litwin #&# Sagiv #&# Vidyasankar,
    Title = {Concurrency and Trie Hashing},
    Year = 1989,
    Journal = acta,
    Volume = 26,
    Number = 7,
    Pages = "597--614",
    Abstract = {
        Trie hashing (TH), defined by Litwin, is one of the fastest
        access methods for dynamic and ordered files. The hashing
        function is defined in terms of a trie, which is basically a
        binary tree where a character string is associated implicitly
        with each node. This string is compared with a prefix of the
        given key in the search process, and depending on the result
        either the left or the right child is chosen as the next node
        to visit. The leaf nodes point to buckets which contain the
        records. The buckets are on a disk, whereas the trie itself is
        in the core memory. In this paper we consider concurrent
        execution of the TH operations. In additon to the usual search,
        insertion and deletion operations, we also include range
        queries among the concurrent operations. Our algorithm locks
        only leaf nodes and at most two nodes need to be locked
        simultaneously by an operation regardless of the number of
        buckets being accessed. The modification required in the basic
        data structure in order to accommodate concurrent operations is
        very minor.
    },
}

@Article{Baeza-Yates:89,
    Ordinal = 12,
    Author = Baeza-Yates,
    Title = {Modeling Splits in File Structures},
    Year = 1989,
    Journal = acta,
    Volume = 26,
    Number = 4,
    Pages = "349--362",
    Review = {
    The author analyzes the expected storage utilization of various file
    structures for which bucket splits are used to handle the overflows.
    The first model is for B$\sp +$-trees. A formula is derived which
    shows the storage utilization in terms of the number of new buckets
    and the split fractions. The study also shows the effect of using
    partial expansions before splitting. A special case is when each
    bucket is split into two new buckets. In this case, the best storage
    utilization is $\ln 2$, which is obtained using balanced splits.
    However, using partial expansions, we can increase the storage
    utilization without having balanced splits. For example, with two
    expansions, for large buckets, it is possible to increase the storage
    utilization to over 76$\%$. The second model is the ideal hashing
    file which maintains a uniform probability of hitting a bucket. An
    upper bound on the storage utilization is obtained. The study shows
    that it cannot have a storage utilization larger than 73$\%$ if the
    hashing method does not allow overflow buckets. Again, storage
    utilization can be increased by using partial expansions to handle
    overflow buckets.
},
    Reviewer = {Tang,-Leh-Sheng; (Springfield, MA)},
}

@Article{Gonnet:Larson:88,
    Ordinal = 13,
    Author = Gonnet #&# Larson,
    Title = {External Hashing with Limited Internal Storage},
    Year = 1988,
    Journal = jacm,
    Volume = 35,
    Number = 1,
    Pages = "161--184",
    Abstract = {
        The following problem is studied How, and to what extent, can
        the retrieval speed of external hashing be improved by storing
        a small amount of extra information in internal storage?
        Several algorithms that guarantee retrieval in one access are
        developed and analyzed. In the first part of the paper, a
        restricted class of algorithms is studied, and a lower bound on
        the amount of extra storage is derived. An algorithm that
        achieves this bound, up to a constant difference, is also
        given. In the second part of the paper a number of restrictions
        are relaxed and several more practical algorithms are developed
        and analyzed. The last one, in particular, is very simple and
        efficient, allowing retrieval in one access using only a fixed
        number of bits of extra internal storage per bucket. The amount
        of extra internal storage depends on several factors, but it is
        typically very small: only a fraction of a bit per record
        stored. The cost of inserting a record is also analyzed and
        found to be low. Taking all factors into account, this
        algorithm is highly competitive for applications requiring very
        fast retrieval.
    },
}

@Article{Ullman:72,
    Author = Ullman,
    Title = "A Note on the Efficiency of Hashing Functions",
    Year = 1972,
    Month = Jul,
    Journal = jacm,
    Volume = 19,
    Number = 3,
    Pages = "569-575",
}


@Article{Yao:85,
    Ordinal = 14,
    Author = Yao,
    Title = "Uniform Hashing is Optimal",
    Year = 1985,
    Journal = jacm,
    Volume = 32,
    Number = 3,
    Pages = "687--693",
    Abstract = {
        ``J. D. Ullman conjectured~\cite{Ullman:72} that uniform
        hashing is optimal in its expected retrieval cost among all
        open-address hashing schemes. In this paper, we show that, for
        any open-address hashing scheme, the expected cost of
        retrieving a record from a large table that is
        $\alpha\text{-fraction}$ full is at least
        $(1/\alpha)\log(1/(1-\alpha)) +o(1)$. This proves Ullman's
        conjecture to be true in the asymptotic sense.''
    },
}

@Article{Pflug:Kessler:87,
    Ordinal = 16,
    Author = Pflug #&# Kessler,
    Title = "Linear Probing with a Nonuniform Address Distribution",
    Year = 1987,
    Journal = jacm,
    Volume = 34,
    Number = 2,
    Pages = "397--410",
    Review = {
    The Authors study a hashing algorithm with linear probing for
    nonuniformly distributed hash keys. The data are assumed to be i.i.d.
    with density $g$ on $[0,1]$, and an element hashes to the $i$th cell in
    the hash table if it falls into $((i-1)/ M,i/M]$, where $M$ is the size
    of the hash table. $n$ points are stored into the hash table, where
    $n=\alpha M$ for some fixed $\alpha\in (0,1)$. Let $L\sb n$ be the
    arithmetic mean of the expected lengths of all probe sequences leading
    to the $n$ entries in the table. Using properties of the empirical
    distribution function, the Authors show that under some regularity
    conditions on the density, $\lim\sb {n\to\infty} L\sb n=\int\sb 0\sp 1
    ((1-(\alpha-1)g(x))/(2-2\alpha g(x)))dx$. They also study a related
    result about the expected length of the probe sequence when an $(n+1)$st
    point is added to the hash table. Throughout, it is assumed that the
    density is bounded by $1/\alpha$. The authors do not consider what
    happens when this condition is violated.
},
}

@Article{Gonnet:81,
    Ordinal = 17,
    Author = Gonnet,
    Title = "Expected Length of the Longest Sequence in Hash Code Searching",
    Year = 1981,
    Journal = jacm,
    Volume = 28,
    Number = 2,
    Pages = "289--304",
    Abstract = {
        An investigation is made of the expected value of the maximum
        number of accesses needed to locate any element in a hashing
        file under various collision resoulution schemes. This differs
        from usual worst-case considerations which, for hashing, would
        be the largest sequence of accesses for the worst possible
        file. Asymptotic expressions of these expected values are found
        for full and partly full tables. For the open addressing shceme
        with a clustering-free model theese values are found to be
        $0.6315\ldots \times n$ for a full table and $\approx
        -\log_\alpha n$ for a partly full, where $n$ is the number of
        records, $m$ is the size of the table, and $\alpha = n/m$. For
        the open addressing scheme which reorders the insertions to
        minimize the worst case, the lower bounds $\ln n + 1.077
        \ldots$ and $\lceil -\alpha^{-1} \ln (1-\alpha) \rceil$ are
        found for fully and partly full tables, respectively. Finally,
        for the separate chaining (or direct chaining) method both
        expected values are found to be $\approx \Gamma^{-1}(n)$. These
        results show that for these schemes, the actual behaviour of
        the worst case in hashs tables is quite good on the average.
    },
}

@Article{Ramakrishna:89,
    Ordinal = 7,
    Author = Ramakrishna,
    Title = "Analysis of Random Probing Hashing",
    Year = 1989,
    Journal = ipl,
    Volume = 31,
    Number = 2,
    Pages = "83--90",
    Abstract = {
        Random probing and uniform haashing are theoretical models of
        hashing schemes based on open addressing such as double
        hashing. Larson provided an asymptotic analysis of random
        probing with mulit-record buckets. His analysis was based on
        Poission approximation to the binomial distribution. The
        problems of obtaining an exact model and analyzing finite
        random probing hashing was left open with the mention of the
        difficulties involved. We address these open problems in this
        paper. Also, the search performance of full hash tables is
        analyzed.
    },
}

@Article{Chen:Vitter:83,
    Author = Chen #&# Vitter,
    Title = "Analysis of Early-Insertion Standard Coalesced Hashing",
    Year = 1983,
    Journal = sicomp,
    Volume = 12,
    Number = 4,
    Pages = "667-676",
}

@Article{Chen:Vitter:84,
    Author = Chen #&# Vitter,
    Title = "Analysis of New Variants of Coalesced Hashing",
    Year = 1984,
    Journal = tods,
    Volume = 9,
    Number = 4,
    Pages = "616-645",
}

@Article{Vitter:Chen:85,
    Author = Vitter #&# Chen,
    Title = "Optimum Algorithms for a Model of Direct Chaning",
    Year = 1985,
    Journal = sicomp,
    Volume = 14,
    Number = 2,
    Pages = "490-499",
}

@Article{Chen:Vitter:86,
    Ordinal = 8,
    Author = Chen #&# Vitter,
    Title = "Deletion Algorithms for Coalesced Hashing",
    Year = 1986,
    Journal = computer,
    Volume = 29,
    Number = 5,
    Pages = "436--450",
    Abstract = {
        We peresent efficient algorithms for three variants of
        coalesced hashing---late insertion (LICH), early insertion
        (EICH), and varied insertion (VICH). Our approach is uniform
        in the sense that each deletion works simultaneously for all
        three variants, though the implementatioon details are of
        course different. Deletion algorithms for coalesced hashing
        when there is a cellar have not been studied previously in the
        literature; these algorithms are useful because coalesced
        hashing is most efficient when a cellar is utilised. First we
        present and analyse a deletion algorithm that preserves
        randomness---in that deleting a record is in some sense like
        never hasve inserted it. In particular, the formulas for the
        average search time after $N$ random insertions intermixed with
        $d$ random deletions are the same as the formulas forr the
        average search times after $N-d$ random insertions. This
        answers an open question in the literature. We then present
        two deletion algorithms that require fewer pointer fields per
        table slot; the latter one does not relocate records once
        inserted. These two algorithms do not preserve randomness, but
        simulations suggest that search times remain good after
        repeeated deletions and insertions.
    },
}

@InProceedings{Vitter:81,
    Ordinal = 60,
    Author = Vitter,
    Title = {Deletion Algorithms For Hashing That Preserve Randomness},
    Year = 1981,
    BookTitle = focs81,
    Pages = {127-132},
}

@Article{Vitter:82,
    Ordinal = "60a",
    Author = Vitter,
    Title = {Deletion Algorithms For Hashing That Preserve Randomness},
    Year = 1982,
    Journal = jalg,
    Volume = 3,
    Pages = "261-275",
}

@PhdThesis{Vitter:82:PhD,
    Author = Vitter,
    Title = "Analysis of Coalesced Hashing",
    Year = 1982,
    Month = Aug,
    School = "Stanford University",
    Address = "Stanford, CA",
    Note = "Technical Report STAN-CS-80-817",
}

@Article{Vitter:83,
    Author = Vitter,
    Title = "Analysis of the Search Performance of Coalesced Hashing",
    Year = 1983,
    Journal = jacm,
    Volume = 30,
    Pages = "231-258",
}

@Article{Ouksel:Scheuermann:88,
    Ordinal = 18,
    Author = Ouksel #&# Scheuermann,
    Title = "Implicit Data Structures for Linear Hashing Schemes",
    Year = 1988,
    Journal = ipl,
    Volume = 29,
    Number = 4,
    Pages = "183--189",
    Summary = {
We introduce two implicit data structures, the linear
binary trie and the linear binary search (LBS) tree, and show that they can be
used to represent the growth and search processes of file structures
constructed using different variants of linear hashing schemes. In particular,
we show that the LBS tree corresponds to an order-preserving variant of linear
hashing that organizes the specific set of records stored, without a priori
knowledge of the bounds of the key values. We use these results in a companion
paper [``Performance evaluation of grid-like, multidimensional file
structures'', submitted] to define a new multidimensional, order-preserving,
dynamic file structure in which LBS trees are used to represent the axial
directories.},
}

@Article{Gori:Soda:89,
    Ordinal = 20,
    Author = Gori #&# Soda,
    Title = "An Algebraic Approach to Cichelli's Perfect Hashing",
    Year = 1989,
    Journal = bit,
    Volume = 29,
    Number = 1,
    Pages = "2--13",
    Abstract = {
        The aim of this paper is to describe a new approach to
        building and perfect hash functions for a predefined set of
        keys. Several papers have dealt with this problem and proposed
        various kinds of functions [e.g., R. J. Cichelli, Comm.\ ACM
        23 (1980), no. 1, 17--19]. This study is based on a function
        whose address depends both on the letter codes and the letter
        position in the key, and therefore represents an extension of
        Cichelli's function. The weights associated with the position
        are considered to be fixed, and letter code computing is
        considered to be an interpolation problem. As a result, hash
        building requires only the solution of a linear algebraic
        system and the time complexity is polynomial $(O(n\sp 3))$. A
        number of clarifying examples are included in the paper.
    },
    Reviewer = "Paredaens, J.",
}

@Article{Knott:84,
    Author = Knott,
    Title = "Direct Chaining with Coalescing Lists",
    Year = 1984,
    Journal = jalg,
    Volume = 4,
    Number = 1,
    Pages = "7-21",
}

@Article{Knott:88,
    Ordinal = 21,
    Author = Knott,
    Title = "Linear Open Addressing and {P}eterson's Theorem Rehashed",
    Year = 1988,
    Journal = bit,
    Volume = 28,
    Number = 2,
    Pages = "364--371",
    Introduction = {Linear open addressing is a venerable hashing
collision resolution method which exhibits primary clustering when items are
stored. Linear open addressing is a 1-successor method as defined herein, but
such methods do not exhaust the class of primary clustering methods. Being a
primary clustering method does not, therefore, characterize linear open
addressing. Linear open addressing is shown here to be characterized, however,
by a description due to W. W. Peterson [IBM J. Res. Develop. 1 (1957),
130--146; MR 19, 69] that the expected retrieval cost is independent of the
order in which items arrive to be stored.''},
}

@Article{Knott:DeLaTorre:89,
    Ordinal = 22,
    Author = Knott #&# DeLaTorre,
    Title = "Hash Table Collision Resolution with Direct Chaining",
    Year = 1989,
    Journal = jalg,
    Volume = 10,
    Number = 1,
    Pages = "20--34",
    Abstract = {
        hash table method called direct chaining, wherein of items
        with the same hash function value are kept in a single table
        without recourse to an index table or a separate overflow area,
        is described. An explicitly linked free-space list is used
        which allows arbitrary insertion and deletion sequences to be
        done indefinitely with no performance degradation. When a
        singly linked free-space list is employed, the interaction of
        stored items appearing embedded in the free-space list and in
        the chains of overflow items leads to an intricate situation
        when we count the expected number of probes to distinct cells
        in the hash table made while inserting a new item. This
        difficulty is explored, and an exact analysis is carried out.
    },
}

@Article{XX:53,
    Author = {Pittel,-B., (1-OHS)},
    Title = {On probabilistic analysis of a coalesced hashing algorithm.},
    Year = 1987,
    Journal = annal-prob,
    Volume = 15,
    Number = 3,
    Pages = "1180--1202",
    Institution = {(1-OHS), Department of Mathematics, Ohio State University,
Columbus, Ohio 43210},
    Abstract = {
        The following hashing algorithm is studied for allocating $n$
        balls to $m\ge n$ cells, with at most one ball per cell. A ball
        $x$ goes into cell $h(x)$, where $h\:\{1,\cdots, n\}\to
        \{1,\cdots,m\}$ is random. If cell $h(x)$ is already occupied,
        the ball $x$ is rejected and moved into the leftmost empty
        cell. This empty cell is found via sequential search from left
        to right starting with the cell occupied by the previous
        rejected ball. Let $N(x)$ be the number of probes to allocate
        $x$. In the end, due to a resulting system of references, the
        $n$ occupied cells form a disjoint union of ordered chains, and
        to locate a ball $x$, it suffices to search only the cells of a
        subchain originating at the cell $h(x)$. Let $L(x)$ be the
        length of this subchain. The author proves that, in
        probability, $\max\sb xN(x)=\log\sb b n-2\log\sb b\log n+O(1)$
        and $\max\sb xL(x)=\log\sb b n-\log\sb b\log n+O(1)$ as
        $n\to\infty$, if $n/m$ is bounded away from zero, and
        $b=1/(1-e\sp {-n/m})$.
    },
    Reviewer = {Devroye,-Luc-P.; (3-CONC-C)},
    MathRN = {88j 68024},
}

@Article{Pittel:87,
    Ordinal = 23,
    Author = Pittel,
    Title = "Linear Probing the Probable Largest Search Time Grows Logarithmically with the Number of Records",
    Year = 1987,
    Journal = jalg,
    Volume = 8,
    Number = 2,
    Pages = "236--249",
    Review = {
The author studies the worst-case performance of a linear probing
hashing scheme under the assumption that the ratio $a=n/m$ is bounded away from
zero and one as $n,m\to\infty$, where $m$ is the number of locations, and $n$
is the number of records. He shows that the length of the longest probe
sequence grows in probability as $\log m/(a-1-\log a)$.},
    Reviewer = "Devroye, Luc PK",
    Comment = {
It may be surprising that the performance of hash table depends, for
fixed density, on the table size.
Note, however, that it is easy to obtain a close approximate result
just by examining $m /\log m$ blocks of size $m /\log m$ cells each.
},
}

@Article{Overmars:88,
    Ordinal = 24,
    Author = Overmars,
    Title = "Efficient Data Structures for Range Searching on a Grid",
    Year = 1988,
    Journal = jalg,
    Volume = 9,
    Number = 2,
    Pages = "254--275",
    Review = {The paper under review studies the two-dimensional range
searching problem in the special situation where all points lie on an integer
grid of size $U\times U$. There are problems in computational geometry where
the additional assumption that all data points lie on a grid can be exploited
to obtain faster algorithms than in the general situation. The author gives an
algorithm based on perfect hashing for range searching with query time
$O(k+\log\log U)$ where $k$ is the number of reported answers. Unfortunately,
the precomputation time is $O(U\sp 3\log U)$. Therefore an alternative solution
is presented with query time $O(k+\sqrt{\log U})$ but preprocessing time
$O(n\sqrt{\log U})$. Generalizations to higher-dimensional range searching
problems as well as an application to the line-segment intersection problem on
a grid are discussed at the end. The line segments are required to be
horizontal and have endpoints in $U\sp 2$. One can then find the segments that
intersect a vertical query line in $O(k+\log\log U)$ time, where again $k$ is
the number of reported segments.},
    Reviewer = "Sutner, Klaus",
}

@InProceedings{MacKenzie:92,
    Ordinal = 39,
    Author = MacKenzie,
    Title = "Load Balancing Requires {$\Omega(\log^* n)$} Expected Time",
    Year = 1992,
    Month = Jan,
    Pages = "94-99",
    BookTitle = soda92,
}

@Article{Poblete:Munro:89,
    Ordinal = 38,
    Author = Poblete #&# Munro,
    Title = "Last-Come-First-Served Hashing",
    Year = 1989,
    Journal = jalg,
    Volume = 10,
    Number = 2,
    Pages = "228--248",
    Abstract = {
        We introduce a new heuristic for resolving collisions in open
        addressing hash tables, called last-come-first-served hashing.
        The analysis shows that its expected search time is the same as
        that of the standard method, but its variance is much smaller.
        This makes the search algorithm much more reliable, and it may
        also be used to conduct a mode-centered search, further
        decreasing the search time.
    },
}

@Article{Chang:Chang:88,
    Ordinal = 41,
    Author = "Chang, C. C." #&# "Chang, C.H.K",
    Title = "An Ordered Minimal Perfect Hashing Scheme with Single Parameter",
    Year = 1988,
    Month = Feb,
    Journal = ipl,
    Volume = 27,
    Number = 2,
    Pages = "79--83",
    Abstract = {
        This paper proposes a new ordered minimal perfect hashing
        scheme with only one parameter. By applying our hashing
        function, all keys can be stored in ascending order. There is
        one very straightforward formula to compute the only parameter
        $C$, that requires $O(n \log_2 k_n)$ time, where $n$ is the
        total number of keys and $k_n$ is the key with maximum
        magnitude.
    },
}

@Article{Korner:Marton:88,
    Ordinal = 74,
    Author = Korner #&# Marton,
    Title = "New Bounds for Perfect Hashing via Information Theory",
    Year = 1988,
    Journal = "Europ. J. Combinatorics",
    Volume = 9,
    Pages = "523-530",
}

@Article{Korner:86,
    Ordinal = 42,
    Author = Korner,
    Title = "Fredman-{\Komlos} bounds and Information Theory",
    Year = 1986,
    Month = Oct,
    Journal = siamjadm,
    Volume = 7,
    Number = 4,
    Pages = "560--570",
    Review = {M. L. Fredman and J. Komlos [same journal 5 (1984),
no. 1, 61--68] have applied an interesting information-theoretic
lemma to two problems in combinatorics. They have derived good lower bounds on
the minimum size of a family of partitions of an $n$-element set into at most
$b$ classes such that all the subsets (respectively, pairs of subsets) of a
certain kind are `separated' by at least one partition in the family.
``Our aim is to show that the Fredman-Komlos lemma is a special case of a
simple inequality between entropies of graphs. The general inequality enables
us to handle more problems on separating partition systems'' (e.g.\ coloring).
``Part of the problems relate to hashing.'' An upper and a lower bound for the
minimum size of any family of nearly-perfect hash functions are derived.},
    Reviewer = "Ludde, Eberhard",
}

@Article{Fredman:Komlos:84,
    Ordinal = 43,
    Author = Fredman #&# Komlos,
    Title = "On the Size of Separating Systems and Families of Perfect Hash Functions",
    Year = 1984,
    Month = Mar,
    Journal = siamjadm,
    Volume = 5,
    Number = 1,
    Pages = "61-68",
    Keywords = "Perfect Hashing",
}

@Article{Rivest:78,
    Ordinal = 45,
    Author = Rivest,
    Title = "Optimal Arrangment of Keys in a Hash Table",
    Year = 1978,
    Month = Apr,
    Journal = jacm,
    Volume = 25,
    Number = 2,
    Pages = "200-209",
    Abstract = {
        When open addresssing is used to resolve collisions in a hash
        table, a given set of keys may be arranged in many ways;
        typically this depends on the order of in which the keys are
        inserted. It is shown that arrangements minimizing either the
        average or worst-case number of probes required to retrieve any
        key in the table can be found using an algorithm for the
        assignment problem. The worst-case retrieval time can be
        reduced to $O(\log_2(M))$ with probability $1 - \epsilon(M)$
        when storing $M$ keys in a table of size $M$, where
        $\epsilon(M) \rightarrow 0$ as $M \rightarrow \infty$. We also
        examine insertion algorithms to see how to apply these ideas
        for a dynamically changing set of keys.
    },
}

@Article{Babai:Moran:89,
    Author = Babai #&# Moran,
    Title = {Proving Properties of Interactive Proofs by a Generalized Counting Technique},
    Year = 1989,
    Journal = infocomp,
    Volume = 82,
    Number = 2,
    Pages = "185--197",
    Review = {A language $L$ admits an interactive proof if when $x\in L$ then
an all-powerful prover can convince a probabilistic polynomial-time verifier
that indeed $x\in L$. The prover convinces the verifier by a sequence of
message exchanges.
The authors study two properties of interactive proofs, namely: ``How many
message exchanges are needed?'', and ``Does the verifier have to send more
complicated messages than just the result of some random coin flips?'' The
weaker model where the verifier sends only random coin flips and then in the
end does a polynomial time computation to check whether he is convinced is
called an Arthur-Merlin game. It was previously known that it is always
possible to decrease the number of message exchanges by an arbitrary constant
factor [the authors, J. Comput. System Sci. 36 (1988), no. 2, 254--276; MR
90b:68028] and that it is always possible to convert an interactive proof to an
Arthur-Merlin game without essentially changing the number of message exchanges
[S. Goldwasser and M. Sipser, in 18th Annual Symposium on Theory of Computing
(Berkeley, CA, 1986), 59--68, ACM, New York, 1986]. The authors now combine
these two results in a single proof.
The outline of the proof is that the prover tries to convince the verifier that
there is a large regular tree of accepting conversations. By joint forces the
prover and the verifier walk down this tree four levels for each message
exchange. The counting gets slightly involved but the main tool for convincing
the verifier of the size of the tree is the use of universal hashing functions.
The proof uses clever counting arguments, but no major new techniques.},
    Reviewer = "Hastad, Johan",
}

@Article{Babai:Moran:88,
    Author = Babai #&# Moran,
    Title = {Arthur-Merlin Games, a Randomized Proof System, and a Hierarchy of
Complexity Classes},
    Year = 1988,
    Journal = jcss,
    Volume = 36,
    Number = 2,
    Pages = "254--276",
    Note = {17th Annual ACM Symposium on the Theory of Computing (Providence,
RI, 1985).},
    Review = {One of the most interesting questions in the philosophy of
science is: What is a proof? The reviewer does not claim to be in a position to
give references to the philosophical answers or discussions, but certainly
Section 1.1 of the paper under review is interesting to read. It is not long,
and it is instructive to compare it with the arguments in a paper by R. A.
DeMillo, R. J. Lipton and A. J. Perlis [Comm. ACM 22 (1977), no. 5, 271--280].
The main point in this part of the introduction is that a proof is an
interactive process by which a prover tries to convince another party of the
truth of a given statement. Then this idea is followed up to define complexity
classes.
Indeed, certain complexity classes capture the idea of ``proof'' at a certain
degree of abstraction; for instance, NP can be defined as the class of sets
such that a computationally powerful prover is able to prove to a polynomial
time verifier that a given string belongs to the set. Other analogies can be
drawn for P and PSPACE. A second ingredient that sometimes appears in
complexity classes is randomization: proofs are based on statistical evidence.
For instance, there are known, computationally feasible processes that prove
that, with overwhelming probability, a given number is a prime.
Now it is clear that it must be possible to integrate in complexity classes the
ingredient of interaction as well. This paper presents one such attempt (other
approaches exist; see the references of the paper under review). In an
Arthur-Merlin game, Merlin tries to convince King Arthur that some property
holds for certain given data, i.e., that a given string belongs to a certain
language. Merlin is magically able to find at every moment his best argument;
Arthur is not biased and just chooses his arguments at random. The game must
last for only a polynomial time, and it is required that either the fact to be
proven is true, and then Merlin has a high probability of convincing Arthur of
it, or it is false, and then he must be extremely lucky to cheat Arthur by
convincing him. This yields definitions of some very interesting complexity
classes, in which both randomization and interaction are present in the proof
process.
The paper explains the results thrice, at different depths. Thus, it is
difficult not to understand it. An abstract quite longer than common reviews
the results. Then an introduction several pages long presents very clearly the
motivations, the intuitive definitions, the relationships with other similar
concepts, and the results obtained and their significance, discussing many
issues and including some open problems. In the remaining part of the paper,
formal definitions and careful arguments proving the results are presented.
This part may be somewhat harder to read, depending on the reader's background
in probability theory. However, the ideas of the proofs can be clearly
understood.
It is shown that the probability of Arthur finishing in error (the
``uncertainty'' of the game) can be made as small as desired by ``playing the
game on many boards'', since the probability that Merlin is lucky once may not
be very low, but the probability that he is lucky in every one of a large
number of plays decreases very fast. Then it is shown how Arthur may reveal his
moves ahead of time with Merlin being unable to gain any advantage from having
this knowledge. This is done by playing differently on several boards, forcing
Merlin to answer the same move on all boards, and then letting Arthur select
afterwards the only one in which the play is to be continued. This allows one
to show that the turns may be switched under certain conditions, turning a
``Merlin-Arthur-Merlin'' fragment of play into an ``Arthur-Merlin-Arthur''
fragment. Moreover, here the last Arthur move is restricted to only a few
choices, and when it is the last move it can be replaced by a polynomial-time
computation. As a consequence, any constant number of turns is equivalent to
just two turns provided that Arthur moves first. The corresponding class is
denoted ${\rm AM}$.
One application of these games given in the paper is to recognize lower bounds
for counting. Given a polynomial-time decidable set of pairs $(x,y)$, with $y$
polynomially longer than $x$, and given $x$, we wish to check whether a guessed
approximation to the number of $y$'s that are paired to that $x$ is a lower
bound, in the following sense: if the guess is too high, Merlin has very small
chances; if it is far too low, he has high chances. No particular behavior is
required if it is a close enough lower bound. A protocol is given that yields
games that meet these conditions, based on universal hashing [see M. Sipser, in
Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing
(Boston, MA, 1983), 330--335, ACM, New York, 1983]. As a consequence,
applications are given that show that the graph nonisomorphism problem and the
coset intersection problem in permutation groups belong to the class AM.
Thus, these classes model a natural proof process and are useful to better
classify computational problems. Additional results have appeared regarding
these classes since their definition, and, in particular, the class ${\rm AM}$
can be characterized in many different ways. It forms a very interesting
subject of further study for the complexity-theorist.
{For the entire collection see MR 89a:68010}.},
    Reviewer = "Balcazar, Jose L",
}

@Article{Jacobs:van-Emde-Boas:86,
    Ordinal = 47,
    Author = Jacobs #&# van-Emde-Boas,
    Title = "Two Results on Tables",
    Year = 1986,
    Journal = ipl,
    Volume = 22,
    Number = 1,
    Pages = "43--48",
    Abstract = {
        A. C. C. Yao [J. Assoc. Comput. Mach. 28 (1981), no. 3,
        615--628; MR 82f:68099] has determined the maximal size of a
        finite universe $U$ such that it is possible to store all
        subsets $A$ of $U$ with $k$ elements in a table of $k$ slots in
        such a way that membership in $A$ can be determined in a single
        probe. In his model it is assumed that all elements of $A$ are
        physically stored in the table. If this assumption is relaxed
        and arbitrary elements in $U$ can be stored in order to encode
        subsets $A$, then Yao's upper bound is no longer valid. It
        fails for trivial reasons only: a single probe lookup strategy
        only exists when it is possible to encode arbitrary subsets of
        $U$ by a bitmap. ``Our second result is an improvement of the
        optimal program size for perfect hash functions, solving an
        open problem of C. Slot and van Emde Boas [Proceedings of the
        sixteenth annual ACM symposium on theory of computing
        (Washington, D.C., 1984), 391--400, ACM, New York, 1984; see MR
        87g:68005]. For every value $u$, value $k\le u$, and every
        subset $A$ of $U=\{ 0,\cdots,u-1\}$ there exists a perfect hash
        function $F$, which scatters $A$ completely into a hash table
        of size $O(k)$, such that the program size of $F$ is
        $O(k\cdot\log\log k+\log\log u)$ and the evaluation time of $F$
        is of order $O(1)$. These estimates are expressed in standard
        RAM space and instructions, respectively. This improves the
        $O(k\cdot\log k+\log\log u)$ upper bound established by K.
        Mehlhorn [Data structures and algorithms, Vol. 1, Chapter
        III.2.3, see pp. 127--139, Springer, Berlin, 1984; MR
        86e:68001] and Slot and van Emde Boas [op. cit.].
    },
}

@InProceedings{Gil:Matias:Vishkin:91,
    Ordinal = 51,
    Author = Gil #&# Matias #&# Vishkin,
    Title = "Towards a Theory of Nearly Constant Time Parallel Algorithms",
    Year = 1991,
    Month = Oct,
    BookTitle = focs91,
    Pages = "698--710",
    Abstract = {
        In this paper we demonstrate that randomization is an
        extremely powerful tool for designing very fast and efficient
        parallel algorithms. Specifically, a running time of
        $O(\log^*n )$ (``nearly-constant''), with high probability, is
        achieved using $n/ \log^*n $ (``optimal speedup'') processors
        for a wide range of fundamental problems, including:
        (1)~support dictionary operations: insert, delete, lookup; this
        is the first optimal dictionary algorithm that is in \RNC{}!
        (2)~load balancing (an essential tool for parallel
        computation); (3)~problems considered in
        \cite{Matias:Vishkin:91}, including hashing, leaders election,
        linear approximate compaction and generation of random
        permutations; (4)~simulation of $\Maximum{}$ (a powerful
        \CRCW{} \PRAM{} model) on $\Tolerant{}$ (a weak \CRCW{} \PRAM{}
        model); (5)~integer chain sorting. We also give a constant
        time algorithm which, using $n$ processors, approximates the
        sum of $n$ positive numbers to within an error which is smaller
        than the sum by an order of magnitude. A variety of known and
        new techniques are used. New techniques, which are of
        independent interest, include estimation of the size of a set
        in constant time for several settings, and ways for deriving
        super-fast optimal algorithms from super-fast non-optimal
        ones.
    },
    Note = "(Revised version)",
}

@InProceedings{Bast:Hagerup:91,
    Ordinal = 2,
    Author = Bast #&# Hagerup,
    Title = "Fast and Reliable Parallel Hashing",
    Year = 1991,
    Month = Jul,
    BookTitle = spaa91,
    Pages = "50-61",
    Abstract = {
        A \Em{perfect hash function} for a (multi)set $X$ of $n$
        integers is an injective function $h: X \rightarrow
        \{1,\ldots,s\}$, where $s = O(n)$, that can be stored in $O(n)$
        space and evaluated in constant time by a single processor. We
        show that a perfect hash function for a given multiset of $n$
        integers can be constructed in $O(\log^*n)$ time using
        $O(n/\log^*n)$ processors. Our algorithm is faster than all
        published methods. More significantly, it is highly reliable:
        Whereas analyses of previous fast parallel hashing schemes
        provided bounds on the expected resource requirments only, our
        algorithm is guaranteed to stay within the bounds given with
        overwhelming probability.
    },
    Location = "Hilton Head, South Carolina",
}

@InProceedings{Bast:Dietzfelbinger:Hagerup:92,
    Author = Bast #&# Dietzfelbinger #&# Hagerup,
    Title = "A Perfect Parallel Dictionary",
    Year = 1992,
    BookTitle = mfcs92,
    Pages = "133-141",
}

@InProceedings{Adleman:Kompella:88,
    Author = Adleman #&# Kompella,
    Title = "Using Smoothness to Achieve Parallelism",
    Year = 1988,
    BookTitle = stoc88,
    Pages = "528-538",
}

@InProceedings{Beame:89,
    Author = Beame,
    Title = "A General Sequential Time-Space Tradeoff for Finding Unique Elements",
    Year = 1989,
    BookTitle = stoc89,
    Pages = "197-203",
}

@PhdThesis{Blelloch:88,
    Author = Blelloch,
    Title = "Scan Primitives and Parallel Vector Models",
    Year = 1988,
    School = "Dept. of Electrical Engineering and Computer Science, MIT",
}

@InProceedings{Blelloch:87,
    Ordinal = 142,
    Author = Blelloch,
    Title = "Scans as Primitives Parallel Operations",
    Year = 1987,
    BookTitle = icpp87,
    Pages = "355-362",
}

@Article{Gottlieb:GKMRS:83,
    Author = Gottlieb #&# Grishman #&# Kruskal #&# McAulife #&# Rudolph #&# Snir,
    Title = "The {NYU} {U}ltracomputer -- designing an {MIMD} shared memory parallel machine",
    Year = 1983,
    Journal = "IEEE Trans. on Comp",
    Volume = "C-32",
    Pages = "175-189",
}

@Article{Hagerup:88,
    Ordinal = 169,
    Author = Hagerup,
    Title = "On saving space in parallel computation",
    Year = 1988,
    Journal = ipl,
    Volume = 29,
    Pages = "327-329",
}

@Article{Johnson:82,
    Author = Johnson,
    Title = "A priority queue in which initialization and queue operations take ${O}(\log\log {D})$ time",
    Year = 1982,
    Journal = "Math. Systems Theory",
    Volume = 15,
    Pages = "295-309",
}

%   CrossRef = "FOCS89",
@InProceedings{Berkman:Vishkin:89,
    Ordinal = 36,
    Author = Berkman #&# Vishkin,
    Title = "Recursive *-Tree Parallel Data-Structure",
    BookTitle = focs89,
    Pages = "196-202",
    Year = 1989,
    Note = "Also in UMIACS-TR-90-40, Institute for Advanced Computer Studies, Univ.\ of Maryland, March 1991. To appear in {\em SIAM J. Comput.}",
}

@Article{Berkman:Vishkin:93,
    Author = Berkman #&# Vishkin,
    Title = "Recursive Star-Tree Parallel Data Structure",
    Journal = sicomp,
    Pages = "221-242",
    Year = 1993,
    Volume = 22,
    Number = 2,
}

%   CrossRef = "FOCS90",
@InProceedings{BJKTV:90,
    Author = Berkman #&# Jaja #&# Krishnamurthy #&# Thurimella #&# Vishkin,
    Title = "Some triply-logarithmic parallel algorithms",
    BookTitle = focs90,
    Year = 1990,
    Pages = "871-881",
    Note1 = {To appear in {\em SIAM J. of Comput.} as
    `Top-bottom routing around a rectangle is as easy as computing
    prefix minima'}
}

@UnPublished{BJKTV:90a,
    Author = Berkman #&# Jaja #&# Krishnamurthy #&# Thurimella #&# Vishkin,
    Title = "Fast Routing around a rectangle",
    Year = 1990,
    Note = "In preparation",
}

@Article{BJKTV:94,
    Ordinal = 102,
    Author = Berkman #&# Jaja #&# Krishnamurthy #&# Thurimella #&# Vishkin,
    Title = "Top-Bottom Routing Around a Rectangle is as Easy as Computing Prefix Minima",
    Year = 1994,
    Journal = sicomp,
    Volume = 23,
    Number = 3,
    Month = jun,
    Pages = "449-465",
}

@InProceedings{Lamdan:Wolfson:88,
    Ordinal = 115,
    Author = Lamdan #&# Wolfson,
    Title = {Geometric Hashing: a General and Efficient Model-Based Recognition Scheme},
    Year = 1988,
    BookTitle = { Proc. 2nd Int'l Conf. on Computer Vision, Tampa, FL},
    Pages = {238-249},
}

--I think there was a typo in this entry. Please check
-- I cannot find entry 116, can you?
@InProceedings{Grimson:Huttenlocher:90,
    Ordinal = 116,
    Author = Eric #&# Grimson #&# Huttenlocher,
    Title = {On the Sensitivity of Geometric Hashing},
    Year = 1990,
    Pages = {334-338},
}

@Article{Kalvin:SSS:86,
    Author = Kalvin #&# Schonberg #&# Schwartz #&# Sharir,
    Title = "Two Dimensional, Model-Based, Boundary Matching using Footprints",
    Year = 1986,
    Journal = "The Int. J. of Robotics Research",
    Volume = 5,
    Number = 4,
    Pages = "38-55",
}

@UnPublished{Bern:Karloff:Raghavan:Schieber:89,
    Author = Bern #&# Karloff #&# Raghavan #&# Schieber,
    Title = "Fast Geometric Approximation Techniques and Geometric Embedding Problems",
    Year = 1989,
    Note = "manuscript",
}

@InProceedings{Chew:Fortune:88,
    Author = Chew #&# Fortune,
    Title = {Sorting Helps for {V}oronoi Diagrams},
    Year = 1988,
    BookTitle = { 13th Symp. on Mathematical Programming, Japan},
}

@UnPublished{Bergen:Shvaytser:90,
    Author = Bergen #&# Shvaytser,
    Title = "A Probabilistic Algorithm for computing {H}ough Transforms",
    Year = 1990,
    Note = "Manuscript",
}

@InProceedings{Karp:Miller:Rosenberg:72,
    Author = Karp #&# MillerRE #&# Rosenberg,
    Title = "Rapid identification of repeated patterns in strings, trees and arrays",
    Year = 1972,
    BookTitle = stoc72,
    Pages = "125-136",
}

@InProceedings{Kedem:Landau:Palem:89,
    Author = Kedem #&# Landau #&# Palem,
    Title = "Optimal Parallel Prefix-Suffix Matching Algorithm and Applications",
    Year = 1989,
    BookTitle = spaa89,
    Pages = "388-398",
}

@Article{Kedem:Palem:92,
    Author = Kedem #&# Palem,
    Title = "Optimal Parallel Algorithms for Forest and Term Matching",
    Year = 1992,
    Journal = tcs,
    Volume = 93,
    Pages = "245-264",
}

@Article{Ruzzo:80,
    Author = Ruzzo,
    Title = "Tree-size bounded alterations",
    Year = 1980,
    Journal = jcss,
    Volume = 21,
    Pages = "218-235",
}

@Article{Stockmeyer:Vishkin:84,
    Author = Stockmeyer #&# Vishkin,
    Title = "Simulation of Parallel Random Access Machines by Circuits",
    Year = 1984,
    Journal = sicomp,
    Volume = 13,
    Pages = "409-422",
}

@TechReport{Vishkin:83b,
    Ordinal = 128,
    Author = Vishkin,
    Title = "Synchronous parallel computation -- a survey",
    Year = 1983,
    Number = 71,
    Institution = courant,
    Note = {Also: Annual Paper Collection of ``Datalogforeningen"
(The Computer Science Association of Aarhus, Denmark), 1987, 76-89.},
}

@TechReport{Vishkin:83a,
    Author = Vishkin,
    Title = "On choice of a model of parallel computation",
    Year = 1983,
    Number = 61,
    Institution = courant,
}

@TechReport{Vishkin:90b,
    Ordinal = 135,
    Author = Vishkin,
    Title = "A parallel blocking flow algorithm for acyclic networks",
    Year = 1990,
    Number = "UMIACS-TR-90-11",
    Institution = "University of Maryland Inst. for Advanced Computer Studies",
}

@Article{Vishkin:92,
    Ordinal = "135a",
    Author = Vishkin,
    Title = "A parallel blocking flow algorithm for acyclic networks",
    Year = 1992,
    Journal = jalg,
    Volume = 13,
    Pages = "489-501",
}


@InProceedings{Rudolph:Steiger:85,
    Ordinal = 146,
    Author = Rudolph #&# Steiger,
    Title = "Subset Size in Parallel",
    Year = 1985,
    BookTitle = "Proc. International Conference on Parallel Processing",
    Pages = "11-13",
}

@Article{Ladner:Fischer:80,
    Author = Ladner #&# Fischer,
    Title = "Parallel prefix computation",
    Year = 1980,
    Journal = jacm,
    Volume = 27,
    Pages = "831-838",
}

@InProceedings{Martel:Vayda:88,
    Ordinal = 150,
    Author = Martel #&# Vayda,
    Title = "The complexity of selection resolution, conflict resolution and maximum finding on multiple access channels",
    Year = 1988,
    BookTitle = awoc88,
    Pages = "401-410",
}

@Article{Martel:Gusfield:89,
    Ordinal = 55,
    Author = Martel #&# Gusfield,
    Title = "A Fast Parallel Quicksort Algorithm",
    Year = 1989,
    Journal = ipl,
    Volume = 30,
    Pages = "97-102",
    Abstract = "Probably the first paper to use the Random CRCW PRAM model",
}

@Book{Patel:Kapadia:Owen:76,
    Author = Patel #&# Kapadia #&# Owen,
    Title = "Handbook of Statistical Distributions",
    Year = 1976,
    Publisher = "Marcel Dekker, Inc.",
    PLACE = "New York and Basel",
}

@InProceedings{Pintz:Steiger:Szemeredi:88,
    Author = Pintz #&# Steiger #&# Szemeredi,
    Title = "Two infinite sets of primes with fast primality tests",
    Year = 1988,
    BookTitle = stoc88,
    Pages = "504-509",
}

@UnPublished{Raman:91,
    Author = Raman,
    Title = "Optimal sub-logarithmic time integer sorting on a {CRCW} {PRAM} (note)",
    Year = 1991,
    Note = submitted,
}

@Article{Rosser:Schoenfeld:62,
    Author = Rosser #&# Schoenfeld,
    Title = "Approximate formulas for some functions of prime numbers",
    Year = 1962,
    Journal = "Illinois J. Math.",
    Volume = 6,
    Pages = "64-94",
}

@InProceedings{Slot:van-Emde-Boas:84,
    Ordinal = 71,
    Author = Slot #&# van-Emde-Boas,
    Title = "On tape versus core; an application of space efficient hash functions to the invariance of space",
    Year = 1984,
    Month = May,
    BookTitle = "Proc. of the 16th Ann. ACM Symp. on Theory of Computing",
    Pages = "391-400",
    PLACE = "Washington, D.C.",
}

@Article{van-Emde-Boas:Kaas:Zijlstra:77,
    Author = van-Emde-Boas #&# Kaas #&# Zijlstra,
    Title = "Design and implementation of an efficient priority queue",
    Year = 1977,
    Journal = "Math. Systems Theory",
    Volume = 10,
    Pages = "99-127",
}

@InProceedings{Khuller:Matias:91:CCCG,
    Author = Khuller #&# Matias,
    Title = "A Simple Randomized Sieve Algorithm for the Closest-Pair Problem",
    Year = 1991,
    BookTitle = cccg91,
    Pages = "130-134",
}

@InProceedings{Gil:Steiger:Wigderson:89,
    Author = Gil #&# Steiger #&# Wigderson,
    Title = "Some Geometric Medians",
    Year = 1989,
    BookTitle = cccg89,
}

@Article{Gil:Steiger:Wigderson:91,
    Author = Gil #&# Steiger #&# Wigderson,
    Title = "Geometric Medians",
    Journal = "Discrete Mathematics",
    Volume = 108,
    Number = 1,
    Pages = "37--51",
    Year = 1992,
    Month = Oct,
    Editor = "J. Nes\v{s}et\v{r}il",
    Publisher = "North-Holland",
    Note = "Special volume on {\em Topological, Algebraic, and Combinatorial Structures}."
}


@InProceedings{Gil:Rudolph:86,
    Ordinal = 149,
    Author = Gil #&# Rudolph,
    Title = "Counting and Packing in Parallel",
    Year = 1986,
    BookTitle = icpp86,
    Pages = {1000-1002},
}

@InProceedings{Dolev:Gil:86,
    Author = Dolev #&# Gil,
    Title = "Parallel Computation of Edit Distance",
    Year = 1987,
    BookTitle = icpp87,
}

@InProceedings{Gil:Werman:90,
    Author = Gil #&# Werman,
    Title = "Computing 2-Dimensional Min, Median and Max Filters",
    Year = 1990,
    BookTitle = "Proceedings of the 7th Israeli Symposium on Artificial Intelligence and Computer Vision",
    Note = "Also to appear in the IEEE Transactions on Pattern Analysis and Machine Intelligence",
}

@InProceedings{Gil:91,
    Ordinal = 82,
    Author = Gil,
    Title = "Fast Load Balancing on a {PRAM}",
    Year = 1991,
    Month = Dec,
    BookTitle = spdp91,
    Pages = "10--17",
    Location = "Dallas, Texas",
    Date = "December 2-5, 1991",
}

@Article{Gil:94,
    Author = Gil,
    Title = "Renaming and Dispersing: Techniques for Fast Load Balancing",
    Year = 1994,
    Month = Nov,
    Journal = jpdc,
    Pages = "149--157",
    Volume = 23,
    Number = 2
}

@Article{Gil:Matias:94:JPDC,
    Author = Gil #&# Matias,
    Title = "Fast and Efficient Simulations among {CRCW} {PRAM}s",
    Year = 1994,
    Month = Nov,
    Journal = jpdc,
    Pages = "135--148",
    Volume = 23,
    Number = 2
}

@TechReport{Gil:91:Report,
    Ordinal = 75,
    Author = Gil,
    Title = "Fast load Balancing on a {PRAM}",
    Year = 1991,
    Month = Jan,
    Number = {91-14},
    Institution = csubc,
    Note = submitted,
}

@TechReport{Gil:Feigon:91:Report,
    Author = Gil #&# Feigon,
    Title = "Debugging by Pre-Processing",
    Year = 1991,
    Number = {91-22},
    Institution = csubc,
}

%   CrossRef = "LATIN92",

@InProceedings{Gil:Matias:LATIN92,
    Ordinal = 209,
    Author = Gil #&# Matias,
    Title = "Leaders election without a conflict resolution rule---Fast and efficient randomized simulations among {CRCW} {PRAM}s",
    BookTitle = latin92,
    Year = 1992,
    Pages = "204-218",
}

@TechReport{Gil:Matias:91:Report,
    Ordinal = 85,
    Author = Gil #&# Matias,
    Title = "Leaders selection without conflict resolution rule",
    Year = 1991,
    Number = {91-21},
    Institution = csubc,
    Note = submitted,
}
@TechReport{Gil:Matias:TA:91,
    Author = Gil #&# Matias,
    Title = "Leaders Election Without a Conflict Resolution Rule---Fast and Efficient Randomized Simulations among {CRCW} {PRAM}s",
    Year = 1991,
    Number = {TR-243/92},
    Institution = Eskenasy,
    Note = "To appear in {\em J.\ of Parallel and Distributed Computing}",
}

@TechReport{Gil:Matias:91:Report:MD,
    Author = Gil #&# Matias,
    Title = "Leaders Election Without a Conflict Resolution Rule---Fast and Efficient Randomized Simulations among {CRCW} {PRAM}s",
    Year = 1991,
    Number = {91-147},
    Institution = UMIACS,
    Note = "To appear in {\em J.\ of Parallel and Distributed Computing}",
}

@TechReport{Apostolico:Iliopoulos:86,
    Author = Apostolico #&# Iliopoulos,
    Title = {Parallel log-time Construction of Suffix Trees},
    Year = 1986,
    Number = {CSD TR 632},
    Institution = {Department of Computer Science, Purdue University},
}

@Article{Guibas:Szemeredi:78,
    Ordinal = 154,
    Author = Guibas #&# Szemeredi,
    Title = "The Analysis of Double Hashing",
    Year = 1978,
    Month = Apr,
    Journal = jcss,
    Volume = 16,
    Pages = "226-274",
}

@InProceedings{Lueker:Molodowitch:88,
    Ordinal = 89,
    Author = Lueker #&# Molodowitch,
    Title = "More Analysis of Double Hashing",
    Year = 1988,
    BookTitle = stoc88,
    Abstract = {
        In~\cite{Guibas:Szemeredi:78} a deep and elegant analysis showed
        that double hashing was equivalent to ideal uniform hashing up
        to a load factor of about $0.319$. In this paper we give an
        analysis which proves this up to load factors arbitrarily close
        to~1. We understand from [\Komlos: private communication,
        1986; Guibas private communication, Fall 1987] that Ajtai,
        Guibas, \Komlos{} and \Szemeredi{} obtained this result in the
        first part of 1986; the analysis in this paper is of interest
        nonetheless because we demonstrate how a resampling technique
        can be used to obtain a remarkably simple proof.

    },
}

@Article{Chor:Goldreich:89,
    Ordinal = 88,
    Author = Chor #&# Goldreich,
    Title = {On the Power of Two-Point Based Sampling},
    Year = 1989,
    Journal = jcmplx,
    Volume = 5,
    Pages = {96-106},
}

@Article{Alon:Babai:Itai:86,
    Ordinal = 97,
    Author = Alon #&# Babai #&# Itai,
    Title = {A Fast and Simple Randomized Parallel Algorithm for the
    Maximal Independent Set Problem},
    Year = 1986,
    Journal = jalg,
    Volume = 7,
    Pages = {567-583},
}

@TechReport{Dietzfelbinger:91,
    Ordinal = 70,
    Author = Dietzfelbinger,
    Title = {On Limitations of the Performance of Universal Hashing with
    Linear Functions},
    Year = 1991,
    Month = Jun,
    Number = {Nr. 84},
    Institution = paderborn,
}

@Article{Harel:Tarjan:84,
    Author = Harel #&# Tarjan,
    Title = "Fast algorithms for finding nearest common ancestors",
    Year = 1984,
    Journal = sicomp,
    Volume = 13,
    Number = 2,
    Pages = "338-355",
}

@Article{Hart:Sharir:86,
    Author = Hart #&# Sharir,
    Title = "Non linearity of Davenport-Schinzel sequences and generalized path compression schemes",
    Year = 1986,
    Journal = "Combinatorica",
    Volume = "6(2)",
    Pages = "151-177",
}

@TechReport{Berkman:Vishkin:90:Report,
    Ordinal = 78,
    Author = Berkman #&# Vishkin,
    Title = "Recursive star-tree parallel data-structure",
    Year = 1990,
    Month = Mar,
    Number = "UMIACS-TR-90-40 CS-TR-2437",
    Institution = UMIACS,
    Note1 = "To appear in {\em SIAM J. Comput.}",
}

@TechReport{Berkman:Vishkin:91,
    Ordinal = 131,
    Author = Berkman #&# Vishkin,
    Title = "Almost fully-parallel parentheses matching",
    Year = 1991,
    Institution = UMIACS,
}

@InProceedings{Gabow:Bentley:Tarjan:84,
    Author = Gabow #&# Bentley #&# Tarjan,
    Title = "Scaling and related techniques for geometry problems",
    Year = 1984,
    BookTitle = stoc84,
    Pages = "135-143",
}

@TechReport{Berkman:Schieber:Vishkin:88A,
    Ordinal = 104,
    Author = Berkman #&# Schieber #&# Vishkin,
    Title = "Some doubly logarithmic parallel algorithms based on finding all nearest smaller values",
    Year = 1988,
    Month = Oct,
    Number = "UMIACS-TR-88-79",
    Institution = "Univ. of Maryland Inst. for Advanced Computer Studies",
    Note1 = "To appear in {\em J. Algorithms} as `Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values'",
}

@Article{Berkman:Schieber:Vishkin:93,
    Ordinal = 104,
    Author = Berkman #&# Schieber #&# Vishkin,
    Title = "Optimal Doubly Logarithmic Parallel Algorithms Based on Finding All Nearest Smaller Values",
    Year = 1993,
    Journal = jalg,
    Volume = 14,
    Pages = "344-370",
}

@TechReport{Alon:Schieber:87,
    Ordinal = 103,
    Author = Alon #&# Schieber,
    Title = "Optimal preprocessing for answering on-line product queries",
    Year = 1987,
    Number = "71/87",
    Institution = Eskenasy,
}

@InProceedings{Yao:82,
    Author = Yao,
    Title = "Space-Time Tradeoff for Answering Range Queries",
    Year = 1982,
    BookTitle = stoc82,
    Pages = "128-136",
}

@InProceedings{Cook:Dwork:82,
    Author = Cook #&# Dwork,
    Title = "Bounds on the time for parallel {RAM}s to compute simple functions",
    Year = 1982,
    BookTitle = stoc82,
    Pages = "231-233",
}

@PhdThesis{Schieber:87,
    Author = Schieber,
    Title = "Design and analysis of some parallel algorithms",
    Year = 1987,
    School = "Dept. of Computer Science, Tel Aviv Univ.",
}

@UnPublished{Ragde:90b,
    Author = Ragde,
    Title = "Towards lower bounds for parallel computation over moderate sized domains",
    Year = 1990,
    Note = "Manuscript",
}

@InProceedings{Meyer:Wigderson:85,
    Author = Fmadh #&# Wigderson,
    Title = "The complexity of parallel sorting",
    Year = 1985,
    BookTitle = focs85,
    Pages = "532-540",
}

@Article{Borodin:Hopcroft:84,
    Author = Borodin #&# Hopcroft,
    Title = "Routing, merging, and sorting on parallel models of computation",
    Year = 1985,
    Journal = jcss,
    Volume = 30,
    Pages = "130-145",
}

@TechReport{Azar:Vishkin:86,
    Author = Azar #&# Vishkin,
    Title = "Tight comparison bounds on the complexity of parallel sorting",
    Year = 1986,
    Number = "47/86",
    Institution = "Tel-Aviv University",
}

@Article{Boppana:IPL89,
    Ordinal = 141,
    Author = Boppana,
    Title = "The average-case parallel complexity of sorting",
    Year = 1989,
    Journal = ipl,
    Volume = 33,
    Pages = "145-146",
}

@Article{Azar:Vishkin:87,
    Ordinal = 138,
    Author = Azar #&# Vishkin,
    Title = "Tight comparison bounds on the complexity of parallel sorting",
    Year = 1987,
    Journal = sicomp,
    Volume = 16,
    Pages = "458-464",
}

@Article{Alon:Azar:88,
    Ordinal = 139,
    Author = Alon #&# Azar,
    Title = "The average complexity of deterministic and randomized parallel comparison-sorting algorithms",
    Year = 1988,
    Journal = sicomp,
    Volume = 17,
    Pages = "1178-1192",
}

@Article{Azar:91,
    Ordinal = 140,
    Author = Azar,
    Title = "Parallel comparison merging of many-ordered lists",
    Year = 1991,
    Journal = tcs,
    Volume = 83,
    Pages = "275-285",
}

@InProceedings{Gereb-Graus:Krizanc:87,
    Author = Gereb-Graus #&# Krizanc,
    Title = "The complexity of parallel comparison merging",
    BookTitle = focs87,
    Pages = "195-201",
    Year = 1987,
    Note = "Also {\em SIAM J.\ Comput.}, to appear"
}

@Misc{Dietz:Private:Communication:91,
    Author = Dietz,
    Year = 1991,
    Note = "Private communication",
}

@InProceedings{Dietz:92,
    Author = Dietz,
    Title = "Heap Construction in the Parallel Comparison Tree Model",
    BookTitle = swat92,
    Pages = "140-150",
    Month = jul,
    Year = 1992,
}

@InProceedings{Chandra:Fortune:Lipton:ICALP83,
    Ordinal = 108,
    Author = Chandra #&# Fortune #&# Lipton,
    Title = "Lower bounds for constant depth circuits for prefix problems",
    Year = 1983,
    BookTitle = icalp83,
    Pages = "109-117",
}

@InProceedings{Chaudhuri:91,
    Ordinal = 105,
    Author = Chaudhuri,
    Title = "Tight bounds for the chaining problem",
    Year = 1991,
    BookTitle = spaa91,
    Pages = "62-70",
}

@Article{Parberry:87,
    Author = Parberry,
    Title = "On the Time Required to Sum $n$ Semigroup Elements on a Parallel Machine with Simultaneous Writes",
    Year = 1987,
    Journal = tcs,
    Volume = 51,
    Pages = "239-247",
}

@Article{Joffe:74,
    Author = Joffe,
    Title = "On a Set of Almost Deterministic $k$-independent Random Variables",
    Year = 1974,
    Journal = ANNAL-PROB,
    Volume = 2,
    Pages = "161-162",
}

@Book{Spencer:Book,
    Author = Spencer,
    Title = "Ten Lectures on the Probabilistic Method",
    Year = 1987,
    Publisher = "SIAM, Philadelphia, PA",
}

@Book{Alon:Spencer:Book,
    Author = Alon #&# Spencer,
    Title = "The Probabilistic Method",
    Year = 1991,
    ISBN = "0-471-53588-5",
    CallNumber = "QA164.A46",
    Publisher = "John Wiley \& Sons, Inc.",
}

%   CrossRef = "FOCS89",
@InProceedings{Motwani:Naor:Naor:89,
    Author = Motwani #&# NaorJ #&# NaorM,
    Title = "The Probabilistic Method Yields Deterministic Parallel Algorithms",
    BookTitle = focs89,
    Year = 1989,
    Pages = "8-13",
}

%   CrossRef = "FOCS89",
@InProceedings{Berger:Rompel:89,
    Author = Berger #&# Rompel,
    Title = "Simulating $(\log^cn)$-wise Independence in {NC}",
    BookTitle = focs89,
    Year = 1989,
    Pages = "2-7",
}

%   CrossRef = "SODA91",
@InProceedings{Berger:91,
    Author = Berger,
    Title = "The Forth Moment Method",
    BookTitle = soda91,
    Year = 1991,
    Pages = "373-383",
}

@Article{Berger:Rompel:91,
    Author = Berger #&# Rompel,
    Title = "Simulating $(\log^cn)$-wise Independence in {NC}",
    Year = 1991,
    Journal = jacm,
    Volume = "?",
    Pages = "?",
}

@PhdThesis{Berger:PhD:90,
    Author = Berger,
    Title = "Using Randomness to Design Efficient Deterministic Algorithms",
    Year = 1990,
    Month = May,
    School = "EECS, MIT",
    Address = "Cambridge, MA",
}

@Article{Mullin:91,
    Author = Mullin,
    Title = "A Caution on Universal Classes of Hash Functions",
    Year = 1991,
    Journal = ipl,
    Volume = 37,
    Pages = "247-256",
}

%   CrossRef = "STOC90",
@InProceedings{Nisan:90,
    Author = Nisan,
    Title = "Pseudorandom Generators for Space-bounded Computations",
    BookTitle = stoc90,
    Year = 1990,
    Pages = "204-212",
}

@InProceedings{Mehlhorn:82,
    Author = Mehlhorn,
    Title = "On the Program Size of Perfect and Universal Hash Functions",
    Year = 1982,
    BookTitle = focs82,
    Pages = "170-175",
}

@InProceedings{Mairson:83,
    Ordinal = 99,
    Author = Mairson,
    Title = "The Program Complexity of Searching a Table",
    Year = 1983,
    BookTitle = focs83,
    Pages = "40-75",
}

@PhdThesis{Mairson:84,
    Author = Mairson,
    Title = "The Program Complexity of Searching a Table",
    Year = 1984,
    Number = "STAN-CS83-988",
    School = "Department of Computer Science, Stanford University",
    Address = "Stanford, CA",
}

%   CrossRef = "STOC91",
@InProceedings{Karp:91,
    Ordinal = 213,
    Author = Karp,
    Title = "Probabilistic Recurrence Relations",
    BookTitle = stoc91,
    Year = 1991,
    Month = may,
    Pages = "190-197",
}

@InProceedings{Adleman:78,
    Ordinal = 98,
    Author = Adleman,
    Title = "Two Theorems on Random Polynomial Time",
    Year = 1978,
    BookTitle = focs78,
    Pages = "75-83",
}

@InProceedings{Ajtai:Ben-Or:86,
    Author = Ajtai #&# Ben-Or,
    Title = "A Theorem on Probabilistic Constant Depth Computations",
    Year = 1986,
    BookTitle = stoc86,
    Pages = "471-474",
}

@Article{Bollobas:87,
    Author = Bollobas,
    Title = "Martingales, Isoperimetric Inequalities and Random Graphs",
    Year = 1987,
    Journal = "Colloq. Math. Soc. J. Bolyai",
    Volume = 52,
    Pages = "113-139",
}

@Book{Bollobas:Book,
    Author = Bollobas,
    Title = "Random Graphs",
    Year = 1985,
    Publisher = "Academic Press",
}

@InProceedings{Dolev:Dwork:Pippenger:Wigderson:83,
    Ordinal = 101,
    Author = Dolev #&# Dwork #&# Pippenger #&# Wigderson,
    Title = "Superconcentrators, Generalizers and Generalized Connectors with Limited Depth",
    Year = 1983,
    BookTitle = focs83,
    Pages = "42-50",
}

@InProceedings{Kim:89,
    Ordinal = 109,
    Author = Kim,
    Title = "Optimal Parallel Algorithms on Sorted Intervals",
    Year = 1983,
    BookTitle = allerton89,
    Pages = "766-775",
}

@InProceedings{Naor:Yung:89,
    Ordinal = 111,
    Author = NaorM #&# Yung,
    Title = "Universal One-Way Hash Functions and their Cryptographic Applications",
    Year = 1989,
    BookTitle = stoc89,
    Pages = "33-43",
    place = "Seattle",
}

%   CrossRef = "STOC90",
@InProceedings{Naor:Yung:90,
    Ordinal = 112,
    Author = NaorM #&# Yung,
    Title = "Public-Key cryptosystems Provably Secure against Chosen Ciphertext Attacks",
    BookTitle = stoc90,
    Year = 1990,
}

@UnPublished{DeSantis:Yung:90:UNPUBLISHED,
    Ordinal = 113,
    Author = DeSantis #&# Yung,
    Title = {``Metaproofs'' (and their Cryptographic Applications)},
    Year = 1990,
    Month = Mar,
    Note = "Manuscript",
}

@InProceedings{DeSantis:Yung:90,
    Ordinal = 114,
    Author = DeSantis #&# Yung,
    Title = "On the Design of Provably-Secure Cryptographic Hash Functions",
    Year = 1990,
    BookTitle = eurocrypt90,
}

@TechReport{Martel:91,
    Ordinal = 124,
    Author = Martel,
    Title = "Asynchronous {PRAM}s with Memory Latency",
    Year = 1991,
    Month = Apr,
    Number = "CSE-91-14",
    Institution = "Computer Science Division, University of California, Davis",
    Keyword = "Asynchronous PRAM, simulations, emulations",
}

@UnPublished{Vishkin:83:Choice,
    Ordinal = 127,
    Author = Vishkin,
    Title = "On Choice of a Model of Parallel Computation",
    Year = 1983,
    Month = Feb,
    Note = "Revised March 1984",
}

@UnPublished{Vishkin:83:Lucid,
    Ordinal = 129,
    Author = Vishkin,
    Title = "Lucid-Boxes Vs. Black-Boxes",
    Year = 1983,
    Month = Sep,
    Note = "Revised March 1984",
}

@InProceedings{Gazit:86,
    Ordinal = 134,
    Author = Gazit,
    Title = "An optimal randomized parallel algorithm for finding connected components in a graph",
    Year = 1986,
    BookTitle = focs86,
    Pages = "492-501",
}

@Article{Gazit:91,
    Author = Gazit,
    Title = "An optimal randomized parallel algorithm for finding connected components in a graph",
    Year = 1991,
    Journal = sicomp,
    Pages = "1046-1067",
}

@TechReport{Kedem:Palem:Raghunathan:Spirakis:91:Report,
    Ordinal = 143,
    Author = Kedem #&# Palem #&# Raghunathan #&# Spirakis,
    Title = "Combining Tentative and Definite Executions for Dependable Paralel Computing",
    Year = 1990,
    Month = Sep,
    Number = "UMIACS-JTR-90-122, CS-TR-2537",
    Institution = UMIACS,
    Keyword = "Faulty PRAM, Asynchronous PRAM, simulations, emulations",
}

%   CrossRef = "STOC91",
@InProceedings{Kedem:Palem:Raghunathan:Spirakis:91,
    Ordinal = 144,
    Author = Kedem #&# Palem #&# Raghunathan #&# Spirakis,
    Title = "Combining Tentative and Definite Executions for Very Fast Dependable Paralel Computing",
    BookTitle = stoc91,
    Year = 1991,
    Keyword = "Faulty PRAM, Asynchronous PRAM, simulations, emulations",
}

@Article{Shvartsman:91,
    Ordinal = 145,
    Author = Shvartsman,
    Title = "Achieving optimal {CRCW} {PRAM} fault-tolerance",
    Year = 1991,
    Month = Jul,
    Journal = ipl,
    Volume = 39,
    Pages = "59-66",
}

@InProceedings{Frieze:Rudolph:84,
    Ordinal = 153,
    Author = Frieze #&# Rudolph,
    Title = "A Parallel Algorithm for All Pairs Shortest Paths in a Random Graph",
    Year = 1984,
    BookTitle = allerton84,
    Pages = "663-670",
}

@InProceedings{Herley:90,
    Author = Herley,
    Title = "Space-Efficient Representations of Shared Data for Parallel Computers",
    Year = 1990,
    BookTitle = spaa90,
    Pages = "407-416",
}

@Article{Willard:83,
    Ordinal = 214,
    Author = Willard,
    Title = "Log-Logarithmic Worst-Case Range Queries are Possible in Space $\Theta(n)$",
    Year = 1983,
    Month = Aug,
    Journal = IPL,
    Volume = 17,
    Number = 2,
    Pages = "81-84",
}

@Article{Willard:Reif:89,
    Ordinal = 215,
    Author = Willard #&# Reif,
    Title = "Parallel Processing Can Be Harmful: {T}he Unusual Behavior of Interpolation Search",
    Year = 1989,
    Journal = InfoComp,
    Volume = 81,
    Pages = "364-379",
}

@Article{Karp:Luby:Madras:89,
    Ordinal = 216,
    Author = Karp #&# Luby #&# Madras,
    Title = "Monte-Carlo Approximation Algorithms for Enumeration Problems",
    Year = 1989,
    Journal = jalg,
    Volume = 10,
    Pages = "429--448",
}

@InProceedings{Karp:Luby:Madras:83,
    Ordinal = 217,
    Author = Karp #&# Luby,
    Title = "Monte-Carlo Approximation Algorithms for Enumeration and Reliability Problems",
    Year = 1983,
    BookTitle = focs83,
    Pages = "56--64",
}


%   CrossRef = "FOCS89",
@InProceedings{Kosaraju:89,
    Ordinal = 218,
    Author = "Kosaraju",
    Title = "Efficient Tree Pattern Matching",
    BookTitle = focs89,
    Year = 1989,
    Pages = "178-183",
}

@Article{Flajolet:Odlyzko:82,
    Author = Flajolet #&# Odlyzko,
    Title = "The Average Height of Binary Trees and other Simple Trees",
    Year = 1982,
    Journal = jcss,
    Volume = 25,
    Pages = "171--213",
}

@Article{Guibas:Odlyzko:81,
    Ordinal = 222,
    Author = Guibas #&# Odlyzko,
    Title = "String Overlaps, Pattern Matching and Nontransitive Games",
    Year = 1981,
    Series = "A",
    Journal = "Journal of Combinatorial Theory",
    Volume = 30,
    Pages = "183-208",
}


@Article{Chlebus:Vrto:91,
    Ordinal = 223,
    Author = Chlebus #&# Vrto,
    Title = "Parallel Quicksort",
    Year = 1991,
    Journal = JPDC,
    Pages = "332-337",
}

%   CrossRef = {FOCS89},
@InProceedings{Goodrich:Kosaraju:89,
    Ordinal = 224,
    Author = Goodrich #&# Kosaraju,
    Title = "Sorting on a Parallel Pointer Machine with Applications to Set Expression Evaluation (Preliminary Version)",
    BookTitle = focs89,
    Year = 1989,
    Pages = {190--195},
}

%   CrossRef = "FOCS89",
@InProceedings{Aragon:Seidel:89,
    Ordinal = 225,
    Author = Aragon #&# Seidel,
    Title = {Randomized Search Trees},
    BookTitle = focs89,
    Year = 1989,
    Pages = {540--545},
}

%   CrossRef = "FOCS88",
@InProceedings{Leighton:Maggs:Rao:88,
    Ordinal = 226,
    Author = Leighton #&# Maggs #&# Rao,
    Title = {Universal Packet Routing Algorithms},
    BookTitle = focs88,
    Pages = "256-269",
    Abstract = {
        In this paper we examine the packet routing problem in a
        network independent context. Our goal is to devise a strategy
        for routing that works well for a wide variety of networks. To
        achieve this goal, we partition the routing problem into two
        stages: a path selection stage and a scheduling stage. In the
        first stage we find paths for the packets with small maximum
        distance, $d$, and small maximum congestion, $c$. Once the
        paths are fixed, both are lower bounds on both the time
        required to deliver the packets. In the second stage we find a
        schedule for the movement of each packet along its path so that
        no two packets traverse the same edge at the same time, and so
        that the total time and maximum queue size required to route
        all of the packets to their destinations are minimized. For
        many graphs, the first stage is easy---we simply use
        randomized intermediate destinations as suggested by Valiant.
        The second stage is more challenging, however, and is the focus
        of this paper. Our results include:
        \begin{enumerate}
        \item a proof that there is a schedule of length $O(c+d)$ requiring
            only constant size queues for any set of paths with distance $d$
            and congestion $c$,
        \item a randomized on-line algorithm for routing any set of $N$
            ``leveled'' paths on a bounded-degree network in $O(c+d+\log N)$
            steps using constant size queues,
        \item the first on-line algorithm for routing $N$-packets in the
            $N$-node shuffle-exchange graph in $O(\log N)$ steps using
            constant size queues, and
        \item the first constructions of area and volume-universal networks
            requiring only $O(\log N)$ slowdown.
    \end{itemize}
    },
}

@Article{Tarjan:75,
    Ordinal = 227,
    Author = Tarjan,
    Title = "Efficiency of a Good But Not Linear Set Union Algorithm",
    Year = 1975,
    Month = Apr,
    Journal = JACM,
    Volume = 22,
    Number = 2,
    Pages = "215--225",
}


@Article{Snir:85,
    Author =  Snir,
    Title = "On Parallel Searching",
    Year = 1985,
    Journal = sicomp,
    Volume = 14,
    Pages = "688-707",
}

@Techreport(Berkman:Matias:Vishkin:91,
    AUTHOR = Berkman #&# Matias #&# Vishkin,
    TITLE = "Randomized Range-Maxima in Nearly-Constant Parallel Time",
    INSTITUTION = UMIACS,
    NUMBER = "UMIACS-TR-91-161",
    NOTE1 = "To appear in {\em  Computational Complexity}",
    YEAR = "1991")

@InProceedings(Berkman:Matias:Vishkin:92,
    AUTHOR = Berkman #&# Matias #&# Vishkin,
    TITLE = "Randomized Range-Maxima in Nearly-Constant Parallel Time",
    BookTitle = isaac92,
    PAGES = "135-144",
    NOTE1 = "To appear in {\em Computational Complexity}",
    YEAR = "1992")

@article(Berkman:Matias:Vishkin:93,
    AUTHOR = Berkman #&# Matias #&# Vishkin,
    TITLE = "Randomized Range-Maxima in Nearly-Constant Parallel Time",
    journal = cc,
    PAGES = "350-373",
    VOLUME = 2,
    YEAR = "1992")

@InProceedings(Amir:Landau:Vishkin:90,
    AUTHOR = Amir #&# Landau #&#  Vishkin,
    TITLE = "Efficient pattern matching with scaling",
    BOOKTITLE = soda90,
    PAGES = "344-357",
    YEAR = "1990"
)

@InProceedings(Ramachandran:Vishkin:88,
    AUTHOR = Ramachandran #&# Vishkin,
    TITLE = "Efficient parallel triconnectivity in logarithmic parallel time",
    BOOKTITLE = awoc88,
    PAGES = "33-42",
    YEAR = "1988"
)

@Book{Tarjan:Book,
    Author = Tarjan,
    Title = "Data Structures and Network Algorithms",
    Year = 1983,
    Publisher = "SIAM, Philadelphia, PA",
}

@PhdThesis{Berkman:PhD:91,
    Author = Berkman,
    Title = "Paradigms for very fast parallel algorithms",
    Year = 1991,
    Month = aug,
    School = "Tel {A}viv {U}niversity",
    Address = "Tel {A}viv 69978, {I}srael",
}

@InProceedings{Vishkin:ICALP91,
    Author = Vishkin,
    Title = "Structural Parallel Algorithmics",
    Year = 1991,
    BookTitle = icalp91,
    Pages = "363-380",
}

@InCollection{Vishkin:93,
    Author = Vishkin,
    Title = "Structural Parallel Algorithmics",
    Year = 1993,
    Pages = {1-18},
    Editor = "A. Gibbons and P. Spirakis",
    BookTitle = "Lectures on parallel computation",
    Publisher = "Cambridge University Press",
    Chapter = 1,
}

@InCollection{Spirakis:93,
    Author = Spirakis,
    Title = "{PRAM} Models and Fundamental Parallel Algorithmic
    Techniques: Part {II} (Randomized Algorithms)",
    Year = 1993,
    Pages = {41-66},
    Editor = "A. Gibbons and P. Spirakis",
    BookTitle = "Lectures on parallel computation",
    Publisher = "Cambridge University Press",
    Chapter = 13,
}

@InCollection{McColl:92,
    Author = McColl,
    Title = "General Purpose Parallel Computing",
    Year = 1993,
    Pages = {337-391},
    Editor = "A. Gibbons and P. Spirakis",
    BookTitle = "Lectures on parallel computation",
    Publisher = "Cambridge University Press",
    Chapter = 13,
}

@Unpublished{McColl:92a,
    Author = McColl,
    Title = "General Purpose Parallel Computing",
    Year = 1992,
    Month = apr,
    Note = "Manuscript",
}

@Book{Akl:89,
    Author = Akl,
    Title = "The Design and Analysis of Parallel Algorithms",
    Publisher = "Prentice-Hall",
    Year = "1989"
}

@Techreport{Atallah:90,
    AUTHOR = Atallah,
    TITLE = "Parallel Techniques for Computational Geometry",
    INSTITUTION = "Purdue University",
    NUMBER = "CS-1020",
    YEAR = "1990"
}

@PhdThesis{Matias:PhD:92,
    Author = Matias,
    Title = "Highly Parallel Randomized Algorithmics",
    Year = 1992,
    Month = dec,
    School = "Tel Aviv University",
    Address = "{T}el {A}viv 69978, {I}srael",
}

@TechReport{Berkman:Vishkin:90,
    AUTHOR = Berkman #&# Vishkin,
    TITLE = "On parallel integer merging",
    INSTITUTION = UMIACS,
    NUMBER = "UMIACS-TR-90-15.1 (revised version)",
    NOTE = "To appear in {\em Information and Computation}",
    YEAR = "1990"
}

@Unpublished{Berkman:Matias:92,
    Author = Berkman #&# Matias,
    Title = "Tight Triply-Logarithmic Parallel Algorithms for Integer
        Range Minima and Related Problems",
    Year = 1992,
    Note = "Manuscript",
}

@Inproceedings{Berkman:Matias:Ragde:93,
    Author = Berkman #&# Matias #&# Ragde,
    Title = "Triply-Logarithmic Upper and Lower Bounds for Minimum,
        Range Minima, and Related Problems with Integer Inputs",
    BookTitle = wads93,
     Pages = "175-187",
    Year = 1993,
}

@Unpublished{Berkman:Matias:94,
    Author = Berkman #&# Matias,
    Title = "Fast Parallel Algorithms for Minimum and Related Problems with
Small Integer Inputs",
    Year = 1994,
    Note = "Manuscript",
}

@Article{Berkman:Matias:94a,
    Author = Berkman #&# Matias,
    Title = "Fast Parallel Algorithms for Minimum and Related Problems with
Small Integer Inputs",
    Journal = ppl,
    Year = 1994,
    Note = "To appear",
}

@Article{Fortune:Hopcroft:79,
    Author = Fortune #&# Hopcroft,
    Title = {A note on {R}abin's nearest-neighbor algorithm},
    Journal = ipl,
    Volume = 8,
    Number = 1,
    Pages = "20-23",
    Year = 1979
}


@Article{FP-74,
   author =  "M.J. Fischer and M.S. Paterson",
    title =  "String Matching and Other Products",
    journal =  "Complexity of Computation, R.M. Karp (editor),
    SIAM-AMS Proceedings",
    year =   1974,
    volume =     7,
    pages =  "113-125"
}

@Article{Abr-87,
    author =  Abrahamson,
    title =  "Generalized String Matching",
    journal = sicomp,
    year =   1987,
    volume =  16,
    number =   6,
    pages =  "1039-1051"
}



@Article{Maurey:79,
    Author = "B. Maurey",
    Year = 1979,
    Title = "Construction de suites sym\'etriques",
    Journal = "Comptes Rendu Academie des Sciences Paris",
    Volume = 288,
    Pages = "679-681",
}

@Book{Milman:Schechtman:86,
    Author = "V. D. Milman and G. Schechtman",
    Year = 1986,
    Title = "Asymptotic Theory of Finite Dimensional Normed Spaces",
    Series = "Lecture Notes in Mathematics",
    Number = 1200,
    Publisher = "Springer Verlag",
    Address = "New York",
}

@InProceedings{Goldberg:Matias:Rao:94,
    Author = Goldberg #&# Matias #&# Rao,
    Title = "An Optical Simulation of Shared Memory",
    Year = 1994,
    Booktitle = spaa94,
    Month = jun,
    Pages = {257-267}
}

@InProceedings{DM:93,
    Author = Dietzfelbinger #&# Fmadh,
    Title = "Simple, Efficient Shared Memory Simulations",
    Year = 1993,
    BookTitle = spaa93,
    Pages = "110-119",
}


@InProceedings{GJLR:93,
    Author = Goldberg #&# Jerrum #&# Leighton #&# Rao,
    Title = "Doubly Logarithmic Communication Algorithms for Optical
     Communication Parallel Computers",
    Year = 1993,
    BookTitle = spaa93,
    Pages = {300-309}
}

@InProceedings{Gibbons:Matias:Ramachandran:94,
    Author = Gibbons #&# Matias #&# Ramachandran,
    Title = "The {QRQW} {PRAM}: Accounting for Contention in Parallel
        Algorithms",
    Year = 1994,
    Month = jan,
    Pages = {638-648},
    BookTitle = soda94,
}

@UnPublished{MacKenzie:Ramachandran:94,
    Author = MacKenzie #&# Ramachandran,
    Title = "Optical Communication and {ERCW} {PRAMs}",
    Year = 1994,
    Month = mar,
    Note = "Manuscript",
}


@InProceedings{Gibbons:Matias:Ramachandran:SPAA:94,
    Author = Gibbons #&# Matias #&# Ramachandran,
    Title = "Efficient Low-Contention Parallel Algorithms",
    Year = 1994,
    Month = jun,
    BookTitle = spaa94,
    Pages = {236-247},
}

@InProceedings{MacKenzie:Stout:93,
    Author = Mackenzie #&# Stout,
    Title = "Optimal Parallel Construction of Hamiltonian Cycles and
        Spanning Trees in Random Graphs",
    Year = 1993,
    Month = jun,
    BookTitle = spaa93,
    Pages = {224-229},
}

--------------------------------------------------------------

@Article{Anderson:Mayr:Warmuth:88,
    Author = "R.J. Anderson and E.W. Mayr and M.K. Warmuth",
    Title = "Parallel approximation algorithms for bin packing",
    Year = 1989,
    Journal = infocomp,
    Volume = 82,
    Pages = "262-277",
}

@Article{BarOn:Vishkin:85,
    Author = "I. {Bar-On} and U. Vishkin",
    Title = "Optimal parallel generation of a computation tree form",
    Year = 1985,
    Journal = "ACM Trans. on Prog. Lang. and Systems",
    Volume = 7,
    Pages = "348-357",
}

@Article{Dekel:Sahni:83,
    Author = "E. Dekel and S. Sahni",
    Title = "Parallel generation of postfix and tree forms",
    Year = 1983,
    Journal = "ACM Trans. on Prog. Languages and Systems",
    Volume = 5,
    Pages = "300-317",
}

@PhdThesis{Ryu:90,
    Author = "Kwan Woo Ryu",
    Title = "Efficient parallel algorithms on the network model",
    Year = 1990,
    Month = Mar,
    School = "Dept. of Computer Science, University of Maryland",
    Address = "College Park, MD 20742",
}

@Article{Fischer:Paterson:74,
    Author = "M.J. Fischer and M.S. Paterson",
    Title = "String Matching and Other Products",
    Year = 1974,
    Journal = "Complexity of Computation, R.M. Karp (editor), SIAM-AMS Proceedings",
    Volume = 7,
    Pages = "113-125",
}

@Article{Abrahamson:87,
    Author = "K. Abrahamson",
    Title = "Generalized String Matching",
    Year = 1987,
    Journal = "SIAM",
    Volume = 16,
    Number = 6,
    Pages = "1039-1051",
}

@UnPublished{Kosaraju:87,
    Author = "S. Rao Kosaraju",
    Title = "Efficient String Matching",
    Year = 1987,
    Note = "Manuscript",
}

@UnPublished{Ragde:90a,
    Author = "P. Ragde",
    Title = "Towards lower bounds for parallel computation over moderate sized domains",
    Year = 1990,
    Note = "Manuscript",
}

@UnPublished{BFR-90,
    Author = "O. Berkman and A. Fiat and M. Ricklin",
    Title = "On the response time of on-line algorithms",
    Year = 1990,
    Month = Nov,
    Note = "Submitted to STOC91",
}

@PhdThesis{Arjomandi:75,
    Author = "Arjomandi, E.",
    Title = "A Study of Parallelism in Graph Theory",
    Year = 1975,
    School = "Computer Science Department, University of Toronto",
}

@InProceedings{Hirschberg:76,
    Author = "Hirschberg, D. S.",
    Title = "Parallel algorithms for the transitive closure and the connected components problems",
    Year = 1976,
    BookTitle = "Proceedings 8th annual ACM Symposium on Theory of Computing",
    Pages = "55-57",
}

@Article{Preparata:78,
    Author = "Preparata, F. P.",
    Title = "New parallel sorting schemes",
    Year = 1978,
    Journal = "IEEE trans. Computer",
    Volume = "C-27",
    Pages = "669-673",
}

@PhdThesis{Savage:77,
    Author = "Savage, C.",
    Title = "Parallel Algorithms for Graph Theoretic Problems",
    Year = 1978,
    School = "University of Illinois, Urbana",
}

@PhdThesis{Shamos:78,
    Author = "Shamos, M. I.",
    Title = "Computational Geometry",
    Year = 1978,
    School = "Department of Computer Science, Yale University",
}

@Book{Preparata:Shamos:85,
    Author = "Preparata, F. P. and Shamos, M. I.",
    Title = "Computational Geometry; An Introduction",
    Year = 1985,
    Publisher = "Springer-Verlag",
}

@PhdThesis{Han:87,
    Author = "Han, Y.",
    Title = "Designing Fast and Efficient Parallel Algorithms",
    Year = 1987,
    School = "Duke University",
}

@Article{Atallah:Goodrich:86,
    Author = "Atallah, M. J. and Goodrich, M. T.",
    Title = "Efficient parallel solutions to some geometric problems",
    Year = 1986,
    Journal = "Journal of Parallel and Distributed Computing",
    Volume = "3(4)",
    Pages = "492-507",
}

@PhdThesis{Wyllie:81,
    Author = "Wyllie, J. C.",
    Title = "The Complexity of Parallel Computations",
    Year = 1981,
    School = "Computer Science Department, Conell University, Ithaca, NY",
}

@InProceedings{Fortune:Wyllie:78,
    Author = "Fortune, S. and J. Wyllie",
    Title = "Parallelism in random access machines",
    Year = 1978,
    BookTitle = "Proceedings of the 10th Annual ACM Symposium on Theory of Computing",
    Pages = "114-118",
}

@InProceedings{Goldberg:Plotkin:Shannon:87,
    Author = "Goldberg, A. and Plotkin, S. and Shannon, G.",
    Title = "Parallel symmetry-breaking in sparse graphs",
    Year = 1987,
    BookTitle = "Proceedings 19th Annual ACM Symposium on Theory of Computing",
    Pages = "315-324",
}

@InProceedings{Goldschlager:78,
    Author = "Goldschlager, L. M.",
    Title = "A unified approach to models of synchronous parallel machines",
    Year = 1978,
    BookTitle = "Proceedings 10th Annual ACM Symposium on Theory of Computing",
    Pages = "89-94",
}

@PhdThesis{Eckstein:77,
    Author = "Eckstein, D. M.",
    Title = "Parallel Processing Using Depth-First Search and Breadth-First Search",
    Year = 1977,
    School = "Computer Science Department, University of Iowa, Iowa City, Iowa",
}

@Article{Csanky:76,
    Author = "Csanky, L.",
    Title = "Fast parallel matrix inversion algorithms",
    Year = 1976,
    Journal = "SIAM J. Computing",
    Volume = 5,
    Pages = "618-623",
}

@Article{Aggarwal:Chazelle:Guibas:ODunlaing:Yap:85,
    Author = "Aggarwal, A. and Chazelle, B. and Guibas, L. and O'Dunlaing, C. and C. Yap",
    Title = "Parallel computational geometry",
    Year = 1988,
    Journal = "Algorithmica",
    Volume = "3(3)",
    Pages = "293-327",
}

@InProceedings{Kosaraju:Delcher:88,
    Author = "Kosaraju, S. R. and A. L. Delcher",
    Title = "Optimal parallel evaluation of tree-structured computations by ranking",
    Year = 1988,
    Month = "June/July",
    BookTitle = "Proceedings of the 3rd Aegean Workshop on Computing,AWOC 88",
    Pages = "101-110",
    Editor = "J. Reif",
    Publisher = "Spring-Verlag",
}

@InProceedings{CoVi188,
    Author = "Cole, R. and U. Vishkin",
    Title = "Optimal parallel algorithms for expression true evaluation and list ranking",
    Year = 1988,
    Month = "June/July",
    BookTitle = "Proceedings of the 3rd Aegean Workshop on Computing,AWOC 88",
    Pages = "91-100",
    Editor = "J. Reif",
    Publisher = "Spring-Verlag",
}

@InProceedings{ScVi88,
    Author = "Schieber, B. and U. Vishkin",
    Title = "On finding lowest common ancestors: simplification and parallelization",
    Year = 1988,
    BookTitle = "SIAM J. Computing",
    Volume = "17(6)",
    Pages = "1253-1262",
}

@TechReport{BeVi90,
    Author = "Berkman, O. and U. Vishkin",
    Title = "Recursive Star-Tree Parallel DaTa-Structure",
    Year = 1990,
    Month = Mar,
    Number = "UMIACS-TR-90-40",
    Institution = "University of Maryland",
}

@TechReport{JaJa:78,
    Author = "J. J\'{a}J\'{a}",
    Title = "Graph connectivity problems on parallel computers",
    Year = 1978,
    Month = Feb,
    Number = "CS-78-05",
    Institution = "The Pennsylvania State University",
}

@Article{CoVi89,
    Author = "Cole, R. and U. Vishkin",
    Title = "Faster optimal prefix sums and list ranking",
    Year = 1989,
    Journal = "Information and Computation",
    Volume = "81(3)",
    Pages = "334-352",
}

@Article{Dekel:Sahni:82,
    Author = "Dekel, E. and S. Sahni",
    Title = "Parallel scheduling algorithms",
    Year = 1983,
    Journal = "Operations Research",
    Volume = "31(1)",
    Pages = "24-49",
}

@Article{Schwartz:80,
    Author = "Schwartz, J. T.",
    Title = "Ultracomputers",
    Year = 1980,
    Journal = "ACM Transactions on Programming Languages and Systems",
    Volume = "2(4)",
    Pages = "484-521",
}

@InProceedings{Vi84,
    Author = "Vishkin, U.",
    Title = "Randomized speed-ups in parallel computation",
    Year = 1984,
    BookTitle = "Proceedings of the 16th ACM Symposium on Theory of Computing",
    Pages = "230-239",
}

@InProceedings{Wagner:Han:86,
    Author = "Wagner, W. and Y. Han",
    Title = "Parallel algorithms for bucked sorting and the data dependent prefix problem",
    Year = 1986,
    BookTitle = "Proceedings of the International Conference on Parallel Processing",
    Pages = "924-930",
}

@InProceedings{Gibbons:Rytter:86,
    Author = "Gibbons, A. and W. Rytter",
    Title = "An optimal parallel algorithm for dynamic evaluation and its applications",
    Year = 1986,
    BookTitle = "Proceedings of the sixth Conference on Foundations of Software Technology and Theoretical Computer Science, Lecture Notes in Computer Science 241",
    Pages = "453-469",
    Publisher = "Springer-Verlag",
}

@InProceedings{CoVi186,
    Author = "Cole, R. and U. Vishkin",
    Title = "Approximate coin tossing with applications to list, tree and graph problems",
    Year = 1986,
    BookTitle = "Proceedings 27th Annual IEEE Symposium on Foundations of Computer Science",
    Pages = "478-491",
}

@Article{Heller:77,
    Author = "Heller, D.",
    Title = "A survey of parallel algorithms in numerical linear algebra",
    Year = 1978,
    Journal = "SIAM Review",
    Volume = "20(4)",
    Pages = "740-777",
}

@TechReport{AbDa87,
    Author = "K. Abrahamson and N. Dadoun and D. A. Kirkpatrick and T. Przytycka",
    Title = "A simple parallel tree contraction algorithm",
    Year = 1987,
    Number = "87-30",
    Institution = "The University of British Columbia",
}

@Article{BaVi85,
    Author = "Bar-On, I. and U. Vishkin",
    Title = "Optimal parallel generation of a computation tree form",
    Year = 1985,
    Journal = "ACM Transactions Programming Languages and Systems",
    Volume = 7,
    Pages = "348-357",
}

@Article{MiRa88,
    Author = "Miller, G. L. and V. Ramachandran and E. Kaltofen",
    Title = "Efficient parallel evaluation of straight-line code and arithmetic circuits",
    Year = 1988,
    Journal = "SIAM J. Computing",
}

@InProceedings{MiRe85,
    Author = "Miller, G. L. and J. H. Reif",
    Title = "Parallel tree contraction and its applications",
    Year = 1985,
    BookTitle = "Proceedings 26th Annual IEEE Symposium on Foundations of Computer Science",
    Pages = "478-489",
}

@InProceedings{MiTe87,
    Author = "Miller, G. L. and S. Teng",
    Title = "Dynamic parallel complexity of computational circuits",
    Year = 1987,
    BookTitle = "Proceedings 19th Annual Symposium on Theory of Computing",
    Pages = "254-263",
}

@Article{Sn85,
    Author = "M. Snir",
    Title = "On parallel searching",
    Year = 1985,
    Journal = "SIAM J. Computing",
    Volume = 14,
    Pages = "688-707",
}

@Article{TaVi85,
    Author = "Tarjan, R. E. and U. Vishkin",
    Title = "Finding biconnected components and computing tree functions in logarithmic parallel time",
    Year = 1985,
    Journal = "SIAM J. Computing",
    Volume = 14,
    Pages = "862-874",
}

@Article{VaSk83,
    Author = "Valiant, L. G. and S. Skyum and S. Berkowitz and C. Rackoff",
    Title = "Fast parallel computation of polynomials using few processors",
    Year = 1983,
    Journal = "SIAM J. Computing",
    Volume = 12,
    Pages = "641-644",
}

@Article{EpGa88,
    Author = "S. Eppstein and Z. Galil",
    Title = "Parallel algorithmic techniques for combinatorial computation",
    Year = 1988,
    Journal = "Ann. Rev. Comput. Sci.",
    Volume = 3,
    Pages = "233-283",
}

@Article{HeYe88,
    Author = "X. He and Y. Yesha",
    Title = "Binary tree algebraic computations and parallel algorithms for simple graphs",
    Year = 1988,
    Journal = "J. of Algorithms",
    Volume = 9,
    Pages = "92-113",
}

@InProceedings{St83,
    Author = "Stout, Q. F.",
    Title = "Topological matching",
    Year = 1983,
    BookTitle = "Proceedings of the 15th Annual ACM Symposium on Theory of Computing",
    Pages = "24-31",
}

@Article{KrRu85,
    Author = "Kruskal, C. and L. Rudolph and M. Snir",
    Title = "The power of parallel prefix",
    Year = 1985,
    Journal = "IEEE Transactions on Computers",
    Pages = "965-968",
}

@InProceedings{KoDe88,
    Author = "Kosaraju, S. R. and A. Delcher",
    Title = "Optimal parallel evaluation of tree-structured computations by raking",
    Year = 1988,
    BookTitle = "Proceedings of AWOC88",
    Pages = "101-110",
    Publisher = "Springer-Verlag",
}

@InProceedings{GaBe84,
    Author = "Gabow, H.N. and J. Bentley and R.E. Tarjan",
    Title = "Scaling and related techniques for geometry problems",
    Year = 1984,
    BookTitle = "Proceedings 16th Annual ACM Symposium on Theory of Computing",
    Pages = "135-143",
}

@Article{Kr83,
    Author = "Kruskal, C.",
    Title = "Searching, merging, and sorting in parallel computation",
    Year = 1983,
    Journal = "IEEE Transactions on Computers",
    Volume = "C-32(10)",
    Pages = "942-946",
}

@Article{cole-88,
    Author = "R. Cole",
    Title = "Parallel merge sort",
    Year = 1988,
    Journal = "SIAM J. Computing",
    Volume = "17(4)",
    Pages = "770-785",
}

@Article{AtCo89,
    Author = "Atallah, M. and Cole, R. and M. Goodrich",
    Title = "Cascading divide-and-conquer: a technique for designing parallel algorithms",
    Year = 1989,
    Journal = "SIAM J. Computing",
    Volume = "18(3)",
    Pages = "499-532",
}

@Article{Vi87,
    Author = "Vishkin, U.",
    Title = "An optimal algorithm for selection",
    Year = 1987,
    Journal = "Advances in Computing Research",
    Volume = 4,
    Pages = "79-86",
}

@Article{Co188,
    Author = "R. Cole",
    Title = "An optimally efficient selection algorithm",
    Year = 1988,
    Journal = "Information Processing Letters",
    Volume = "26(6)",
    Pages = "295-299",
}

@Article{CoYa85,
    Author = "Cole , R. and C. Yap",
    Title = "A parallel median algorithm",
    Year = 1985,
    Journal = "Information Processing Letters",
    Volume = "20(3)",
    Pages = "137-139",
}

@InProceedings{AjKo86,
    Author = "Ajtai, M. and Komlos, J. and Steiger, W.L. and E. szemeredi",
    Title = "Deterministic selection in O($\log\log n$) parallel time",
    Year = 1986,
    BookTitle = "Proceedings of the 18th Annual ACM Symposium on Theory of Computing",
    Pages = "188-195",
}

@Article{AjKo83,
    Author = "Ajtai, M. and Komlos, J. and E. Szemeredi",
    Title = "Sorting in $c\log n$ parallel steps",
    Year = 1983,
    Journal = "Combinatorica",
    Volume = 3,
    Pages = "1-19",
}

@Article{BiNi89,
    Author = "Bilardi, G. and A. Nicolau",
    Title = "Adaptive bitonic sorting: an optimal parallel algorithm for shared-memory machines",
    Year = 1989,
    Journal = "SIAM J. Computing",
    Volume = 18,
    Pages = "216-228",
}

@Article{HaRu89,
    Author = "Hagerup, T. and C. Rub",
    Title = "Optimal merging and sorting on the EREW PRAM",
    Year = 1989,
    Journal = "Information Processing Letters",
    Volume = 33,
    Pages = "181-185",
}

@InProceedings{Ba68,
    Author = "Batcher, K.",
    Title = "Sorting networks and their applications",
    Year = "32(1968)",
    BookTitle = "AFIPS Spring Joint Computing Conference",
    Pages = "307-314",
}

@Book{Kn,
    Author = "D. Knuth",
    Title = "Sorting and Searching",
    Year = 1973,
    Publisher = "Addison-Wesley",
}

@Article{Wa74,
    Author = "A. Waksman",
    Title = "A permutation network",
    Year = 1968,
    Journal = "JACM",
    Volume = "15(1)",
    Pages = "159-163",
}

@Book{Be65,
    Author = "V. E. Benes",
    Title = "Mathematical Theory of Connecting Networks and Telephone Traffic",
    Year = 1965,
    Publisher = "Academic Pub. Company",
}

@Article{Cl53,
    Author = "C. Clos",
    Title = "A study of non-blocking switching networks",
    Year = 1953,
    Journal = "Bell Systems Technical Journal",
    Volume = "32(2)",
    Pages = "406-425",
}

@Book{ApGa85,
    Title = "Combinatorial Algorithms on Words",
    Year = 1985,
    Editor = "Alberto Apostolico and Zvi Galil",
    Publisher = "Springer-Verlag",
}

@Article{ApIl88,
    Author = "A. Apostolico and C. Iliopoulos and G. M. Landau and B. Schieber and U. Vishkin",
    Title = "Parallel Construction of a Suffix Tree with Applications",
    Year = 1988,
    Journal = "Algorithmica",
    Volume = 3,
    Pages = "347-365",
}

@Article{BoMo77,
    Author = "R. S. Boyer and J. S. Moore",
    Title = "A fast string searching algorithm",
    Year = 1977,
    Journal = "Communications ACM",
    Volume = 20,
    Pages = "762-772",
}

@Article{GaGi87,
    Author = "Z. Galil and R. Giancarlo",
    Title = "Parallel string matching with k mismatches",
    Year = 1987,
    Journal = "Theoretical Computer Science",
    Volume = 51,
    Pages = "343-348",
}

@Article{KnMo77,
    Author = "D. E. Knuth and J. H. Morris and V. B. Pratt",
    Title = "Fast pattern matching in strings",
    Year = 1977,
    Journal = "SIAM J. Computing",
    Volume = 6,
    Pages = "189-195",
}

@Article{landau-vishkin-86,
    Author = "G. M. Landau and U. Vishkin",
    Title = "Efficient string matching with k mismatches",
    Year = 1986,
    Journal = "Theoretical Computer Science",
    Volume = 43,
    Pages = "239-249",
}

@Article{landau-vishkin-89b,
    Author = "G. M. Landau and U. Vishkin",
    Title = "Efficient parallel and serial approximate string matching",
    Year = 1989,
    Journal = "Journal of Algorithms",
    Volume = "10(2)",
    Pages = "157-169",
}

@UnPublished{landau-vishkin-90,
    Author = "G. M. Landau and U. Vishkin",
    Title = "Pattern matching in a digitized image",
    Year = 1990,
    Note = "Manuscript",
}

@Article{Mc76,
    Author = "E. M. McCreight",
    Title = "A space economical suffix tree construction algorithm",
    Year = 1976,
    Journal = "JACM",
    Volume = 23,
    Pages = "262-272",
}

@InProceedings{Wi73,
    Author = "P. Wiener",
    Title = "Linear pattern matching algorithms",
    Year = 1973,
    BookTitle = "Proceedings of the 14th Annual Symposium on Switching and Automata Theory",
    Pages = "1-11",
}

@Article{Ga85,
    Author = "Z. Galil",
    Title = "Optimal parallel algorithms for string matching",
    Year = 1985,
    Journal = "Information and Control",
    Volume = 67,
    Pages = "144-157",
}

@Article{Vi85,
    Author = "U. Vishkin",
    Title = "Optimal parallel matching in strings",
    Year = 1985,
    Journal = "Information and Control",
    Volume = 67,
    Pages = "91-113",
}

@TechReport{ApAt88,
    Author = "A. Apostolico and M. Atallah and L. Larmore and H. McFaddin",
    Title = "Efficient parallel algorithms for string editing and related problems",
    Year = 1988,
    Number = "CSD-TR-724",
    Institution = "Computer Sciences Department, Purdue University",
}

@InProceedings{KeLa89,
    Author = "Z. Kedem and G. M. Landau and K. Palem",
    Title = "Optimal parallel suffix-prefix matching algorithm and applications",
    Year = 1989,
    BookTitle = "Proceedings of the 1989 ACM Symposium on Parallel Algorithms and Architectures",
    Pages = "388-398",
}

@Article{KaRa87,
    Author = "R. M. Karp and M. O. Rabin",
    Title = "Efficient randomized pattern-matching algorithms",
    Year = 1987,
    Journal = "IBM J. RES. DEVELOP.",
    Volume = "31(2)",
    Pages = "249-260",
}

@InBook{KaRa90,
    Author = "R. Karp and V. Ramachandran",
    Title = "A survey of parallel algorithms for shared-memory machines",
    Year = 1990,
    Chapter = "Handbook of Theoretical Computer Science",
    Publisher = "North-Holland",
}

@Article{FiWi65,
    Author = "N. J. Fine and H. S. Wilf",
    Title = "Uniqueness theorems for periodic functions",
    Year = 1965,
    Journal = "Proc. Amer. Math. Soc.",
    Volume = 16,
    Pages = "109-114",
}

@Article{LySc62,
    Author = "R. C. Lyndon and M. P. Schutzenberger",
    Title = "The equation $a^M =b^N c^P$ in a free group",
    Year = 1962,
    Journal = "Michigan Math. J.",
    Volume = 9,
    Pages = "289-298",
}

@Article{RoSc62,
    Author = "J. B. Rosser and L. Schoenfeld",
    Title = "Approximate Formulas for some functions of prime numbers",
    Year = 1962,
    Journal = "Illinois J. Math",
    Volume = 6,
    Pages = "64-94",
}

@Article{ETVi88,
    Author = "T. Eilam-Tzoreff and U. Vishkin",
    Title = "Matching patterns in a string subject to multi-linear transformations",
    Year = 1988,
    Journal = "Theoretical Computer Science",
    Volume = 60,
    Pages = "231-254",
}

@Article{Ry88,
    Author = "W. Rytter",
    Title = "A note on parallel transformations of regular expressions to nondeterministic finite automata",
    Year = 1988,
    Journal = "Theoretical Computer Science",
    Pages = "?",
}

@Article{Uk85,
    Author = "E. Ukkonen",
    Title = "Finding approximate patterns in strings",
    Year = 1985,
    Journal = "J. Algorithms",
    Volume = 6,
    Pages = "132-137",
}

@Article{GaGi88,
    Author = "Z. Galil and R. Giancarlo",
    Title = "Data structures and algorithms for approximate string matching",
    Year = 1988,
    Journal = "Journal of Complexity",
    Volume = 4,
    Pages = "33-72",
}

@UnPublished{BrGa88,
    Author = "D. Breslauer and Z. Galil",
    Title = "An optimal O($\log\log n$) time parallel string matching algorithm",
    Year = 1988,
    Note = "Manuscript",
}

@Article{Ba78,
    Author = " T. P. Baker",
    Title = "A technique for extending rapid exact-match string matching to arrays of more than one dimension",
    Year = 1978,
    Journal = "SIAM J. Computing",
    Volume = "7(4)",
    Pages = "533-541",
}

@Article{Bi77,
    Author = "R. S. Bird",
    Title = "Two dimensional pattern matching",
    Year = 1977,
    Journal = "Information Processing Letters",
    Volume = "6(5)",
    Pages = "168-170",
}

@Article{BrGu80,
    Author = "R. P. Brent and F. Gustavson and S. Y. Yun",
    Title = "Fast solution of Toeplitz systems of equations and computation of Pad\'{e} approximations",
    Year = 1980,
    Journal = "Journal of Algorithms",
    Volume = 1,
    Pages = "259-295",
}

@Article{BrTr71,
    Author = " W. Brown and J. Traub",
    Title = "On Euclid's algorithm and the theory of subresultants",
    Year = 1971,
    Journal = "JACM",
    Volume = "18(4)",
    Pages = "505-514",
}

@Article{Ga84,
    Author = "J. {von zur} Gathen",
    Title = "Parallel arithmetic computations: a survey",
    Year = 1984,
    Journal = "SIAM J. Computing",
    Volume = "13(4)",
    Pages = "802-824",
}

@InProceedings{Ga86,
    Author = "J. {von zur} Gathen",
    Title = "Parallel arithmetic computation: a survey",
    Year = 1986,
    BookTitle = "Proceedings MFCS",
    Pages = "93-112",
}

@Book{GoLo89,
    Author = "G. Golub and C. van Loan",
    Title = "Matrix Computations",
    Year = 1989,
    Publisher = "Johns Hopkins University Press",
}

@Article{Sc180,
    Author = "J. Schwartz",
    Title = "Fast probabilistic algorithms for verification of polynomial identities",
    Year = 1980,
    Journal = "JACM",
    Volume = "27(4)",
    Pages = "701-717",
}

@Article{Bi84,
    Author = "D. Bini",
    Title = "Parallel solution of certain Toeplitz linear systems",
    Year = 1984,
    Journal = "SIAM J. Computing",
    Volume = "13(2)",
    Pages = "268-276",
}

@Article{ChKa87,
    Author = "J. Chun and T. Kailath and H. Lev-Ari",
    Title = "Fast parallel algorithm for QR-factorization of structured matrices",
    Year = 1987,
    Journal = "SIAM J. Scientific and Statistical Computing",
    Volume = "8(6)",
    Pages = "899-913",
}

@Article{Co67,
    Author = "G. Collins",
    Title = "Subresultants and reduced polynomial remainder sequences",
    Year = 1967,
    Journal = "JACM",
    Volume = 14,
    Pages = "128-142",
}

@Article{CoWi90,
    Author = "D. Coppersmith and S. Winograd",
    Title = "Matrix multiplication via arithmetic progressions",
    Year = 1990,
    Journal = "J. of Symbolic Computations",
    Volume = "9(3)",
}

@Article{Mu87,
    Author = "K. Mulmuley",
    Title = "Fast parallel algorithm to compute the rank of a matrix",
    Year = 1987,
    Journal = "Combinatorica",
    Volume = "7(1)",
    Pages = "101-104",
}

@Article{Pa88,
    Author = "V. Pan",
    Title = "Computing the determinant and the characteristic polynomial of a matrix via solving linear systems of equations",
    Year = 1988,
    Journal = "Information Processing Letters",
    Volume = "28(2)",
    Pages = "71-75",
}

@Article{Be84,
    Author = "S. Berkowitz",
    Title = "On computing the determinant in small parallel time using a small number of processors",
    Year = 1984,
    Journal = "Information Processing Letters",
    Volume = "18(3)",
    Pages = "147-150",
}

@InProceedings{BiGe90,
    Author = "D. Bini and L. Gemignani",
    Title = "On the Euclidean scheme for polynomials",
    Year = 1990,
    BookTitle = "Proceedings of the 2nd Annual Symposium Parallel Algorithms and Architectures",
    Pages = "254-258",
}

@Article{BoGa82,
    Author = "A. Borodin and J. vonzur Gathen and J. Hopcroft",
    Title = "Fast parallel matrix and GCD computation",
    Year = 1982,
    Journal = "Information and Control",
    Volume = "52(3)",
    Pages = "241-256",
}

@InProceedings{Ch85,
    Author = "A. Chistov",
    Title = "Fast parallel calculation of the rank of matrices over a field of arbitrary characteristic",
    Year = 1985,
    BookTitle = "Proceedings of FCT",
    Pages = "63-69",
}

@Article{GaPa89,
    Author = "Z. Galil and V. Pan",
    Title = "Parallel evaluation of the determinant and of the inverse of a matrix",
    Year = 1989,
    Journal = "Information Processing Letters",
    Volume = 30,
    Pages = "41-45",
}

@Article{Pa87,
    Author = "V. Pan",
    Title = "Complexity of parallel matrix computations",
    Year = 1987,
    Journal = "Theoretical Computer Science",
    Volume = 54,
    Pages = "65-85",
}

@InProceedings{Pa90.1,
    Author = "V. Pan",
    Title = "Parallel least-squares solution of general and Toeplitz-like linear systems",
    Year = 1990,
    BookTitle = "Proceedings of the 2nd Annual Symposium Parallel Algorithms and Architectures",
    Pages = "244-253",
}

@Article{CoTu65,
    Author = "J. Cooley and J. Tukey",
    Title = "An algorithm for machine calculation of complex Fourier series",
    Year = 1965,
    Journal = "Mathematics of Computation",
    Volume = 19,
    Pages = "297-301",
}

@Book{Kn81,
    Author = "D. Knuth",
    Title = "The Art of Computer Programming: Seminumerical Algorithms",
    Year = 1981,
    Edition = "second",
    Publisher = "Addison-Wesley",
}

@Article{SaBr77,
    Author = "A. Sameh and R. Brent",
    Title = "Solving triangular systems on a parallel computer",
    Year = 1977,
    Journal = "SIAM J. on Numerical Analysis",
    Volume = 14,
    Pages = "1101-1113",
}

@Article{Sa42,
    Author = "P. Samuelson",
    Title = "A method for determining explicitly the coefficients of the characteristic polynomial",
    Year = 1942,
    Journal = "Annals of Mathematical Statistics",
    Volume = 13,
    Pages = "424-429",
}

@Book{St73,
    Author = "G. W. Stewart",
    Title = "Introduction to Matrix Computations",
    Year = 1973,
    Publisher = "Academic Press",
}

@Book{BeTs89,
    Author = "D. P. Bertsekas and J. N. Tsitsiklis",
    Title = "Parallel and Distributed Computation: Numerical Methods",
    Year = 1989,
    Publisher = "Prentice Hall",
}

@Book{BoMu75,
    Author = "A. Borodin and I. Munro",
    Title = "The Computational Complexity of Algebraic and Numeric Problems",
    Year = 1975,
    Publisher = "American Elsevier",
}

@Book{Ga59,
    Author = "F. R. Gantmacher",
    Title = "The Theory of Matrices",
    Year = 1959,
    Publisher = "Chelsea",
}

@Book{IsKe66,
    Author = "E. Isacson and H. B. Keller",
    Title = "Analysis of Numerical Methods",
    Year = 1966,
    Publisher = "Wiley",
}

@Article{PrSa78,
    Author = "F. P. Preparata and D. V. Sarwate",
    Title = "An improved parallel processor bound in fast matrix inversion",
    Year = 1978,
    Journal = "Information Processing Letters",
    Volume = 7,
    Pages = "148-149",
}

@Article{Of63,
    Author = " Yu. Ofman",
    Title = "On the algorithmic complexity of discrete functions",
    Year = 1963,
    Journal = "Sov. Phys. Dokl.",
    Volume = 7,
    Pages = "589-591",
}

@UnPublished{Pa90,
    Author = "V. Pan",
    Title = "Improved parallel computations with structured and general matrices",
    Year = 1990,
    Note = "extended abstract",
}

@Article{Tr64,
    Author = "W. F. Trench",
    Title = "An algorithm for inversion of finite Toeplitz matrices",
    Year = 1964,
    Journal = "J. of SIAM",
    Volume = "12(3)",
    Pages = "515-522",
}

@Article{Wi86,
    Author = "D. H. Wiedemann",
    Title = "Solving sparse linear equations over finite fields",
    Year = 1986,
    Journal = "IEEE Transactions on Information Theory",
    Volume = "32(1)",
    Pages = "54-62",
}

@Article{BeFe89,
    Author = "M. Ben-Or and E. Feig and D. Kozen and P. Tiwari",
    Title = "A fast parallel algorithm for determining all roots of a polynomial with real roots",
    Year = 1989,
    Journal = "SIAM J. Computing",
    Volume = "17(6)",
    Pages = "1081-1092",
}

@Article{BiPa86,
    Author = " D. Bini and V. Pan",
    Title = "Polynomial division and its computational complexity",
    Year = 1986,
    Journal = "Journal of Complexity",
    Volume = 2,
    Pages = "179-203",
}

@Article{Sw79,
    Author = "P. N. Swarztrauber",
    Title = "A parallel algorithm for solving general tridiagonal equations",
    Year = 1979,
    Journal = "Mathematics of Computation",
    Volume = "33(145)",
    Pages = "185-199",
}

@TechReport{Ka89,
    Author = "E. Kaltofen",
    Title = "Parallel Algebraic Algorithm design",
    Year = 1989,
    Institution = "Rensselaer Polytechnic Institute",
}

@Book{Ja74,
    Author = "N. Jacobson",
    Title = "Basic Algebra I",
    Year = 1974,
    Publisher = "W. H. Freeman \& Co.",
}

@Book{He64,
    Author = "I. N. Herstein",
    Title = "Topics in Algebra",
    Year = 1964,
    Publisher = "Xerox College Publishing",
}

@Article{Ho65,
    Author = "R. W. Hockney",
    Title = "A fast direct solution of Poisson's equation using Fourier analysis",
    Year = 1965,
    Journal = "JACM",
    Volume = 12,
    Pages = "95-113",
}

@Article{Ko74,
    Author = "P. M. Kogge",
    Title = "Parallel solution of recurrence problems",
    Year = 1974,
    Journal = "IBM Journal of Research and Development",
    Volume = 18,
    Pages = "138-148",
}

@Article{KoSt73,
    Author = "P. M. Kogge and H. S. Stone",
    Title = "A parallel algorithm for the efficient solution of a general class of recurrence equations",
    Year = 1973,
    Journal = "IEEE Transactions on Computers",
    Volume = 22,
    Pages = "786-792",
}

@Article{He76,
    Author = "D. Heller",
    Title = "Some aspects of the cyclic reduction algorithm for block tridiagonal linear systems",
    Year = 1976,
    Journal = "SIAM J. on Numerical Analysis",
    Volume = 13,
    Pages = "484-496",
}

@Article{ChKu78,
    Author = "S. C. Chen and D. J. Kuck and A. H. Sameh",
    Title = "Practical parallel band triangular systems solvers",
    Year = 1978,
    Journal = "ACM Transactions on Mathematical Software",
    Volume = 4,
    Pages = "270-277",
}

@Article{MuPa73,
    Author = "I. Munro and M. Paterson",
    Title = "Optimal algorithms for parallel polynomial evaluation",
    Year = 1973,
    Journal = "JCSS",
    Volume = "7(2)",
    Pages = "189-198",
}

@InProceedings{St66,
    Author = "T. G. Stockham",
    Title = "High speed convolution and correlation",
    Year = 1966,
    BookTitle = " AFIPS Conference Proceedings",
    Pages = "229-233",
}

@Book{Bl85,
    Author = "R. E. Blahut",
    Title = "Fast Algorithms for Digital Signal Processing",
    Year = 1985,
    Publisher = "Addison-Wesley",
}

@Book{McRa79,
    Author = "J. H. McClellan and C. M. Rader",
    Title = "Number Theory in Digital Signal Processing",
    Year = 1979,
    Publisher = "Prentice-Hall",
}

@Article{CoLe67,
    Author = "J. W. Cooley and P. A. Lewis and P. D. Welch",
    Title = "History of the fast Fourier transform",
    Year = 1967,
    Journal = "Proc. IEEE",
    Volume = 55,
    Pages = "1675-1677",
}

@Article{BoMo74,
    Author = "A. Borodin and R. Moenck",
    Title = "Fast modular transforms",
    Year = 1974,
    Journal = "JCSS",
    Volume = 8,
    Pages = "366-386",
}

@InProceedings{Fi72,
    Author = "C. M. Fiduccia",
    Title = "Polynomial evaluation via the division algorithm: the fast Fourier transform revisited",
    Year = 1972,
    BookTitle = "Proceedings of the 4th Annual ACM Symposium on Theory of Computing",
    Pages = "88-93",
}

@InProceedings{PaRe85,
    Author = "V. Pan and J. Reif",
    Title = "Efficient parallel solution of linear systems",
    Year = 1985,
    BookTitle = "Proceedings of the 17th Annual Symposium on Theory of Computing",
    Pages = "143-152",
}

@TechReport{IeKo90,
    Author = "D. Ierardi and D. Kozen",
    Title = "Parallel resultant computation",
    Year = 1990,
    Number = "TR 90-1087",
    Institution = "Cornell University",
}

@InProceedings{Fr79,
    Author = "R. Freivalds",
    Title = "Fast probabilistic algorithms",
    Year = 1979,
    BookTitle = "Proceedings of Mathematical Foundations of Computer Science",
    Volume = 74,
    Publisher = "Springer-Verlag",
}

@Book{AhHo74,
    Author = "A. V. Aho and J. E. Hopcroft and J. D. Ullman",
    Title = "The Design and Analysis of Computer Algorithms",
    Year = 1974,
    Publisher = "Addison-Wesley",
}

@Article{GoSe72,
    Author = "I. C. Gohberg and A. A. Semencul",
    Title = "On the inversion of finite Toeplitz matrices and their continuous analogs",
    Year = 1972,
    Journal = "Mat. Issled.",
    Volume = 2,
    Pages = "201-233",
}

@Article{FrMo79,
    Author = "B. Friedlander and M. Morf and T. Kailath and L. Ljung",
    Title = "New inversion formulas for matrices classified in terms of their distance from Teoplitz matrices",
    Year = 1979,
    Journal = "Linear Algebra and Its Applications",
    Volume = 27,
    Pages = "31-60",
}

@Article{goldschlager-shaw-staples-82,
    Author = "L.M. Goldschlager, R.A. Shaw and J. Staples",
    Title = "The maximum flow problem is log-space complete for P",
    Year = 1982,
    Journal = "tcs",
    Volume = 21,
    Pages = "105-111",
}

@Article{landau-vishkin-nussinov-86,
    Author = "G.M Landau, U. Vishkin and R. Nussinov",
    Title = "An efficient string matching algorithm with k differences for nucleotide and amino acid sequences",
    Year = 1986,
    Journal = "Nucleic Acids Research (Computer Issue)",
    Volume = "14,1",
    Pages = "31-46",
}

@Article{landau-vishkin-nussinov-87,
    Author = "G.M Landau, U. Vishkin and R. Nussinov",
    Title = "An efficient string matching algorithm with k substitutions for nucleotides and amino acid sequences",
    Year = 1987,
    Journal = "J. of Theoretical Biology",
    Volume = 126,
    Pages = "483-490",
}

@Article{landau-vishkin-nussinov-88,
    Author = "G.M Landau, U. Vishkin and R. Nussinov",
    Title = "Locating alignments with k differences for nucleotide and amino acid sequences",
    Year = 1988,
    Journal = "Computer Applications in the Biosciences (CABIOS)",
    Volume = "4,1",
    Pages = "19-24",
}

@Article{landau-vishkin-89a,
    Author = "G. M. Landau and U. Vishkin",
    Title = "Fast string matching with k differences",
    Year = 1989,
    Journal = "J. of Computer Systems and Sciences",
    Volume = "37,1",
    Pages = "63-78",
}

@Article{landau-vishkin-nussinov-90,
    Author = "G.M Landau, U. Vishkin and R. Nussinov",
    Title = "Fast alignment of DNA and protein sequences",
    Year = 1990,
    Journal = " Methods in Enzymology (a volume on Molecular Evolution: Computer Analysis of Protein and Nucleic Acid Sequences)",
    Volume = 183,
    Pages = "487-502",
}

-------------------------------------------------------------------------------------------------------------

@UnPublished{BSV-88a,
    Author = "O. Berkman and B. Schieber and U. Vishkin",
    Title = "The parallel complexity of finding the convex-hull of a monotone polygon",
    Year = 1988,
    Note = "In preparation",
}

@InProceedings{MMS-88,
    Author = "M.S. Manasse and L.A. McGeoch and D.D. Sleator",
    Title = "Competitive algorithms for on-line problems",
    Year = 1988,
    BookTitle = stoc88,
    Pages = "322-333",
}

@Article{EG-88,
    Author = "D. Eppstein and Z. Galil",
    Title = "Parallel algorithmic techniques for combinatorial computation",
    Year = 1988,
    Journal = "Ann. Rev. Comput. Sci.",
    Volume = 3,
    Pages = "233-283",
}

@mastersThesis{Be-88,
    Author = Berkman,
    Title = "Some doubly logarithmic parallel algorithms based on finding nearest smallers",
    Year = 1988,
    School = "Dept. of Computer Science, Tel Aviv Univ.",
}

@Article{StV-84,
    Author = "L. Stockmeyer and U. Vishkin",
    Title = "Simulation of parallel random access machines by circuits",
    Year = 1984,
    Journal = sicomp,
    Volume = 13,
    Pages = "409-422",
}

@InProceedings{KLP-89,
    Author = "Z.M. Kedem and G.M. Landau and K.V. Palem",
    Title = "Optimal parallel prefix-suffix matching algorithm and applications",
    Year = 1989,
    BookTitle = spaa89,
    Pages = "388-398",
}

@TechReport{BSV-88,
    Author = "O. Berkman and B. Schieber and U. Vishkin",
    Title = "Some doubly logarithmic parallel algorithms based on finding all nearest smaller values",
    Year = 1988,
    Number = "UMIACS-TR-88-79",
    Institution = "Univ. of Maryland Inst. for Advanced Computer Studies",
    Note = "Also {IBM} research report, Computer Science, RC 14128 (\#63291)",
}

@InProceedings{Vi-90,
    Author = {U. Vishkin},
    Title = {Deterministic Sampling---A New Technique for Fast
Pattern Matching},
    Year = 1990,
    BookTitle = stoc90,
    Pages = "170-180",
}

@InProceedings{Afek:Matias:89,
    Author = Afek #&# Matias,
    Title = "Simple and Efficient Election Algorithms for Anonymous Networks",
    Year = 1989,
    Month = Sep,
    BookTitle = wdag89,
    Pages = "183-194",
    Place = "Nice, France",
}

@InProceedings{Matias:Afek:89,
    Author = Matias #&# Afek,
    Title = "Simple and Efficient Election Algorithms for Anonymous Networks",
    Year = 1989,
    Month = Sep,
    BookTitle = wdag89,
    Pages = "183-194",
    Place = "Nice, France",
}

@TechReport{Afek:Matias:TA:91,
    Author = Afek #&# Matias,
    Title = "Elections in Anonymous Networks",
    Year = 1991,
    Number = "TR-223/91",
    Institution = Eskenasy,
    Note = "To appear in {\em Information and Computation}",
}


@TechReport{Afek:Matias:91,
    Author = Afek #&# Matias,
    Title = "Elections in Anonymous Networks",
    Year = 1991,
    Number = "UMIACS-TR-91-115",
    Institution = UMIACS,
    Note = "To appear in {\em Information and Computation}",
}

@Article{Afek:Matias:94,
    Author = Afek #&# Matias,
    Title = "Elections in Anonymous Networks",
    Year = 1994,
    Month = sep,
    Volume = 113,
    Journal = infocomp,
    Number = 2,
    Pages = "312--330",
}


@InProceedings{Lavallee:Lavault:90a,
    Author = Lavallee #&# Lavault,
    Title = "Spanning tree construction in nameless networks",
    Year = 1990,
    Month = Sep,
    Pages  = "41-56",
    BookTitle = wdag90,
    Place = "Ontario, Italy",
}

@TechReport{Raghavan:89,
    Author = Raghavan,
    Title = "Lecture notes in randomized algorithms",
    Year = 1989,
    Number = 146,
    Institution = "IBM",
}

@Book{Brassard:Bratley:88,
    FAuthor = "Gilles Brassard and Paul Bratley",
    Author = Brassard #&#  Bratley,
    Title = "Algorithmics: Theory and Practice",
    Year = 1988,
    Publisher = "Prentice Hall",
    Address = "Englewood Cliffs, New Jersey 07632",
}

@Book{mehlhorn-book,
    Author = Mehlhorn,
    Title = "Data Structures and Algorithms, 1: Sorting and Searching",
    Year = 1984,
    Publisher = "Springer-Verlag, Berlin Heidelberg",
}

@TechReport{Matias:Ruppin:91:Both,
    Author = Matias #&# Ruppin,
    Title = "A neural network model for a randomized frequency-spatial transformation",
    Year = 1991,
    Number = "TR-212/91",
    Institution = Eskenasy,
    Note = "Also in UMIACS-TR-91-82, Institute for Advanced Computer Studies, University of Maryland. Submitted for publication",
}

@TechReport{Matias:Ruppin:91:TA,
    Author = Matias #&# Ruppin,
    Title = "A neural network model for a randomized frequency-spatial transformation",
    Year = 1991,
    Number = "TR-212/91",
    Institution = Eskenasy,
    Note = submitted,
}

@TechReport{Matias:Ruppin:91:MD,
    Author = Matias #&# Ruppin,
    Title = "A Neural Network Model for a Randomized Frequency-Spatial Transformation",
    Year = 1991,
    Number = "UMIACS-TR-91-82",
    Institution = UMIACS,
    Note = submitted,
}

@InProceedings{Matias:Ruppin:92,
    Author = Matias #&# Ruppin,
    Title = "A Neural Network Model for a Randomized Frequency-Spatial Transformation",
    BookTitle = "Computation and Neural Systems, Eeckman and Bower Ed.,
     a collection from papers presented in the
     {\em First Annual Computation and Neural Systems Meeting (CNS)}",
    Month = jul,
    Place = "San Francisco, California",
    Year = 1992,
    Publisher = "Kluwer Academic",
    Chapter = 68,
    Pages = "449-454",

}


@MastersThesis{Matias:87,
    Author = Matias,
    Title = "A Video Scrambling Technique based on Space Filling Curves",
    Year = 1987,
    Publisher = "The Weizmann Institute of Science, Master Thesis",
    School = "The Weizmann Institute of Science",
    PLACE = "Rehovot, Israel",
}

@InProceedings{Matias:Shamir:87,
    Author = "Yossi Matias and Adi Shamir",
    Title = "A Video Scrambling Technique Based on Space Filling Curves",
    Year = 1987,
    Month = Aug,
    BookTitle = crypto87,
    Pages = "398-417",
    PLACE = "Santa Barbara",
}

@UnPublished{Matias:Shamir:90,
    Author = "Yossi Matias and Adi Shamir",
    Title = "Video Scrambling Apparatus and Method Based on Space Filling Curves",
    Year = 1990,
    Note = "U.S. Patent 4,910,772",
}

@UnPublished{Matias:Shamir:91,
    Author = "Yossi Matias and Adi Shamir",
    Title = "Video Scrambling Apparatus and Method Based on Space Filling Curves",
    Year = 1991,
    Note = "U.S. Patent 5,058,158",
}

@InProceedings{Khuller:Matias:91,
    Author = Khuller #&# Matias,
    Title = "A Simple Randomized Sieve Algorithm for the Closest-Pair Problem",
    Year = 1991,
    BookTitle = cccg91,
    Pages = "130-134",
    Note = "To appear in {\em information and computation}",
}

@TechReport{Khuller:Matias:91:MD,
    Author = Khuller #&# Matias,
    Title = "A Simple Randomized Sieve Algorithm for the Closest-Pair Problem",
    Year = 1991,
    Number = "UMIACS-TR-91-126",
    Institution = UMIACS,
    Note = submitted,
}

@UnPublished{Matias:93:Semi,
    Author = Matias,
    Title = "Semi-Dynamic Closest-Pairs: On-line Algorithms and their Limitations",
    Year = 1993,
    Note = "Manuscript",
}

@UnPublished{Matias:93:Semi2,
    Author = Matias,
    Title = "Semi-Dynamic Closest-Pairs: Extensions and Generalizations",
    Year = 1993,
    Note = "Manuscript",
}

@InProceedings{AESW:90,
    Author = "P. K. Agarwal and  H. Edelsbrunner and O. Schwarzkopf and
        E. Welzl",
    Title = "Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs",
    BookTitle = scg90,
    Pages = "203--210",
    Year = 1990,
}

@Article{Bentley:80,
    Author = Bentley,
    Title = "Multidimensional Divide-and-Conquer",
    Journal = cacm,
    Volume = 23,
    Pages = "214--229",
    Year = 1980,
}

@InProceedings{Schwarz:Smid:92,
    Author = Schwarz #&# Smid,
    Title = "An ${O}(n\log n\log\log n)$ Algorithm for the On-line Closest
        Pair Problem",
    BookTitle = soda92,
    Pages = "280-285",
    Year = 1992,
}

@InProceedings{Schwarz:Smid:Snoeyink:92,
    Author = Schwarz #&# Smid #&# Snoeyink,
    Title = "An Optimal Algorithm for the On-line Closest-Pair Problem",
    BookTitle = scg92,
    Pages = "330-336",
    Year = 1992,
}

@TechReport{Smid:91:Report,
    Author = Smid,
    Title = "Dynamic Rectangular Point Location, with an Application
        to the Closest Pair Problem",
    Number = "MPI-I-91-101, Max-Planck-Insitut fur Informatik,
        Saarbrucken, 1991",
}

@InProceedings{Smid:91,
    Author = Smid,
    Title = "Dynamic Rectangular Point Location, with an Application
        to the Closest Pair Problem",
    BookTitle = "Proc. 2nd Annual International Symp. on Algorithms",
    Year = 1991,
}

@Article{Smid:91:Review,
    Author = Smid,
    Title = "Maintaining the minimal distance of a point set in
        less than linear time",
    Journal = "Algorithms Review",
    Volume = 2,
    Pages = "33-44",
    Year = 1991,
}

@Article{Smid:92,
    Author = Smid,
    Title = "Maintaining the minimal distance of a point set in
        polylogarithmic time",
    Journal = "Discrete Comput. Geom.",
    Pages = "415-431",
    Year = 1992,
}

@InProceedings{Supowit:90,
    Author = Supowit,
    Title = "New Techniques for some Dynamic Closest-point and
        Farthest-point problems",
    BookTitle = soda90,
    Pages = "84-90",
    Year = 1990,
}

@Article{Salowe:92,
    Author = Salowe,
    Title = "Shallow Interdistance Selection and Interdistance
        Enumeration",
    Journal = "International Journal of Computational Geometry \&
        Applications",
    Volume = 2,
    Pages = "49-59",
    Year = 1992,
}

@InProceedings{Dickerson:Drysdale:91,
    Author = Dickerson #&# Drysdale,
    Title = "Enumerating $k$ Distances for $n$ points in the Plane",
    BookTitle = scg91,
    Pages = "234-238",
    Year = 1991,
}

@InProceedings{Lenhof:Smid:92,
    Author = Lenhof #&# Smid,
    Title = "Enumerating the $k$ Closest Pairs Optimally",
    BookTitle = focs92,
    Pages = "380-386",
    Year = 1992,
}

@InProceedings{Katoh:Iwano:92,
    Author = Katoh #&# Iwano,
    Title = "Finding $k$ Farthest Pairs and $k$ Closest/Farthest
        Bichromatic Pairs for Points in the Plane",
    BookTitle = scg92,
    Pages = "320-329",
    Year = 1992,
}

@Unpublished{Golin:Raman:Schwarz:Smid:92,
    Author = Golin #&# Raman #&# Schwarz #&# Smid,
    Title = "Randomized Data Structures for the Dynamic Closest-Pair
        Problem",
    Note = "Manuscript",
    Month = aug,
    Year = 1992,
}

@InProceedings{Golin:Raman:Schwarz:Smid:93,
    Author = Golin #&# Raman #&# Schwarz #&# Smid,
    Title = "Randomized Data Structures for the Dynamic Closest-Pair
        Problem",
    BookTitle = soda93,
    Month = jan,
    Year = 1993,
}

@InProceedings{Golin:Raman:Schwarz:Smid:93b,
    Author = Golin #&# Raman #&# Schwarz #&# Smid,
    Title = "Simple Randomized Algorithms for Closest Pair Problems",
    BookTitle = cccg93,
    Month = aug,
    Year = 1993,
}

@InProceedings{Ben-Or:83,
    Author = Ben-Or,
    Title = "Lower bounds for algebraic computation trees",
    BookTitle = stoc83,
    Pages = "80-86",
    Year = 1983,
}

@Article{Yao:91,
    Author = Yao,
    Title = "Lower bounds for algebraic computation trees with integer
        inputs",
    Journal = sicomp,
    Volume = 20,
    Number = 4,
    Pages = "655-668",
    Year = 1991
}

@Article{Bentley:79,
    Author = Bentley,
    Title = "Decomposable Searching Problems",
    Journal = ipl,
    Volume = 8,
    Pages = "244-251",
    Year = 1979,
}

@InProceedings{Bentley:Shamos:76,
    Author = Bentley #&# Shamos,
    Title = "Divide and conquer in multidimensional space",
    BookTitle = stoc76,
    Pages = "220-230",
    Year = 1976,
}

@Article{Bentley:80,
    Author = Bentley,
    Title = "Multidimensional Divide-and-conquer",
    Journal = cacm,
    Volume = 23,
    Pages = "214-229",
    Year = 1980,
}

@InProceedings{Clarkson:83,
    Author = Clarkson,
    Title = "Fast algorithms for the all nearest neighbours problem",
    BookTitle = focs83,
    Pages = "226-232",
    Year = 1983,
}

@Article{Clarkson:Shor:89,
    Author = Clarkson #&# Shor,
    Title = "Applications of Random Sampling in Computational Geometry {II}",
    Journal = "Discrete \& Comput. Geometry",
    Volume = 4,
    Pages = "387-421",
    Year = 1989,
}

@InProceedings{Shamos:Hoey:75,
    Author = Shamos #&# Hoey,
    Title = "Closest-point problems",
    BookTitle = focs75,
    Pages = "151-162",
    Year = 1975,
}

@Article{Vaidya:89,
    Author = Vaidya,
    Title = "An ${O}(n\log n)$ algorithm for the all-nearest-neighbors
        problem",
    Journal = "Discrete \& Comput. Geometry",
    Volume = 4,
    Pages = "101-115",
    Year = 1989,
}

@Article{HNS:88,
    Author = "K. Hinrichs and J. Nievergelt and P. Schorn",
    Title = "Plane-sweep solves the closest pair problem elegantly",
    Journal = ipl,
    Volume = 26,
    Pages = "255-261",
    Year = 1988,
}



@Book{CLR:90,
    Author = "T. Cormen and  C. Leiserson and R. Rivest",
    Title = "Introduction to Algorithms",
    Publisher = "McGraw Hill and The MIT Press",
    Year = 1990,
}



@Book{Reif:91A,
    Title = "Synthesis of Parallel Algorithms",
    Year = 1991,
    Editor = Reif,
    Publisher = "Morgan Kaufmann, San Mateo, California",
}

@Book{Reif93:book,
    Editor = Reif,
    Title = {A Synthesis of Parallel Algorithms},
    Publisher = {Morgan-Kaufmann},
    Year = {1993},
    Address = {San Mateo, CA}
}

@Book{Gibbons:Rytter:88,
    Author = "A. Gibbons and W. Rytter",
    Title = "Efficient Parallel Algorithms",
    Year = 1988,
    Publisher = "Cambridge University Press, Cambridge",
}

@TechReport{Alon:Megiddo:90:Report,
    Ordinal = 172,
    Author = Alon #&# Megiddo,
    Title = "Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time",
    Year = 1990,
    Number = "RJ 7245",
    Institution = IBM-Almaden,
}

@InProceedings{Alon:Megiddo:90,
    Author = Alon #&# Megiddo,
    Title = "Parallel Linear Programming in Fixed Dimension Almost Surely in Constant Time",
    Year = 1990,
    BookTitle = focs90,
}

@Article{Han:89,
    Ordinal = 170,
    Author = Han,
    Title = "Parallel Algorithms for Computing Linked List Prefix",
    Year = 1989,
    Journal = jpdc,
    Volume = 6,
    Pages = "537-557",
}

@InProceedings{Han:89:CONF,
    Ordinal = 171,
    Author = Han,
    Title = "Matching Partition a Linked List and Its Optimization",
    Year = 1989,
    BookTitle = spaa89,
    Pages = "246-253",
}

@InProceedings{Anderson:90,
    Author = Anderson,
    Title = "Parallel Algorithms for Generating Random Permutations on a Shared Memory Machine",
    Year = 1990,
    BookTitle = spaa90,
    Pages = "95-102",
}

@Article{Ullman:Yannakakis:91,
    Ordinal = 161,
    Author = Ullman #&# Yannakakis,
    Title = "High-Probability Parallel Transitive-Closure Algorithms",
    Year = 1991,
    Month = Feb,
    Journal = sicomp,
    Volume = 20,
    Number = 1,
    Pages = "100-125",
}

@Article{Ullman:Yannakakis:90,
    Ordinal = 162,
    Author = Ullman #&# Yannakakis,
    Title = "High-Probability Parallel Transitive-Closure Algorithms",
    Year = 1990,
    BookTitle = spaa90,
    Pages = "200-209",
}

@Article{Vishkin:91,
    Author = Vishkin,
    Title = "Deterministic Sampling---A New Technique for Fast Pattern Matching",
    Year = 1991,
    Month = Feb,
    Journal = sicomp,
    Volume = 20,
    Number = 1,
    Pages = "22-40",
}

@InCollection{Miller:Reif:89,
    Ordinal = 157,
    Author = Miller #&# Reif,
    Title = "Parallel Tree Contraction, {P}art 1: Fundamentals",
    Year = 1989,
    BookTitle = "Randomness and Computation",
    Volume = 5,
    Pages = "47-72",
    Editor = Micali,
    Publisher = "JAI Press",
    Place = "Greenwich, CT",
    Keyword = "Parallel, Randomized",
}

@Article{Miller:Reif:91,
    Ordinal = 158,
    Author = Miller #&# Reif,
    Title = "Parallel Tree Contraction, {P}art 2: Further Applications",
    Year = 1991,
    Month = Dec,
    Journal = sicomp,
    Volume = 20,
    Number = 6,
    Pages = "1128-1147",
    Keyword = "Parallel, Randomized",
}

@Article{Megiddo:83,
    Ordinal = 160,
    Author = Megiddo,
    Title = {Applying parallel computation algorithms in the design
    of serial algorithms},
    Year = 1983,
    Journal = jacm,
    Volume = 28,
    Pages = {852-865},
}

@PhdThesis{Przytycka:90:PhD,
    Author = Przytycka,
    Title = "Parallel Techniques for Construction of Trees and Related Problems",
    Year = 1990,
    Institution = csubc,
}

 @TechReport{Przytycka:90,
    Ordinal = 163,
    Author = Przytycka,
    Title = "Parallel Techniques for Construction of Trees and Related Problems",
    Year = 1990,
    Month = Oct,
    Number = "90-28",
    Institution = csubc,
}

@TechReport{Valiant:89,
    Ordinal = 164,
    Author = Valiant,
    Title = "General Purpose Parallel Architectures",
    Year = 1989,
    Month = Apr,
    Number = "07-89",
    Institution = Aiken,
}

@InCollection{Valiant:90,
    Ordinal = 165,
    Author = Valiant,
    Title = "General Purpose Parallel Architectures",
    Year = 1990,
    BookTitle = Handbook,
    Chapter = 18,
    Volume = "A",
    Editor = van-Leeuwen,
    Publisher = elsevier,
    Pages = "944-971",
}

@InProceedings{Hagerup:Chrobak:Diks:87,
    Author = Hagerup #&# Chrobak #&# Diks,
    Title = "Optimal Parallel 5-Colouring of Planar Graphs",
    Year = 1987,
    BookTitle = icalp87,
    Orinal = 173,
}

@Article{Pinotti:Pucci:91,
    Ordinal = 174,
    Author = Pinotti #&# Pucci,
    Title = "Parallel Priority Queues",
    Year = 1991,
    Journal = ipl,
    Volume = 40,
    Pages = "33-40",
}

@InProceedings{Pinotti:Pucci:92,
    Author = Pinotti #&# Pucci,
    Title = "Parallel Algorithms for Priority Queue Operations",
    Year = 1992,
    BookTitle = swat92,
}

@Article{Pan:Reif:91,
    Ordinal = 175,
    Author = Pan #&# Reif,
    Title = "The Parallel Computation of Minimum Cost Paths in Graphs by Stream Contraction",
    Year = 1991,
    Journal = ipl,
    Volume = 40,
    Pages = "79-83",
}

@TechReport{Broder:Karlin:Raghavan:Upfal:90,
    Ordinal = 177,
    Author = Broder #&# Karlin #&# Raghavan #&# Upfal,
    Title = "Trading Space for Time in Undirected $s-t$ Connectivity",
    Year = 1990,
    Number = "RJ 7631",
    Institution = IBM-Almaden,
}

@Article{Naor:91,
    Ordinal = 178,
    Author = NaorM,
    Title = "A Lower Bound on Probabilistic Algorithms for Distributive Ring Coloring",
    Year = 1991,
    Journal = siamjdisc,
    Volume = 4,
    Number = 3,
    Pages = "409-412",
}

@Article{Reghbati:Corneil:78,
    Ordinal = 179,
    Author = Reghbati #&# Corneil,
    Title = "Parallel Computations in Graph Theory",
    Year = 1978,
    Journal = sicomp,
    Volume = 7,
    Number = 2,
    Pages = "230-237",
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@TechReport{Atallah:Kosaraju:90,
    Ordinal = 208,
    Author = Atallah #&# Kosaraju,
    Title = "An Efficient Parallel Algorithm for the Row Minima of a Totally Monotone Matrix",
    Year = 1990,
    Number = "CSD-TR-959",
    Institution = Purdue,
}

@InProceedings{Atallah:Kosaraju:91,
    Author = Atallah #&# Kosaraju,
    Title = "An Efficient Parallel Algorithm for the Row Minima of a Totally Monotone Matrix",
    Year = 1991,
    BookTitle = soda91,
    Pages = "394-403",
}

@InProceedings{Aggarwal:Park:88,
    Ordinal = 205,
    Author = Aggarwal #&# ParkJ,
    Title = "Parallel Searching in Multidimensional Monotone Arrays",
    Year = 1988,
    BookTitle = focs88,
    Pages = "497-512",
}

@Article{Aggarwal:Park:91,
    Ordinal = 206,
    Author = Aggarwal #&# ParkJ,
    Title = "Parallel Searching in Multidimensional Monotone Arrays",
    Year = 1991,
    Journal = jalg,
    Note = "To appear",
    Comment = "with notes",
}

@Article{SMAWK:87,
    Ordinal = 207,
    Author = Aggarwal #&# Klawe #&# Moran #&# Wilber,
    Title = "Geometric Applications of a Matrix Searching Algorithm",
    Year = 1987,
    Journal = algorithmica,
    Volume = 2,
    Pages = "209-233",
}

%%%%%%%%%%%%%%%%%%%%%@Article{Bentley:75,
    Ordinal = 180,
    Author = Bentley,
    Title = "Multidimensional Binary Search Trees Used for Associative Searching",
    Year = 1975,
    Journal = cacm,
    Volume = 18,
    Number = 9,
    Pages = "509-517",
}

%%%%%%%%%%%%%%%%%%%%%@InProceedings{Ben-Asher:Peleg:Ramaswami:Schuster:91,
    Ordinal = 181,
    Author = Ben-Asher #&# Peleg #&# Ramaswami #&# Schuster,
    Title = "The Power of Reconfiguration",
    Year = 1991,
    BookTitle = icalp91,
    Pages = "139-150",
}

@Article{Ben-Asher:Peleg:Ramaswami:Schuster:91:J,
    Ordinal = 182,
    Author = Ben-Asher #&# Peleg #&# Ramaswami #&# Schuster,
    Title = "The Power of Reconfiguration",
    Year = 1991,
    BookTitle = jpdc,
}

@TechReport{Anastasio:91,
    Ordinal = 183,
    Author = Anastasio,
    Title = "A Critical Survey of the Literature on Mapping Static Dataflow Programs by Level",
    Year = 1991,
    Number = "SRC-TR-91-040",
    Institution = SRC,
}

@TechReport{Zimmermann:90,
    Ordinal = 184,
    Author = Zimmermann,
    Title = "Automatic Worst Case Complexity Analysis of Parallel Programs",
    Year = 1990,
    Number = "TR-90-066",
    Institution = ICSI,
}

@InProceedings{Leighton:Lisinski:Maggs:91,
    Ordinal = 185,
    Author = Leighton #&# Lisinski #&# Maggs,
    Title = "Empirical Evaluation of Randomly-Wired Multistage Networks",
    Year = 1991,
}

@TechReport{OHRWAB:91,
    Ordinal = 186,
    Author = Orbenic #&# Herbordt #&# Rosenberg #&# Weems #&# Annexstein #&# Baumslag,
    Title = "Using Emulations to Construct High-Performance Virtual Parallel Architectures",
    Year = 1991,
    Number = "91-40",
    Institution = umass,
}

@TechReport{KLMRRS:91,
    Ordinal = 187,
    Author = Koch #&# Leighton #&# Maggs #&# Rao #&# Rosenberg #&# Schwabe,
    Title = "Work-Preserving Emulations of Fixed-Connection Networks",
    Year = 1991,
    Number = "91-114",
    Institution = umass,
}

@InProceedings{Upfal:Wigderson:84,
    Ordinal = 188,
    Author = Upfal #&# Wigderson,
    Title = "How to Share Memory in a distributed System",
    Year = 1984,
    BookTitle = focs84,
    Pages = "171-180",
}

@Article{Kim:Lai:91,
    Ordinal = 189,
    Author = Kim #&# Lai,
    Title = "The Complexity of Congestion-1 Embedding in a Hypercube",
    Year = 1991,
    Journal = jalg,
    Volume = 12,
    Pages = "246-280",
}

@TechReport{Valiant:89:TR,
    Ordinal = 190,
    Author = Valiant,
    Title = "Bulk-Synchronous Parallel Computers",
    Year = 1989,
    Number = "TR-08-89",
    Institution = Aiken,
}

    Author = Valiant,
    Title = "Bulk-Synchronous Parallel Computers",
    Year = 1990,
    Pages =
    Journal = cacm,
}

@TechReport{Valiant:89,
    Ordinal = 191,
    AUTHOR = Valiant,
    TITLE = {Bulk-synchronous parallel computers},
    INSTITUTION = {Harvard University},
    YEAR = {1989},
    NUMBER = {TR-08-89},
    ADDRESS = {Cambridge, Massachusetts},
    MONTH = apr,
    MYNOTE = {Has now appeared in CACM}
}

@Article{Valiant:90:Bulk,
    AUTHOR = Valiant,
    TITLE = {A bridging model for parallel computation},
    JOURNAL = {Communications of the ACM},
    YEAR = {1990},
    VOLUME = {33},
    NUMBER = {8},
    PAGES = {103-111},
    MYNOTE = {Bulk-Synchronous Computer}
}

@Misc{Rosenberg:91,
    Ordinal = 192,
    Author = Rosenberg,
    Title = "Principles of Graph Embedding",
    Year = 1991,
    Note = "Slides' notes",
}

@TechReport{Lin:Pippenger:91,
    Ordinal = 193,
    Author = Lin #&# Pippenger,
    Title = "Parallel Algorithms for Routing in Non-blocking Networks",
    Year = 1991,
    Number = "91-8",
    Institution = csubc,
}

@TechReport{Stamoulis:Tsitsiklis:90:Report,
    Ordinal = 194,
    Author = Stamoulis #&# Tsitsiklis,
    Title = "The Efficiency of Greedy Routing in Hypercubes and Butterflies",
    Year = 1990,
    Number = "LIDS-P-1999",
    Institution = umass,
}

@InProceedings{Stamoulis:Tsitsiklis:90,
    Author = Stamoulis #&# Tsitsiklis,
    Title = "The Efficiency of Greedy Routing in Hypercubes and Butterflies",
    Year = 1990,
    BookTitle = spaa90,
}

@TechReport{Abolhassan:Keller:Paul:91:Report,
    Ordinal = 195,
    Author = Abohassan #&# Keller #&# Paul,
    Title = "On The Cost-Effectiveness and Realization of the Theoretical {PRAM} Model",
    Year = 1991,
    Number = "09/1991",
    Institution = saarbrucken,
}

@InProceedings{Abolhassan:Keller:Paul:91,
    Ordinal = 196,
    Author = Abohassan #&# Keller #&# Paul,
    Title = "On The Cost-Effectiveness and Realization of the Theoretical {PRAM} Model",
    Year = 1991,
    BookTitle = spdp91,
}

@InProceedings{Anderson:Woll:91,
    Ordinal = 197,
    Author = Anderson #&# Woll,
    Title = "Wait-free Parallel Algorithms for the Union-Find Problem",
    Year = 1991,
    BookTitle = spaa91,
    Pages = "370-380",
}

@InProceedings{Aggarwal:Chandra:Snir:87,
    Ordinal = 198,
    Author = Aggarwal #&# Chandra #&# Snir,
    Title = "Hierarchical Memory with Block Transfer",
    Year = 1987,
    BookTitle = focs87,
    Pages = "204-216",
}

@InProceedings{Aggarwal:Chandra:88,
    Ordinal = 199,
    Author = Aggarwal #&# Chandra,
    Title = "Virtual Memory Algorithms",
    Year = 1988,
    BookTitle = stoc88,
    Pages = "173-185",
}

@InProceedings{Aggarwal:Chandra:Snir:89,
    Ordinal = "199a",
    Author = Aggarwal #&# Chandra #&# Snir,
    Title = "On Communication Latency in PRAM Computations",
    Year = 1989,
    BookTitle = spaa89,
    Pages = "11-21",
}

@InProceedings{Alpern:Carter:Feig:90,
    Ordinal = 200,
    Author = Alpern #&# Carter #&# Feig,
    Title = "Uniform Memory Hierarchies",
    Year = 1990,
    BookTitle = focs90,
    Pages = "600-608",
}

@TechReport{Koren:Shasha:91,
    Ordinal = 201,
    Author = Koren #&# Shasha,
    Title = "An Optimal Scheduling ALgorithm with a Competitive Factor for Real-Time Systems",
    Year = 1991,
    Number = 572,
    Institution = courant,
}

@InProceedings{BKRMSR:91,
    Ordinal = 202,
    Author = Barua #&# Koren #&# Rosier #&# Mishra #&# Shasha #&# Raghunathan,
    Title = "On-Line Scheduling in the Presence of Overload",
    Year = 1991,
    BookTitle = focs91,
}

@TechReport{Stankovic:88,
    Ordinal = 203,
    Author = Stankovic,
    Title = "Real-Time Computing Systems: The Next Generation",
    Year = 1988,
    Number = "88-06",
    Institution = umass,
}

@TechReport{Vishkin:91:Report,
    Ordinal = 204,
    Author = Vishkin,
    Title = "Can Parallel Algorithms Enhance Serial Implementation?",
    Year = 1991,
    Number = "UMIACS-TR-91-145, CS-TR-2784",
    Institution = UMIACS,
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%@UnPublished{Gil:Matias:Soda:Revised:91,
    Author = Gil #&# Matias,
    Title = "Fast Hashing on a {PRAM}",
    Year = 1991,
    Note = "Manuscript (Revised version)",
}

@UnPublished{Gil:Matias:HashLogLog:91,
    Author = Gil #&# Matias,
    Title = "Fast Parallel Hashing",
    Year = 1991,
    Note = "Manuscript",
}

@UnPublished{Gil:Matias:Design:92a,
    Author = Gil #&# Matias,
    Title = "Designing Algorithms by Expectations",
    Year = 1992,
    Note = submitted,
}

@Unpublished{Gil:Matias:Policy:94,
    Author = Gil #&# Matias,
    Title = "An effective load balancing policy for geometric decaying
        algorithms",
    Year = 1994,
    Note = submitted,
}

@UnPublished{Matias:Vishkin:Note:92a,
    Author = Matias #&# Vishkin,
    Title= "A Note on Simulations and Integer Sorting",
    Note= "Manuscript",
    Year= 1992
}

@InProceedings{Matias:Vishkin:Note:92,
    Author = Matias #&# Vishkin,
    Title= "A note on reducing parallel model simulations to integer sorting",
    BookTitle= ipps95,
    Year= 1995,
    Note= "To appear",
}

@InProceedings{Gil:Matias:94,
    Author = Gil #&# Matias,
    Title = "Simple Fast Parallel Hashing",
    BookTitle = icalp94,
    Year = 1994,
    Month = Jul,
    Pages = {239-250},
}

@TechReport{Gil:Matias:J94,
    Title = "Simple Fast Parallel Hashing by Oblivious Execution",
    Author = Gil #&# Matias,
    Month = apr,
    Year = 1994,
    Institution = {AT\&T Bell Laboratories},
    Address = {Murray Hill, NJ},
    Note = {Submitted for publication.},
}

@TeChreport{Gibbons:Matias:Ramachandran:93,
    AUTHOR = Gibbons #&# Matias #&# Ramachandran,
    TITLE = {{QRQW}: Accounting for Concurrency in {PRAM}s and
        {A}synchronous {PRAM}s},
    INSTITUTION = {AT\&T Bell Laboratories},
    YEAR = {1993},
    ADDRESS = {Murray Hill, NJ},
    MONTH = mar,
    NOTE = {Revised version.}
}

@InProceedings{Gibbons:Matias:Ramachandran:soda:94,
    AUTHOR = Gibbons #&# Matias #&# Ramachandran,
    TITLE = {The {QRQW PRAM}: Accounting for Contention in Parallel Algorithms},
    BOOKTITLE = soda94,
    YEAR = {1994},
    PAGES = {638-648},
    FADDRESS = {Arlington, Virginia},
    MONTH = jan
}


@UnPublished{Rajasekaran:Ross:91,
    Author = Rajasekaran #&# Ross,
    Title = "Fast Algorithms for Generating Discrete Random Variates
        with Changing Distributions",
    Month = nov,
    Year = 1991,
    Note = submitted,
}

 @UnPublished{Matias:91,
    Author = Matias,
    Title = " Generating Discrete Random Variates with Arbitrarily Changing
        Distributions",
    Month = nov,
    Year = 1991,
    Note = "Manuscript",
}

 @UnPublished{Matias:91:Dice,
    Author = Matias,
    Title = " Rolling a Dice with Varying Biases ",
    Month = nov,
    Year = 1991,
    Note = "Manuscript",
}


 @Book{Bratley:Fox:Schrage:87,
    Author = "Paul Bratley and Bennett L. Fox and Linus E. Schrage",
    Title = "A Guide to Simulation",
    Year = 1987,
    Note = "Second Edition",
    Publisher = "Springer-Verlag",
    Call = "QA76.9.C65B73 1987"
}

@Article{Walker:77,
    Author = "A.J. Walker",
    Title = "An Efficient Method for Generating Discrete Random
        Variables with General Distributions",
    Journal = "ACM Trans. Math. Software",
    Volume = 3,
    Pages = "253-256",
    Year = 1977
}

@Article{Kronmal:Peterson:79,
    Author = "R.A. Kronmal and A.V. {Peterson, Jr.}",
    Title = "On the Alias Method for Generating Random Variables from
        a Discrete Distribution",
    Journal = "Am. Statist.",
    Volume = 33,
    Pages = "214-218",
    Year = 1979
}

@Article{Wong:Easton:80,
    Author = "C. K. Wong and M. C. Easton",
    Title = "An Efficient Method for Weighted Sampling without Replacement",
    Journal = sicomp,
    Volume = 9,
    Number = 1,
    Pages = "111-114",
    Year = 1980
}

 @Book{Law:Kelton:82,
    Author = "Averill M. Law and W. David Kelton",
    Title = "Simulation Modeling and Analysis",
    Year = 1982,
    Publisher = "McGraw-Hill",
    Call = "QA76.9.C65L38 1982"
}

@Article{Berkman:Vishkin:92,
    Author = Berkman #&# Vishkin,
    Title = "On parallel integer merging",
    Year = 1992,
    Journal = infocomp,
    Note = "To appear. Also UMIACS-TR-90-15.1.
    A preliminary version appeared in
O. Berkman, J. JaJa, S. Krishnamurthy, R. Thurimella and U. Vishkin,
Some triply-logarithmic parallel algorithms,
Proc. 31st Annual IEEE Symposium on Foundations of Computer
Science, 1990, 871-881."
}

@Article{Stone:75,
    Author = Stone,
    Title = "Parallel tridiagonal equation solvers",
    Journal = "ACM Trans. on Mathematical Software",
    Volume = 1,
    Number = 4,
    Pages = "289-307",
    Year = 1975,
}

@Article{Fox:90,
    Author = "Bennet L. Fox",
    Title = "Generating Markov-Chain Transitions Quickly: I",
    Journal = "Operations Research Society of America Journal on
        Computing",
    Volume = 2,
    Number = 2,
    Pages = "126-135",
    Year = 1990,
}

@Article{Fox:Young:91,
    Author = "B.L. Fox and A.R. Young",
    Title = "Generating Markov-Chain Transitions Quickly: II",
    Journal = "Operations Research Society of America Journal on
        Computing",
    Volume = 2,
    Number = 1,
    Pages = "3-11",
    Year = 1991,
}

@Article{Heidelberger:Lavenberg:84,
    Author = "P. Heidelberger and S.S. Lavenberg",
    Title = "Computer Performance Evaluation Methodology",
    Journal = "IEEE Transactions on Computers",
    Volume = 33,
    Pages = "1195-1220",
    Year = 1984,
}

@Book{Kleinrock:75,
    Author = "L. Kleinrock",
    Title = "Queueing Systems, Volume 1: Theory",
    Year = 1975,
    Publisher = "John-Wiley and Sons Publishers",
}

@Book{Walrand:88,
    Author = "J. Walrand",
    Title = "An INtroduction to Queueing Netwoks",
    Year = 1988,
    Publisher = "Prentice Hall",
}


@Book{Manber:89,
    Author= "Udi Manber",
    Title="Introduction To Algorithms, A Creative Approach",
    Publisher= "Addison-Wesley",
    Year= "1989",
    Call= "QA76.9.D35M36 1989"
}

@TechReport{Prindiville:Rajasekaran:Ross:91,
    Author = "M. Prindiville and S. Rajasekaran and K.W. Ross",
    Title = "Efficient Simulation of Large-Scale Loss Netwroks",
    Year = 1991,
    Number = "MS-CIS-91-62",
    Institution = "Department of Computer Science, University of Pennsylvania",
    Month = aug,
}

@TechReport{Rajasekaran:Reif:87,
    Author = "S. Rajasekaran and J.H. Reif",
    Title = "Derivation of Randomized Sorting and Selection Algorithms",
    Year = 1987,
    Institution = "Aiken Computing Lab, Harvard University",
    Month = mar,
}

@Book{Feller:68,
    Author= "William Feller",
    Title= "An Introduction to Probability Theory and Its
    Applications",
    Publisher= "John Wiley",
    Volume= "I",
    Year= "1968"
}
 @UnPublished{AGMKW:91,
    Ordinal = 228,
    Author = Alt #&# Guibas #&# Mehlhorn #&# Karp #&# Wigderson,
    Title = "A method for Obtaining Randomized Algorithms with Small
        Tail Probabilities",
    Month = sep,
    Year = 1991,
    Note = "Manuscript",
}

 @UnPublished{Martingales,
    Ordinal = 229,
    Author = Alon #&# Spencer #&# Karp,
    Title = "Notes on {M}artingales from {A}lon-{S}pencer and from {K}arp",
    Year = 1991,
    Note = "Manuscript",
}

@UnPublished{Alon:Galil:Margalit:Naor:92,
    Ordinal = 230,
    Author = Alon #&# Galil #&# Margalit #&# Naor,
    Title = "Witnesses for Boolean Matrix Multiplication and for
        Shortest Paths",
    Year = 1992,
    Note = "Manuscript",
}

@UnPublished{Lyuu:92,
    Ordinal = 231,
    Author = Lyuu,
    Title = "Fast Fault-Tolerant Parallel Communication and On-Line
        Maintenance for Hypercubes Using Information Dispersal",
    Year = 1992,
    Note = "Manuscript",
    Keywords = "IDA",
}

@TechReport{Sairam:Vitter:Tamassia:91,
    Ordinal = 245,
    Author = Sairam #&# Vitter #&# Tamassia,
    Title = "A Complexity Teoretic Approach to Incremental Computation",
    Year = 1991,
    Number = "CS-91-66",
    Institution = Brown,
    Month = nov,
}

@Book{Bentley:82,
    Author= Bentley,
    Title= "Writing Efficient Progams",
    Publisher= "Prentice Hall",
    Year= "1982",
    Call = " QA76.6.B455 1982"
}

@Book{Bentley:86,
    Author= Bentley,
    Title= "Programming Pearls",
    Publisher= "Addison-Wesley",
    Year= "1986",
    Call = "QA76.6.B453 1986"
}

@Book{Bentley:88,
    Author= Bentley,
    Title= "More Programming Pearls: Confessions of a Coder",
    Publisher= "Addison-Wesley",
    Year= "1988",
    Call= "QA76.6.B452 1988"
}

@Book{Berlioux:Bizard:86,
    Author= "Pierre Berlioux and Philippe Bizard",
    Title= "Algorithms: the Construction, Proof, and Analysis of Programs",
    Publisher= "John Wiley \& Sons",
    Year= "1986",
    Call= "QA76.6.B471913 1986"
}

@UnPublished{Vitter:92:Private,
    Author = Vitter,
    Note= "Private Communication",
    Year= 1992
}

@UnPublished{Vitter:Ni:92,
    Author = Vitter #&# Ni,
    Title = "Dynamic Generation of Random Variables",
    Note= "Manuscript",
    Year= 1992
}

@InProceedings{Matias:Vitter:Ni:93,
    Author = Matias #&# Vitter #&# Ni,
    Title = "Dynamic Generation of Random Variates",
    BookTitle = soda93,
    Pages = "361-370",
    Year= 1993
}

@Article{Ahrens:Dieter:72,
    Author = "J. H. Ahrens and U. Dieter",
    Title = "Computer Methods for Sampling from the Exponential and
        Normal Distributions",
    Journal = cacm,
    Volume = 15,
    Pages = "873-882",
    Year = 1972,
}

@Article{Ahrens:Dieter:74,
    Author = "J. H. Ahrens and U. Dieter",
    Title = "Computer Methods for Sampling from Gamma, Beta, Poisson
        and Binomial Distributions",
    Journal = "Computing",
    Volume = 12,
    Pages = "223-246",
    Year = 1974,
}

@UnPublished{Matias:Vishkin:Note:91,
    Author = Matias #&# Vishkin,
    Title= "A Note on Simulations and Integer Sorting",
    Note= "Manuscript",
    Year= 1991
}

@InProceedings{Mansour:Nisan:Tiwari:90,
    Author = "Yishay Mansour and Noam Nisan and Prasoon Tiwari",
    Title = "The Computational Complexity of Universal Hashing",
    BookTitle = stoc90,
    Pages = "235-243",
    Year = 1990,
}

@PhdThesis{Wu:91:PhD,
    Author = "Michael M. Wu",
    Title = "Asynchronous Algorithms for Shared Memory Machines",
    Year = 1991,
    School = "University of Illinois at Urbana-Champaign",
}

@Article{Kruskal:Rudolph:Snir:Algorithmica:90,
    Author = Kruskal #&# Rudolph #&# Snir,
    Title = "Efficient Parallel Algorithms for Graph Problems",
    Journal = algorithmica,
    Volume = 5,
    Pages = "43-64",
    Year = 1990,
}

@InProceedings{Johnson:Metaxas:91,
    Author = Johnson #&# Metaxas,
    Title = "Connected Components in ${O}(\log^{3/2}|V|)$ Parallel
        Time for the {CREW} {PRAM}",
    BookTitle = focs91,
    Pages = "688-697",
    Year = 1991,
}

@InProceedings{Ben-Amram:Galil:91,
    Author = Ben-Amram #&# Galil,
    Title = "Lower Bounds for Data Structure Problems on RAMs",
    BookTitle = focs91,
    Pages = "622-631",
    Year = 1991,
}

@InProceedings{Guibas:Salesin:Stolfi:89,
    Author = Guibas #&# Salesin #&# Stolfi,
    Title = "Epsilon Geometry: Building Robust Algorithms from
        Imprecise Computations",
    BookTitle = scg89,
    Year = 1989,
    Pages = "208-217",
}

@InProceedings{Fortune:Milenkovic:91,
    Author = Fortune #&# Milenkovic,
    Title = "Numerical Stability of Algorithms for Line Arrangements",
    BookTitle = scg91,
    Year = 1991,
    Pages = "334-341",
}

@InProceedings{Chaudhuri:Radhakrishnan:92,
    Author = Chaudhuri #&# Radhakrishnan,
    Title = "The Complexity of Parallel Prefix Problems on Small
        Domains",
    BookTitle = focs92,
    Year = 1992,
}

@InProceedings{Chaudhuri:93,
    Author = Chaudhuri,
    Title = "A Lower Bound for Linear Approximate Compaction",
    BookTitle = istcs93,
    Year = 1993,
    Pages = "25-32",
}

@InProceedings{Chaudhuri:93:FOCS,
    Author = Chaudhuri,
    Title = "Sensitive Functions and Approximate Problems",
    BookTitle = focs93,
    Year = 1993,
    Pages = "186-193",
}

@InProceedings{Dietzfelbinger:Kutylowski:Reischuk:90,
    Author = Dietzfelbinger #&# Kutylowski #&# Reischuk,
    Title = "Exact Time Bounds for Computing Boolean Functions on
    {PRAM}s Without Simultaneous Writes",
    BookTitle = spaa90,
    Pages = "125-135",
    Year = 1990,
}

@Article{Dietzfelbinger:Kutylowski:Reischuk:94,
    Author = Dietzfelbinger #&# Kutylowski #&# Reischuk,
    Title = {Exact Lower Time Bounds for Computing Boolean
        Functions on {CREW} {PRAM}s},
    Journal = jcss,
    Year = {1994},
    Volume = {48},
    Number = {2},
    Pages = {231-254}
}

@Article{ACG:89,
    Author= "Atallah, M. and Cole, R. and M. Goodrich",
    Title= "Cascading divide-and-conquer: a technique for designing
    Parallel algorithms",
    Journal= "SIAM J. Computing",
    Volume= "18(3)",
    Year= "1989",
    Pages= "499-532"}

@InProceedings{Ghouse:Goodrich:91,
    Author = "M.~Ghouse and M.T.~Goodrich",
    Title = "In-Place Techniques for Parallel Convex Hull Algorithms",
    Year = 1991,
    BookTitle = spaa91,
    Pages = "192-203",
}

@Book{Hillis:85,
    Author = "W.D.~Hillis",
    Title = "The Connection Machine",
    Year = 1985,
    Publisher = "The MIT Press (Cambridge, Mass.",
}

@UnPublished{Hagerup:Raman:92:Private,
    Author = Hagerup #&# Raman,
    Note = "Private communication through Rajeev Raman",
    Year = 1992,
}

@InProceedings{Hagerup:Raman:92,
    Author = Hagerup #&# Raman,
    Title = "Waste Makes Haste: Tight Bounds for Loose Parallel Sorting",
    BookTitle = focs92,
    Pages = "628-637",
    Year = 1992,
}

@InProceedings{Hagerup:93,
    Author = Hagerup,
    Title = "Fast Deterministic Processor Allocation",
    BookTitle = soda93,
    Pages = "1-10",
    Year = 1993,
}

@InProceedings{Hagerup:Raman:93,
    Author = Hagerup #&# Raman,
    Title = "Fast Deterministic Approximate and Exact Parallel Sorting",
    BookTitle = spaa93,
    Pages = "346-355",
    Year = 1993,
}

@TechReport{Goodrich:Matias:Vishkin:JHU:92,
    Author = Goodrich #&# Matias #&# Vishkin,
    Title = "On Approximate Parallel Prefix and Padded Integer Sorting",
    Year = 1992,
    Number = "JHU-92/13",
    Institution = "The Johns Hopkins Univ.",
    Month = jun,
}

@TechReport{Goodrich:Matias:Vishkin:92,
    Author = Goodrich #&# Matias #&# Vishkin,
    Title = "On Approximate Parallel Prefix and Padded Integer Sorting",
    Year = 1992,
    Number = "JHU-92/13",
    Institution = "The Johns Hopkins Univ.",
    Month = jun,
    Note1 = "To be presented in the {\em Seventh International Parallel
    Processing Symposium {\rm (IPPS)}}, April 1993"
}

@UnPublished{Goodrich:Matias:Vishkin:In:92,
    Author = Goodrich #&# Matias #&# Vishkin,
    Title = "In preparation",
    Year = 1992,
    Month = sep,
}

@InProceedings{Goodrich:Matias:Vishkin:93,
    Author = Goodrich #&# Matias #&# Vishkin,
    Title = "On Approximate Parallel Prefix and Padded Integer Sorting",
    BookTitle = ipps93,
    Pages = "318-325",
    Year = 1993,
    Month = apr,
}

@InProceedings{Goodrich:Matias:Vishkin:94,
    Author = Goodrich #&# Matias #&# Vishkin,
    Title = "Optimal Parallel Approximation Algorithms for Prefix Sums
        and Integer Sorting",
    BookTitle = soda94,
    Year = 1994,
    Month = jan,
    Pages = "241-250",
}

@InProceedings{Goldberg:Zwick:95,
    Author = GoldbergT #&# Zwick,
    Title = "Optimal Deterministic Approximate Parallel Prefix Sums
        and Their Applications",
    BookTitle = istcs95,
    Year = 1995,
    Month = jan,
    Note = "To appear",
}

@UnPublished{Goldberg:Zwick:95A,
    Author = GoldbergT #&# Zwick,
    Title = "Optimal Deterministic Approximate Parallel Prefix Sums
        and Their Applications",
    Note = "These proceedings",
}

@Book{nsf:grandchallenge,
  key = "NSF",
  title =       "Grand Challenges: High Performance Computing and
                          Communications",
  publisher =   "A Report by the Committee on Physical, Mathematical
and
                          Engineering Sciences, NSF/CISE",
  year =        1991,
  address =     "1800 G~Street NW, Washington, D.C. 20550",
  keyword = "grand challenges, parallel computing"
}

@InProceedings{May:91,
    Author = May,
    Title = "The Next Generation Transputers and Beyond",
    BookTitle = edmcc2,
    Year = 1991,
    Pages = "7-22",
    Place = "Munich",
    Month = apr,
}


@Article{Lubiw:Racz:91,
    Author= Lubiw #&# Racz,
    Title= "A Lower Bound for the Integer Element Distinctness Problem",
    Journal= infocomp,
    Volume= "94",
    Number= "1",
    Year= "1991",
    Pages= "83-92"}
}

@InProceedings{Matias:93:CCCG,
    Author = Matias,
    Title = "Semi-Dynamic Closest-Pair Algorithms",
    BookTitle = cccg93,
    Year = 1993,
    Pages = "264-271",
    Place = "Waterloo",
    Month = aug,
}

@INCOLLECTION{Rajasekaran:Sen:93,
    AUTHOR = Rajasekaran #&# Sen,
    TITLE = {Random Sampling Techniques and Parallel Algorithm Design},
    BOOKTITLE = {A Synthesis of Parallel Algorithms},
    PUBLISHER = {Morgan-Kaufmann},
    YEAR = {1993},
    EDITOR = {J. H. Reif},
    CHAPTER = {9},
    PAGES = {411-451},
    ADDRESS = {San Mateo, CA}
}

@UnPublished{Berkman:Gibbons:Matias:93,
    Author = Berkman #&# Gibbons #&# Matias,
    Title = "On the Power of Randomization for the {C}ommon {PRAM}",
    Year = {1993},
    Month = Nov,
    Note = "Manuscript",
}

@InProceedings{Berkman:Gibbons:Matias:95,
    Author = Berkman #&# Gibbons #&# Matias,
    Title = "On the Power of Randomization for the {C}ommon {PRAM}",
    Year = {1995},
    Month = Jan,
    Pages = {229-240},
    BookTitle = istcs95,
}

@InProceedings{Chandra:Stockmeyer:Vishkin:82,
    Author = Chandra #&# Stockmeyer #&# Vishkin,
    Title = "A Complexity Theory for Unbounded Fan-In Parallelism",
    Year = 1982,
    Month = Oct,
    BookTitle = focs82,
    Pages = "1--13",
}

@InProceedings{Matias:Vitter:Young:94,
    Author = Matias #&# Vitter #&# Young,
    Title = "Approximate Data Structures  with Applications",
    BookTitle = soda94,
    Year = 1994,
    Month = jan,
    Pages = "187-194",
}

@InProceedings{Klein:Sairam:92,
    Author = Klein #&# Sairam,
    Title = "A Parallel Randomized Approximation Scheme for Shortest Paths",
    BookTitle = stoc92,
    Year = 1994,
    Month = may,
    Pages = "750-758",
}


@INCOLLECTION{Fich:93,
    AUTHOR = Fich,
    TITLE = {The Complexity of Computation on the Parallel Random Access Machine},
    BOOKTITLE = {A Synthesis of Parallel Algorithms},
    PUBLISHER = {Morgan-Kaufmann},
    YEAR = {1993},
    EDITOR = Reif,
    CHAPTER = {20},
    PAGES = {843-899},
    ADDRESS = {San Mateo, CA}
}

@InProceedings{MacKenzie:IPPS93,
    Title = "A Separation Between Reconfigurable Mesh Models",
    Author = MacKenzie,
    BookTitle = ipps93,
    Pages = "84--88",
    Year = 1993
}

@TechReport{Matias:Schuster:93,
    Author = Matias #&# Schuster,
    Title = "On the Power of the $2 \times n$ Reconfigurable Mesh",
    INSTITUTION = {AT\&T Bell Laboratories},
    YEAR = {1993},
    ADDRESS = {Murray Hill, NJ}
}

@Article{Droste:Gastin:99,
    Author = "Manfred Droste and Paul Gastin",
    Title = "The Kleene-Sch{\"{u}}tzenberger Theorem for Formal Power Series in Partially Commuting Variables",
    Journal = "Information and Computation",
    Year = 1999,
    Volume = 153,
    Pages = "47--80"
}

@InCollection{Mateescu:Salomaa:97,
    Author = "Alexandru Mateescu and Arto Salomaa",
    Title = "Formal Languages: an Introduction and a Synopsis",
    Booktitle = "Handbook of Formal Languages",
    Year = 1997,
    Editor = "G. Rozenberg and A. Salomaa",
    Volume = 1,
    Pages = "1--39",
    Publisher = "Springer-Verlag",
    Address = "Berlin, Heidelberg"
}

@InProceedings{Hopkins:Kozen:99,
    Author = "Mark W. Hopkins and Dexter C. Kozen",
    Title = "Parikh's Theorem in Commutative Kleene Algebra",
    BookTitle = "Fourteenth Annual IEEE Symposium on Logic in Computer Science (LICS'99)",
    Year = 1999,
    Pages = "394--401",
    Month = Jul
}

@Article{Droogenbroeck:Talbot:96,
    Ordinal = 246,
    Author = "Fast Computation of Morphological Operations with Arbitrary Structuring Elements",
    Journal = "Pattern Recognition Letters",
    Year = 1996,
    Volume = 17,
    Pages = "1451--1460"
}

@Article{Hsu:75,
    Ordinal = 247,
    Author = "Harry T. Hsu",
    Title = "An Algorithm for Finding a Minimal Equivalent Graph of a Digraph",
    Journal = "Journal of the Association for Computing Machinery",
    Year = 1975,
    Month = Jan,
    Volume = 22,
    Number = 1,
    Pages = "11--16"
}

@Article{Moyles:Thompson:69,
    Ordinal = 248,
    Author = "Dennis M. Moyles and Gerald L. Thompson",
    Title = "An Algorithm for Finding a Minimal Equivalent Graph of a Digraph",
    Journal = "Journal of the Association for Computing Machinery",
    Year = 1969,
    Month = Jul,
    Volume = 16,
    Number = 3,
    Pages = "455--460"
}

@TechReport{Goldin:Wegner:99,
    Ordinal = 249,
    Author = "Dina Goldin and Peter Wegner",
    Title = "Behavior and Expressiveness of Persistent Turing Machines",
    Institution = "Brown University",
    Year = 1999,
    Number = "99-14"
}