%%% -*-BibTeX-*-
%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nelson H. F. Beebe",
%%% version = "2.00",
%%% date = "15 July 2005",
%%% time = "17:05:27 MDT",
%%% filename = "focs1990.bib",
%%% address = "University of Utah
%%% Department of Mathematics, 110 LCB
%%% 155 S 1400 E RM 233
%%% Salt Lake City, UT 84112-0090
%%% USA",
%%% telephone = "+1 801 581 5254",
%%% FAX = "+1 801 581 4148",
%%% URL = "http://www.math.utah.edu/~beebe",
%%% checksum = "63116 8367 31305 270935",
%%% email = "beebe at math.utah.edu, beebe at acm.org,
%%% beebe at computer.org (Internet)",
%%% codetable = "ISO/ASCII",
%%% keywords = "bibliography; BibTeX; Foundations of Computer
%%% Science (FOCS)",
%%% supported = "yes",
%%% docstring = "This is a COMPLETE bibliography of
%%% publications in the annual IEEE symposia on
%%% the Foundations of Computer Science (CODEN
%%% ASFPDV, ISSN 0272-5428) for the decade
%%% 1990--1999.
%%%
%%% At version 2.00, the year coverage looked like
%%% this:
%%%
%%% 1990 ( 91) 1994 ( 73) 1998 ( 80)
%%% 1991 ( 85) 1995 ( 74) 1999 ( 68)
%%% 1992 ( 77) 1996 ( 66)
%%% 1993 ( 74) 1997 ( 64)
%%%
%%% InProceedings: 742
%%% Proceedings: 10
%%%
%%% Total entries: 752
%%%
%%% The checksum field above contains a CRC-16
%%% checksum as the first value, followed by the
%%% equivalent of the standard UNIX wc (word
%%% count) utility output of lines, words, and
%%% characters. This is produced by Robert
%%% Solovay's checksum utility.",
%%% }
%%% ====================================================================
%%% ====================================================================
%%% Acknowledgement abbreviations:
@String{ack-nhfb = "Nelson H. F. Beebe,
Center for Scientific Computing,
University of Utah,
Department of Mathematics, 322 INSCC,
155 S 1400 E RM 233,
Salt Lake City, UT 84112-0090, USA,
Tel: +1 801 581 5254,
FAX: +1 801 585 1640, +1 801 581 4148,
e-mail: \path|beebe@math.utah.edu|,
\path|beebe@acm.org|,
\path|beebe@computer.org|,
\path|beebe@ieee.org| (Internet),
URL: \path|http://www.math.utah.edu/~beebe/|"}
%%% ====================================================================
%%% Publisher abbreviations:
@String{pub-IEEE = "IEEE Computer Society Press"}
@String{pub-IEEE:adr = "1109 Spring Street, Suite 300,
Silver Spring, MD 20910, USA"}
%%% ====================================================================
%%% Bibliography entries:
@InProceedings{Lund:1990:AMI,
author = "C. Lund and L. Fortnow and H. Karloff and N. Nisan",
title = "Algebraic methods for interactive proof systems",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "2--10",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Shamir:1990:IIP,
author = "A. Shamir",
title = "{IP}={PSPACE} (interactive proof=polynomial space)",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "11--15",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Babai:1990:NET,
author = "L. Babai and L. Fortnow and C. Lund",
title = "Nondeterministic exponential time has two-prover
interactive protocols",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "16--25",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Babai:1990:CHP,
author = "L. Babai and L. Fortnow",
title = "A characterization of {Hash P} by arithmetic straight
line programs",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "26--34",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Dolev:1990:PSM,
author = "D. Dolev and C. Dwork and O. Waarts and M. Yung",
title = "Perfectly secure message transmission",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "36--45",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Alon:1990:CFG,
author = "N. Alon and M. Naor",
title = "Coin-flipping games immune against linear-sized
coalitions",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "46--54",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Attiya:1990:WFA,
author = "H. Attiya and N. Lynch and N. Shavit",
title = "Are wait-free algorithms fast?",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "55--64",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Awerbuch:1990:DPA,
author = "B. Awerbuch and M. Saks",
title = "A dining philosophers algorithm with polynomial
response time",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "65--74",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Du:1990:APL,
author = "D.-Z. Du and F. K. Hwang",
title = "An approach for proving lower bounds: solution of
{Gilbert-Pollak}'s conjecture on {Steiner} ratio",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "76--85",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Formann:1990:DGP,
author = "M. Formann and T. Hagerup and J. Haralambides and M.
Kaufmann and F. T. Leighton and A. Simvonis and E.
Welzl and G. Woeginger",
title = "Drawing graphs in the plane with high resolution",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "86--95",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Cheng:1990:NRD,
author = "S. W. Cheng and R. Janardan",
title = "New results on dynamic planar point location",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "96--105",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Reif:1990:CCO,
author = "J. H. Reif and J. D. Tygar and A. Yoshida",
title = "The computability and complexity of optical beam
tracing",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "106--114",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Chang:1990:ASM,
author = "W. I. Chang and E. L. Lawler",
title = "Approximate string matching in sublinear expected
time",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "116--124",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Li:1990:TDS,
author = "M. Li",
title = "Towards a {DNA} sequencing theory (learning a
string)",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "125--134",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Colussi:1990:ECS,
author = "L. Colussi and Z. Galil and R. Giancarlo",
title = "On the exact complexity of string matching",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "135--144",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Dubiner:1990:FTP,
author = "M. Dubiner and Z. Galil and E. Magen",
title = "Faster tree pattern matching",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "145--150",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Neff:1990:SPP,
author = "C. A. Neff",
title = "Specified precision polynomial root isolation is in
{NC}",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "152--162",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kosaraju:1990:TPT,
author = "S. R. Kosaraju and A. L. Delcher",
title = "A tree-partitioning technique with applications to
expression evaluation and term matching",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "163--172",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Lagergren:1990:EPA,
author = "J. Lagergren",
title = "Efficient parallel algorithms for tree-decomposition
and related problems",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "173--182",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Angluin:1990:LCH,
author = "D. Angluin and M. Frazier and L. Pitt",
title = "Learning conjunctions of {Horn} clauses",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "186--192",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Goldman:1990:EIC,
author = "S. A. Goldman and M. J. Kearns and R. E. Schapire",
title = "Exact identification of circuits using fixed points of
amplification functions",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "193--202",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Maass:1990:CLC,
author = "W. Maass and G. Turan",
title = "On the complexity of learning from counterexamples and
membership queries",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "203--210",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Blum:1990:SDF,
author = "A. Blum",
title = "Separating distribution-free and mistake-bound
learning models over the {Boolean} domain",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "211--218",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Chazelle:1990:TSP,
author = "B. Chazelle",
title = "Triangulating a simple polygon in linear time",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "220--230",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Bern:1990:PGM,
author = "M. Bern and D. Eppstein and J. Gilbert",
title = "Provably good mesh generation",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "231--241",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Chazelle:1990:CCC,
author = "B. Chazelle and H. Edelsbrunner and L. J. Guibas and
R. Pollack and R. Seidel and M. Sharir and J.
Snoeyink",
title = "Counting and cutting cycles of lines and rods in
space",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "242--251",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{deBerg:1990:HSR,
author = "M. de Berg and M. H. Overmars",
title = "Hidden surface removal for axis-parallel polyhedra",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "252--261",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Leighton:1990:FSC,
author = "T. Leighton and C. G. Plaxton",
title = "A (fairly) simple circuit that (usually) sorts",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "264--274",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Assaf:1990:FTS,
author = "S. Assaf and E. Upfal",
title = "Fault tolerant sorting network",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "275--284",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kaklamanis:1990:ATB,
author = "C. Kaklamanis and A. R. Karlin and F. T. Leighton and
V. Milenkovic and P. Raghavan and S. Rao and C.
Thomborson and A. Tsantilas",
title = "Asymptotically tight bounds for computing with faulty
arrays of processors",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "285--296",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Bay:1990:DLR,
author = "P. Bay and G. Bilardi",
title = "Deterministic on-line routing on area-universal
networks",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "297--306",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Feige:1990:MNI,
author = "U. Feige and D. Lapidot and A. Shamir",
title = "Multiple non-interactive zero knowledge proofs based
on a single random string",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "308--317",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Goldreich:1990:SPA,
author = "O. Goldreich and R. Impagliazzo and L. Levin and R.
Venkatesan and D. Zuckerman",
title = "Security preserving amplification of hardness",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "318--326",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Sturtivant:1990:EIB,
author = "C. Sturtivant and Z.-L. Zhang",
title = "Efficiently inverting bijections given by straight
line programs",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "327--334",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Chor:1990:PCI,
author = "B. Chor and M. Gereb-Graus and E. Kushilevitz",
title = "Private computations over the integers",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "335--344",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Lovasz:1990:MRM,
author = "L. Lovasz and M. Simonovits",
title = "The mixing rate of {Markov} chains, an isoperimetric
inequality, and computing the volume",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "346--354",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Deng:1990:EUG,
author = "X. Deng and C. H. Papadimitriou",
title = "Exploring an unknown graph",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "355--361",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kannan:1990:IEH,
author = "S. Kannan and T. Warnow",
title = "Inferring evolutionary history from {DNA} sequences",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "362--371",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Fich:1990:P,
author = "F. E. Fich and J. I. Munro and P. V. Poblete",
title = "Permuting",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "372--379",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kearns:1990:EDF,
author = "M. J. Kearns and R. E. Schapire",
title = "Efficient distribution-free learning of probabilistic
concepts",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "382--391",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Aldous:1990:MEV,
author = "D. Aldous and U. Vazirani",
title = "A {Markovian} extension of {Valiant}'s learning
model",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "392--396",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Paturi:1990:TCP,
author = "R. Paturi and M. E. Saks",
title = "On threshold circuits for parity",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "397--404",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Fulk:1990:RSI,
author = "M. A. Fulk",
title = "Robust separations in inductive inference",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "405--410",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Abrahamson:1990:TST,
author = "K. Abrahamson",
title = "A time-space tradeoff for {Boolean} matrix
multiplication",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "412--419",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Beame:1990:CST,
author = "P. Beame and M. Tompa and P. Yan",
title = "Communication-space tradeoffs for unrestricted
protocols",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "420--428",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Beame:1990:TST,
author = "P. Beame and A. Borodin and P. Raghavan and W. L.
Ruzzo and M. Tompa",
title = "Time-space tradeoffs for undirected graph traversal",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "429--438",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Istrail:1990:CGU,
author = "S. Istrail",
title = "Constructing generalized universal traversing
sequences of polynomial size for graphs with small
diameter",
crossref = "IEEE:1990:PAS",
volume = "1",
pages = "439--448",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Fiat:1990:CSA,
author = "A. Fiat and Y. Rabani and Y. Ravid",
title = "Competitive $k$-server algorithms",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "454--463",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Vishwanathan:1990:ROG,
author = "S. Vishwanathan",
title = "Randomized online graph coloring",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "464--469",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Irani:1990:CIG,
author = "S. Irani",
title = "Coloring inductive graphs on-line",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "470--479",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Cole:1990:OAF,
author = "R. Cole and A. Raghunathan",
title = "Online algorithms for finger searching",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "480--489",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Awerbuch:1990:COM,
author = "B. Awerbuch and I. Cidon and S. Kutten",
title = "Communication-optimal maintenance of replicated
information",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "492--502",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Awerbuch:1990:SP,
author = "B. Awerbuch and D. Peleg",
title = "Sparse partitions",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "503--513",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Awerbuch:1990:NSP,
author = "B. Awerbuch and D. Peleg",
title = "Network synchronization with polylogarithmic
overhead",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "514--522",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Zuckerman:1990:GWR,
author = "D. Zuckerman",
title = "General weak random sources",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "534--543",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Alon:1990:SCA,
author = "N. Alon and O. Goldreich and J. Hastad and R.
Peralta",
title = "Simple construction of almost $k$-wise independent
random variables",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "544--553",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Blum:1990:STA,
author = "A. Blum",
title = "Some tools for approximate $3$-coloring",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "554--562",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Bellare:1990:RIP,
author = "M. Bellare and O. Goldreich and S. Goldwasser",
title = "Randomness in interactive proofs",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "563--572",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Alon:1990:PLP,
author = "N. Alon and N. Megiddo",
title = "Parallel linear programming in fixed dimension almost
surely in constant time",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "574--582",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Vaidya:1990:RPC,
author = "P. M. Vaidya",
title = "Reducing the parallel complexity of certain linear
programming problems",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "583--589",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Martel:1990:APA,
author = "C. Martel and R. Subramonian and A. Part",
title = "Asynchronous {PRAM}s are (almost) as good as
synchronous {PRAM}s",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "590--599",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Alpern:1990:UMH,
author = "B. Alpern and L. Carter and E. Feig",
title = "Uniform memory hierarchies",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "600--608",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Hastad:1990:PSD,
author = "J. Hastad and M. Goldmann",
title = "On the power of small-depth threshold circuits",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "610--618",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Yao:1990:ATC,
author = "A. C.-C. Yao",
title = "{ON} {ACC} and threshold circuits",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "619--627",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Smolensky:1990:IAF,
author = "R. Smolensky",
title = "On interpolation by analytic functions with special
properties and some weak lower bounds on the size of
circuits with symmetric gates",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "628--631",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Bruck:1990:PTF,
author = "J. Bruck and R. Smolensky",
title = "Polynomial threshold functions, {AC} functions and
spectrum norms",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "632--641",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Paterson:1990:FCS,
author = "M. S. Paterson and N. Pippenger and U. Zwick",
title = "Faster circuits and shorter formulae for multiple
addition, multiplication and symmetric {Boolean}
functions",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "642--650",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Harel:1990:DPN,
author = "D. Harel and D. Raz",
title = "Deciding properties of nonregular programs",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "652--661",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Lincoln:1990:DPP,
author = "P. Lincoln and J. Michell and A. Scedrov and N.
Shankar",
title = "Decision problems for propositional linear logic",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "662--671",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Maler:1990:TBC,
author = "O. Maler and A. Pnueli",
title = "Tight bounds on the complexity of cascaded
decomposition of automata",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "672--682",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kaminski:1990:FMA,
author = "M. Kaminski and N. Francez",
title = "Finite-memory automata",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "683--688",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Lynch:1990:PSA,
author = "J. F. Lynch",
title = "Probabilities of sentences about very sparse random
graphs",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "689--696",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Naor:1990:FAO,
author = "D. Naor and D. Gusfield and C. Martel",
title = "A fast algorithm for optimally increasing the
edge-connectivity",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "698--707",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Frank:1990:AGM,
author = "A. Frank",
title = "Augmenting graphs to meet edge-connectivity
requirements",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "708--718",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Fredman:1990:TDA,
author = "M. L. Fredman and D. E. Willard",
title = "Trans-dichotomous algorithms for minimum spanning
trees and shortest paths",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "719--725",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Klein:1990:ATM,
author = "P. Klein and A. Agrawal and R. Ravi and S. Rao",
title = "Approximation through multicommodity flow",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "726--737",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Even:1990:CSD,
author = "S. Even and A. Litman and P. Winkler",
title = "Computing with snakes in directed networks of
automata",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "740--745",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Pneuli:1990:DRS,
author = "A. Pneuli and R. Rosner",
title = "Distributed reactive systems are hard to synthesize",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "746--757",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Luo:1990:CCA,
author = "Z.-Q. Luo and J. N. Tsitsiklis",
title = "Communication complexity of algebraic computation",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "758--765",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Canetti:1990:BTB,
author = "R. Canetti and O. Goldreich",
title = "Bounds on tradeoffs between randomness and
communication complexity",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "766--775",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Toda:1990:CFM,
author = "S. Toda",
title = "The complexity of finding medians",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "778--787",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Buss:1990:PCA,
author = "S. Buss and C. H. Papadimitriou and N. J. Tsitsiklis",
title = "On the predictability of coupled automata: an allegory
about chaos",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "788--793",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Papadimitriou:1990:GTL,
author = "C. H. Papadimitriou",
title = "On graph-theoretic lemmata and complexity classes",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "794--801",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Gurevich:1990:MDP,
author = "Y. Gurevich",
title = "Matrix decomposition problem is complete for the
average case",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "802--811",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Impagliazzo:1990:NBW,
author = "R. Impagliazzo",
title = "No better ways to generate hard {NP} instances than
picking uniformly at random",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "812--821",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Koscielski:1990:CUF,
author = "A. Koscielski and L. Pacholski",
title = "Complexity of unification in free groups and free
semi-groups",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "824--829",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Vallee:1990:LRA,
author = "B. Vallee and P. Flajolet",
title = "The lattice reduction algorithm of {Gauss}: an average
case analysis",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "830--839",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Horng:1990:SNR,
author = "G. Horng and M.-D. A. Huang",
title = "Simplifying nested radicals and solving polynomials by
radicals in minimum depth",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "847--856",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Babai:1990:DFG,
author = "L. Babai and G. Hetyei and W. M. Kantor and A.
Lubotzky and A. Seress",
title = "On the diameter of finite groups",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "857--865",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Berkman:1990:STL,
author = "O. Berkman and J. Jaja and S. Krishnamurthy and R.
Thurimella and U. Vishkin",
title = "Some triply-logarithmic parallel algorithms",
crossref = "IEEE:1990:PAS",
volume = "2",
pages = "871--881",
year = "1990",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Feige:1991:ACA,
author = "U. Feige and S. Goldwasser and L. Lovasz and S. Safra
and M. Szegedy",
title = "Approximating clique is almost {NP}-complete",
crossref = "IEEE:1991:PAS",
pages = "2--12",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Lapidot:1991:FPM,
author = "D. Lapidot and A. Shamir",
title = "Fully parallelized multi prover protocols for
{NEXP}-time",
crossref = "IEEE:1991:PAS",
pages = "13--18",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Beigel:1991:LET,
author = "R. Beigel and M. Bellare and J. Feigenbaum and S.
Goldwasser",
title = "Languages that are easier than their proofs",
crossref = "IEEE:1991:PAS",
pages = "19--28",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Chazelle:1991:OCH,
author = "B. Chazelle",
title = "An optimal convex hull algorithm and new results on
cuttings",
crossref = "IEEE:1991:PAS",
pages = "29--38",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Hoffmann:1991:AGT,
author = "F. Hoffmann and M. Kaufmann and K. Kriegel",
title = "The art gallery theorem for polygons with holes",
crossref = "IEEE:1991:PAS",
pages = "39--48",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Matousek:1991:FTD,
author = "J. Matousek and N. Miller and J. Pach and M. Sharir
and S. Sifrony and E. Welzl",
title = "Fat triangles determine linearly many holes
(computational geometry)",
crossref = "IEEE:1991:PAS",
pages = "49--58",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Goldreich:1991:QKC,
author = "O. Goldreich and E. Petrank",
title = "Quantifying knowledge complexity",
crossref = "IEEE:1991:PAS",
pages = "59--68",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Boyar:1991:SZK,
author = "J. Boyar and G. Brassard and R. Peralta",
title = "Subquadratic zero-knowledge",
crossref = "IEEE:1991:PAS",
pages = "69--78",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Zuckerman:1991:SBU,
author = "D. Zuckerman",
title = "Simulating {BPP} using a general weak random source",
crossref = "IEEE:1991:PAS",
pages = "79--89",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Blum:1991:CCM,
author = "M. Blum and W. Evans and P. Gemmell and S. Kannan and
M. Naor",
title = "Checking the correctness of memories",
crossref = "IEEE:1991:PAS",
pages = "90--99",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Baruah:1991:LSP,
author = "S. Baruah and G. Koren and B. Mishra and A.
Raghunathan and L. Rosier and D. Shasha",
title = "On-line scheduling in the presence of overload",
crossref = "IEEE:1991:PAS",
pages = "100--110",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Feldmann:1991:DSP,
author = "S. Feldmann and J. Sgall and S.-H. Teng",
title = "Dynamic scheduling on parallel machines",
crossref = "IEEE:1991:PAS",
pages = "111--120",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Vitter:1991:OPD,
author = "J. S. Vitter and P. Krishnan",
title = "Optimal prefetching via data compression",
crossref = "IEEE:1991:PAS",
pages = "121--130",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Shmoys:1991:SPM,
author = "D. B. Shmoys and J. Wein and D. P. Williamson",
title = "Scheduling parallel machines on-line",
crossref = "IEEE:1991:PAS",
pages = "131--140",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kunde:1991:CRD,
author = "M. Kunde",
title = "Concentrated regular data streams on grids: sorting
and routing near to the bisection bound",
crossref = "IEEE:1991:PAS",
pages = "141--150",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Wu:1991:CCP,
author = "I.-C. Wu and H. T. Kung",
title = "Communication complexity for parallel
divide-and-conquer",
crossref = "IEEE:1991:PAS",
pages = "151--162",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Papadimitriou:1991:SST,
author = "C. H. Papadimitriou",
title = "On selecting a satisfying truth assignment",
crossref = "IEEE:1991:PAS",
pages = "163--169",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Aizenstein:1991:ELR,
author = "H. Aizenstein and L. Pitt",
title = "Exact learning of read-twice {DNF} formulas",
crossref = "IEEE:1991:PAS",
pages = "170--179",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Mulmuley:1991:RMSa,
author = "K. Mulmuley",
title = "Randomized multidimensional search trees: lazy
balancing and dynamic shuffling",
crossref = "IEEE:1991:PAS",
pages = "180--196",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Schwarzkopf:1991:DMG,
author = "O. Schwarzkopf",
title = "Dynamic maintenance of geometric structures made
easy",
crossref = "IEEE:1991:PAS",
pages = "197--206",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Matousek:1991:RPH,
author = "J. Matousek",
title = "Reporting points in halfspaces",
crossref = "IEEE:1991:PAS",
pages = "207--215",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Mulmuley:1991:RMSb,
author = "K. Mulmuley",
title = "Randomized multidimensional search trees: further
results in dynamic sampling",
crossref = "IEEE:1991:PAS",
pages = "216--227",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Orlitsky:1991:ICB,
author = "A. Orlitsky",
title = "Interactive communication: balanced distributions,
correlated files, and average-case complexity",
crossref = "IEEE:1991:PAS",
pages = "228--238",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Feder:1991:ACC,
author = "T. Feder and E. Kushilevitz and M. Naor",
title = "Amortized communication complexity",
crossref = "IEEE:1991:PAS",
pages = "239--248",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Edmonds:1991:CCT,
author = "J. Edmonds and R. Impagliazzo and S. Rudich and J.
Sgall",
title = "Communication complexity towards lower bounds on
circuit depth",
crossref = "IEEE:1991:PAS",
pages = "249--257",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Awerbuch:1991:DPC,
author = "B. Awerbuch and G. Varghese",
title = "Distributed program checking: a paradigm for building
self-stabilizing distributed protocols",
crossref = "IEEE:1991:PAS",
pages = "258--267",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Awerbuch:1991:SSL,
author = "B. Awerbuch and B. Patt-Shamir and G. Varghese",
title = "Self-stabilization by local checking and correction",
crossref = "IEEE:1991:PAS",
pages = "268--277",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Wang:1991:ATD,
author = "W. Wang",
title = "An asynchronous two-dimensional self-correcting
cellular automaton",
crossref = "IEEE:1991:PAS",
pages = "278--285",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Fiat:1991:CAL,
author = "A. Fiat and D. P. Foster and H. Karloff and Y. Rabani
and Y. Ravid and S. Viswanathan",
title = "Competitive algorithms for layered graph traversal",
crossref = "IEEE:1991:PAS",
pages = "288--297",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Deng:1991:HLU,
author = "X. Deng and T. Kameda and C. Papadimitriou",
title = "How to learn an unknown environment",
crossref = "IEEE:1991:PAS",
pages = "298--303",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Klein:1991:WUS,
author = "R. Klein",
title = "Walking an unknown street with bounded detour",
crossref = "IEEE:1991:PAS",
pages = "304--313",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Radhakrishnan:1991:BBT,
author = "J. Radhakrishnan",
title = "Better bounds for threshold formulas",
crossref = "IEEE:1991:PAS",
pages = "314--323",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Paterson:1991:SMF,
author = "M. S. Paterson and U. Zwick",
title = "Shrinkage of {de Morgan} formulae under restriction",
crossref = "IEEE:1991:PAS",
pages = "324--333",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Bshouty:1991:SDT,
author = "N. H. Bshouty and R. Cleve and W. Eberly",
title = "Size-depth tradeoffs for algebraic formulae",
crossref = "IEEE:1991:PAS",
pages = "334--341",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kapron:1991:NCM,
author = "B. Kapron and S. A. Cook",
title = "A new characterization of {Mehlhorn}'s polynomial time
functionals",
crossref = "IEEE:1991:PAS",
pages = "342--347",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Verma:1991:TUH,
author = "R. M. Verma",
title = "A theory of using history for equational systems with
applications",
crossref = "IEEE:1991:PAS",
pages = "348--357",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Klarlund:1991:PMC,
author = "N. Klarlund",
title = "Progress measures for complementation
$\omega$-automata with applications to temporal logic",
crossref = "IEEE:1991:PAS",
pages = "358--367",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Emerson:1991:TAM,
author = "E. A. Emerson and C. S. Jutla",
title = "Tree automata, mu-calculus and determinacy",
crossref = "IEEE:1991:PAS",
pages = "368--377",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Shoup:1991:LBP,
author = "V. Shoup and R. Smolensky",
title = "Lower bounds for polynomial evaluation and
interpolation problems",
crossref = "IEEE:1991:PAS",
pages = "378--383",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{vonzurGathen:1991:EEF,
author = "J. von zur Gathen",
title = "Efficient exponentiation in finite field",
crossref = "IEEE:1991:PAS",
pages = "384--391",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Morgenstern:1991:ECN,
author = "M. Morgenstern",
title = "Explicit construction of natural bounded
concentrators",
crossref = "IEEE:1991:PAS",
pages = "392--397",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kahale:1991:BER,
author = "N. Kahale",
title = "Better expansion for {Ramanujan} graphs",
crossref = "IEEE:1991:PAS",
pages = "398--404",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Emiris:1991:GAR,
author = "I. Emiris and J. Canny",
title = "A general approach to removing degeneracies",
crossref = "IEEE:1991:PAS",
pages = "405--413",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Edelsbrunner:1991:QTA,
author = "H. Edelsbrunner and T. S. Tan",
title = "A quadratic time algorithm for the minmax length
triangulation",
crossref = "IEEE:1991:PAS",
pages = "414--423",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Matousek:1991:DAB,
author = "J. Matousek and E. Welzl and L. Wernisch",
title = "Discrepancy and in-approximations for bounded
{VC}-dimension",
crossref = "IEEE:1991:PAS",
pages = "424--430",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Du:1991:BHE,
author = "D.-Z. Du and Y. Zhang and Q. Feng",
title = "On better heuristic for {Euclidean Steiner} minimum
trees",
crossref = "IEEE:1991:PAS",
pages = "431--439",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Anumann:1991:AOP,
author = "Y. Anumann and M. Ben-Or",
title = "Asymptotically optimal {PRAM} emulation on faulty
hypercubes",
crossref = "IEEE:1991:PAS",
pages = "440--446",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Goldreich:1991:FTC,
author = "O. Goldreich and S. Goldwasser and N. Linial",
title = "Fault-tolerant computation in the full information
model",
crossref = "IEEE:1991:PAS",
pages = "447--457",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Leighton:1991:HFT,
author = "T. Leighton and Y. Ma and C. G. Plaxton",
title = "Highly fault-tolerant sorting circuits",
crossref = "IEEE:1991:PAS",
pages = "458--469",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Leighton:1991:EAD,
author = "T. Leighton and E. J. Schwabe",
title = "Efficient algorithms for dynamic allocation of
distributed memory",
crossref = "IEEE:1991:PAS",
pages = "470--479",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Adler:1991:PAL,
author = "I. Adler and P. A. Beling",
title = "Polynomial algorithms for {LP} over a subring of the
algebraic integers with applications to {LP} with
circulant matrices",
crossref = "IEEE:1991:PAS",
pages = "480--487",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Eppstein:1991:DTD,
author = "D. Eppstein",
title = "Dynamic three-dimensional linear programming",
crossref = "IEEE:1991:PAS",
pages = "488--494",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Plotkin:1991:FAA,
author = "S. A. Plotkin and D. B. Shmoys and E. Tardos",
title = "Fast approximation algorithms for fractional packing
and covering problems",
crossref = "IEEE:1991:PAS",
pages = "495--504",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Awerbuch:1991:MCD,
author = "B. Awerbuch and L. J. Schulman",
title = "The maintenance of common data in a distributed
system",
crossref = "IEEE:1991:PAS",
pages = "505--514",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Naor:1991:OFS,
author = "M. Naor and R. M. Roth",
title = "Optimal file sharing in distributed networks",
crossref = "IEEE:1991:PAS",
pages = "515--525",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Herlihy:1991:LCL,
author = "M. Herlihy and N. Shavit and O. Waarts",
title = "Low contention linearizable counting",
crossref = "IEEE:1991:PAS",
pages = "526--535",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Miller:1991:UGA,
author = "G. L. Miller and S.-H. Teng and S. A. Vavasis",
title = "A unified geometric approach to graph separators",
crossref = "IEEE:1991:PAS",
pages = "538--547",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Hsu:1991:LTA,
author = "T.-S. Hsu and V. Ramachandran",
title = "A linear time algorithm for triconnectivity
augmentation",
crossref = "IEEE:1991:PAS",
pages = "548--559",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Karger:1991:FHP,
author = "D. R. Karger and D. Koller and S. J. Phillips",
title = "Finding the hidden path: time bounds for all-pairs
shortest paths",
crossref = "IEEE:1991:PAS",
pages = "560--568",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Lovasz:1991:SPD,
author = "L. Lovasz and M. Naor and I. Newman and A. Wigderson",
title = "Search problems in the decision tree model",
crossref = "IEEE:1991:PAS",
pages = "576--585",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Alon:1991:PAV,
author = "N. Alon",
title = "A parallel algorithmic version of the local lemma",
crossref = "IEEE:1991:PAS",
pages = "586--593",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Gal:1991:LBC,
author = "A. Gal",
title = "Lower bounds for the complexity of reliable {Boolean}
circuits with noisy gates",
crossref = "IEEE:1991:PAS",
pages = "594--601",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Reischuk:1991:RCN,
author = "R. Reischuk and B. Schmeltz",
title = "Reliable computation with noisy circuits and decision
trees --- a general $n \log n$ lower bound",
crossref = "IEEE:1991:PAS",
pages = "602--611",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Sundar:1991:LBD,
author = "R. Sundar",
title = "A lower bound for the dictionary problem under a
hashing model",
crossref = "IEEE:1991:PAS",
pages = "612--621",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Ben-Amram:1991:LBD,
author = "A. M. Ben-Amram and Z. Galil",
title = "Lower bounds for data structure problems on {RAMs}",
crossref = "IEEE:1991:PAS",
pages = "622--631",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Frederickson:1991:ADS,
author = "G. N. Frederickson",
title = "Ambivalent data structures for dynamic
$2$-edge-connectivity and $k$ smallest spanning trees",
crossref = "IEEE:1991:PAS",
pages = "632--641",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Andersson:1991:FUR,
author = "A. Andersson and T. Ottmann",
title = "Faster uniquely represented dictionaries",
crossref = "IEEE:1991:PAS",
pages = "642--649",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Donald:1991:CCH,
author = "B. R. Donald and D. R. Chang",
title = "On the complexity of computing the homology type of a
triangulation",
crossref = "IEEE:1991:PAS",
pages = "650--661",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Grigoriev:1991:AAN,
author = "D. Grigoriev and M. Karpinski",
title = "An approximation algorithm for the number of zeros or
arbitrary polynomials over {GF$(q)$}",
crossref = "IEEE:1991:PAS",
pages = "662--669",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Blomer:1991:CSR,
author = "J. Blomer",
title = "Computing sums of radicals in polynomial time",
crossref = "IEEE:1991:PAS",
pages = "670--677",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Huang:1991:EAR,
author = "M.-D. Huang and D. Ierardi",
title = "Efficient algorithms for the {Riemann-Roch} problem
and for addition in the {Jacobian} of a curve",
crossref = "IEEE:1991:PAS",
pages = "678--687",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Johnson:1991:CCP,
author = "D. B. Johnson and P. Metaxas",
title = "Connected components in {$O(\lg^{3/2 \bmod V} \bmod)$}
parallel time for the {CREW PRAM}",
crossref = "IEEE:1991:PAS",
pages = "688--697",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Gil:1991:TTN,
author = "J. Gil and Y. Matias and U. Vishkin",
title = "Towards a theory of nearly constant time parallel
algorithms",
crossref = "IEEE:1991:PAS",
pages = "698--710",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Goodrich:1991:UAA,
author = "M. T. Goodrich",
title = "Using approximation algorithms to design parallel
algorithms that may ignore processor allocation",
crossref = "IEEE:1991:PAS",
pages = "711--722",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Gazit:1991:DPA,
author = "H. Gazit",
title = "A deterministic parallel algorithm for planar graphs
isomorphism",
crossref = "IEEE:1991:PAS",
pages = "723--732",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Babai:1991:ART,
author = "L. Babai and K. Friedl",
title = "Approximate representation theory of finite groups",
crossref = "IEEE:1991:PAS",
pages = "733--742",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Saran:1991:FCW,
author = "H. Saran and V. V. Vazirani",
title = "Finding $k$-cuts within twice the optimal",
crossref = "IEEE:1991:PAS",
pages = "743--751",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Shor:1991:HPB,
author = "P. W. Shor",
title = "How to pack better than best fit: tight bounds for
average-case online bin packing",
crossref = "IEEE:1991:PAS",
pages = "752--759",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Amir:1991:ADM,
author = "A. Amir and M. Farach",
title = "Adaptive dictionary matching",
crossref = "IEEE:1991:PAS",
pages = "760--766",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Maass:1991:CPS,
author = "W. Maass and G. Schnitger and E. D. Sontag",
title = "On the computational power of sigmoid versus {Boolean}
threshold circuits",
crossref = "IEEE:1991:PAS",
pages = "767--776",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Krause:1991:VRC,
author = "M. Krause and S. Waack",
title = "Variation ranks of communication matrices and lower
bounds for depth two circuits having symmetric gates
with unbounded fan-in",
crossref = "IEEE:1991:PAS",
pages = "777--782",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Beigel:1991:ACC,
author = "R. Beigel and J. Tarui",
title = "On {ACC} (circuit complexity)",
crossref = "IEEE:1991:PAS",
pages = "783--792",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kanevsky:1991:LMF,
author = "A. Kanevsky and R. Tamassia and G. Di Battista and J.
Chen",
title = "On-line maintenance of the four-connected components
of a graph",
crossref = "IEEE:1991:PAS",
pages = "793--801",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Gupta:1991:CPI,
author = "A. Gupta and R. Impagliazzo",
title = "Computing planar intertwines",
crossref = "IEEE:1991:PAS",
pages = "802--811",
year = "1991",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Arora:1992:PCP,
author = "S. Arora and S. Safra",
title = "Probabilistic checking of proofs; a new
characterization of {NP}",
crossref = "IEEE:1992:ASF",
pages = "2--13",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Arora:1992:PVH,
author = "S. Arora and C. Lund and R. Motwani and M. Sudan and
Mario Szegedy",
title = "Proof verification and hardness of approximation
problems",
crossref = "IEEE:1992:ASF",
pages = "14--23",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Nisan:1992:UCS,
author = "N. Nisan and E. Szemeredi and A. Wigderson",
title = "Undirected connectivity in {$O(\log^{1.5}n)$} space",
crossref = "IEEE:1992:ASF",
pages = "24--29",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Fenner:1992:ICH,
author = "S. Fenner and L. Fortnow and S. A. Kurtz",
title = "The isomorphism conjecture holds relative to an
oracle",
crossref = "IEEE:1992:ASF",
pages = "30--39",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Buchsbaum:1992:DSB,
author = "A. L. Buchsbaum and R. Sundar and R. E. Tarjan",
title = "Data structural bootstrapping, linear path
compression, and catenable heap ordered double ended
queues",
crossref = "IEEE:1992:ASF",
pages = "40--49",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Rauch:1992:FDB,
author = "M. Rauch",
title = "Fully dynamic biconnectivity in graphs",
crossref = "IEEE:1992:ASF",
pages = "50--59",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Eppstein:1992:STS,
author = "D. Eppstein",
title = "Sparsification-a technique for speeding up dynamic
graph algorithms",
crossref = "IEEE:1992:ASF",
pages = "60--69",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Hsu:1992:FCT,
author = "T. Hsu",
title = "On four-connecting a triconnected graph",
crossref = "IEEE:1992:ASF",
pages = "70--79",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Agarwal:1992:DHS,
author = "P. K. Agarwal and D. Eppstein and J. Matousek",
title = "Dynamic half-space reporting, geometric optimization,
and minimum spanning trees",
crossref = "IEEE:1992:ASF",
pages = "80--89",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Mulmuley:1992:RGA,
author = "K. Mulmuley",
title = "Randomized geometric algorithms and pseudo-random
generators",
crossref = "IEEE:1992:ASF",
pages = "90--100",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kant:1992:DPG,
author = "G. Kant",
title = "Drawing planar graphs using the lmc-ordering",
crossref = "IEEE:1992:ASF",
pages = "101--110",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Luks:1992:CSM,
author = "E. M. Luks",
title = "Computing in solvable matrix groups",
crossref = "IEEE:1992:ASF",
pages = "111--120",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Giesbrecht:1992:FAM,
author = "M. Giesbrecht",
title = "Fast algorithms for matrix normal forms",
crossref = "IEEE:1992:ASF",
pages = "121--130",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Bini:1992:IPP,
author = "D. Bini and V. Pan",
title = "Improved parallel polynomial division and its
extensions",
crossref = "IEEE:1992:ASF",
pages = "131--136",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Aspnes:1992:RCE,
author = "J. Aspnes and O. Waarts",
title = "Randomized consensus in expected {$O(n \log^2 n)$}
operations per processor",
crossref = "IEEE:1992:ASF",
pages = "137--146",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Aumann:1992:CCF,
author = "Y. Aumann and M. O. Rabin",
title = "Clock construction in fully asynchronous parallel
systems and {PRAM} simulation",
crossref = "IEEE:1992:ASF",
pages = "147--156",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Jayanti:1992:FTW,
author = "P. Jayanti and T. D. Chandra and S. Toueg",
title = "Fault-tolerant wait-free shared objects",
crossref = "IEEE:1992:ASF",
pages = "157--166",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Gradel:1992:HTC,
author = "E. Gradel and G. L. McColm",
title = "Hierarchies in transitive closure logic, stratified
{Datalog} and infinitary logic",
crossref = "IEEE:1992:ASF",
pages = "167--176",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Alur:1992:BFT,
author = "R. Alur and T. A. Henzinger",
title = "Back to the future: towards a theory of timed regular
languages",
crossref = "IEEE:1992:ASF",
pages = "177--186",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Pitassi:1992:CHC,
author = "T. Pitassi and A. Urquhart",
title = "The complexity of the {Hajos} calculus",
crossref = "IEEE:1992:ASF",
pages = "187--196",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Blum:1992:DTB,
author = "A. Blum and H. Karloff and Y. Rabani and M. Saks",
title = "A decomposition theorem and bounds for randomized
server problems",
crossref = "IEEE:1992:ASF",
pages = "197--207",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Karlin:1992:MP,
author = "A. R. Karlin and S. J. Phillips and P. Raghavan",
title = "{Markov} paging",
crossref = "IEEE:1992:ASF",
pages = "208--217",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Azar:1992:LLB,
author = "Y. Azar and A. Z. Broder and A. R. Karlin",
title = "On-line load balancing",
crossref = "IEEE:1992:ASF",
pages = "218--225",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Plaxton:1992:ILB,
author = "C. G. Plaxton and B. Poonen and T. Suel",
title = "Improved lower bounds for {Shellsort}",
crossref = "IEEE:1992:ASF",
pages = "226--235",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Miltersen:1992:ACM,
author = "P. B. Miltersen and M. Paterson and J. Tarui",
title = "The asymptotic complexity of merging networks",
crossref = "IEEE:1992:ASF",
pages = "236--246",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Galil:1992:TAI,
author = "Z. Galil and K. Park",
title = "Truly alphabet-independent two-dimensional pattern
matching",
crossref = "IEEE:1992:ASF",
pages = "247--256",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Dubiner:1992:APP,
author = "M. Dubiner and U. Zwick",
title = "Amplification and percolation (probabilistic {Boolean}
functions)",
crossref = "IEEE:1992:ASF",
pages = "258--267",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Yao:1992:ADT,
author = "A. Chi-Chih Yao",
title = "Algebraic decision trees and {Euler} characteristics",
crossref = "IEEE:1992:ASF",
pages = "268--277",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Grolmusz:1992:SCC,
author = "V. Grolmusz",
title = "Separating the communication complexities of {MOD} $m$
and {MOD} $p$ circuits",
crossref = "IEEE:1992:ASF",
pages = "278--287",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Coppersmith:1992:LBD,
author = "D. Coppersmith and B. Schieber",
title = "Lower bounds on the depth of monotone arithmetic
computations",
crossref = "IEEE:1992:ASF",
pages = "288--295",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kahale:1992:SEL,
author = "N. Kahale",
title = "On the second eigenvalue and linear expansion of
regular graphs",
crossref = "IEEE:1992:ASF",
pages = "296--303",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Rabinovich:1992:QDS,
author = "Y. Rabinovich and A. Sinclair and A. Wigderson",
title = "Quadratic dynamical systems",
crossref = "IEEE:1992:ASF",
pages = "304--313",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Friedman:1992:BEP,
author = "J. Friedman",
title = "On the bit extraction problem",
crossref = "IEEE:1992:ASF",
pages = "314--319",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Jerrum:1992:MEA,
author = "M. Jerrum and U. Vazirani",
title = "A mildly exponential approximation algorithm for the
permanent",
crossref = "IEEE:1992:ASF",
pages = "320--326",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{El-Yaniv:1992:CAF,
author = "R. El-Yaniv and A. Fiat and R. Karp and G. Turpin",
title = "Competitive analysis of financial games",
crossref = "IEEE:1992:ASF",
pages = "327--333",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Alon:1992:LBC,
author = "N. Alon and G. Kalai and M. Ricklin and L.
Stockmeyer",
title = "Lower bounds on the competitive ratio for mobile user
tracking and distributed job scheduling",
crossref = "IEEE:1992:ASF",
pages = "334--343",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Bartal:1992:DSP,
author = "Y. Bartal and A. Rosen",
title = "The distributed $k$-server problem --- a competitive
distributed translator for $k$-server algorithms",
crossref = "IEEE:1992:ASF",
pages = "344--353",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Marcinkowski:1992:UHC,
author = "J. Marcinkowski and L. Pacholski",
title = "Undecidability of the {Horn}-clause implication
problem",
crossref = "IEEE:1992:ASF",
pages = "354--362",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kozen:1992:EIP,
author = "D. Kozen and J. Palsberg and M. I. Schwartzbach",
title = "Efficient inference of partial types",
crossref = "IEEE:1992:ASF",
pages = "363--371",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{denBussche:1992:COC,
author = "J. Van den Bussche and D. Van Gucht and M. Andries and
M. Gyssens",
title = "On the completeness of object-creating query
languages",
crossref = "IEEE:1992:ASF",
pages = "372--379",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Lenhof:1992:EKC,
author = "H.-P. Lenhof and M. Smid",
title = "Enumerating the $k$ closest pairs optimally",
crossref = "IEEE:1992:ASF",
pages = "380--386",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Clarkson:1992:SED,
author = "K. L. Clarkson",
title = "Safe and effective determinant evaluation",
crossref = "IEEE:1992:ASF",
pages = "387--395",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Katoh:1992:MMS,
author = "N. Katoh and T. Tokuyama and K. Iwano",
title = "On minimum and maximum spanning trees of linearly
moving points",
crossref = "IEEE:1992:ASF",
pages = "396--405",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Blum:1992:TCT,
author = "M. Blum and O. Goldreich",
title = "Towards a computational theory of statistical tests",
crossref = "IEEE:1992:ASF",
pages = "406--416",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Alon:1992:WBM,
author = "N. Alon and Z. Galil and O. Margalit and M. Naor",
title = "Witnesses for {Boolean} matrix multiplication and for
shortest paths",
crossref = "IEEE:1992:ASF",
pages = "417--426",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Santis:1992:ZKP,
author = "A. De Santis and G. Persiano",
title = "Zero-knowledge proofs of knowledge without
interaction",
crossref = "IEEE:1992:ASF",
pages = "427--436",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Yap:1992:FUR,
author = "C. K. Yap",
title = "Fast unimodular reduction: planar integer lattices",
crossref = "IEEE:1992:ASF",
pages = "437--446",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Blomer:1992:HDR,
author = "J. Blomer",
title = "How to denest {Ramanujan}'s nested radicals",
crossref = "IEEE:1992:ASF",
pages = "447--456",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Eberly:1992:EBM,
author = "W. Eberly",
title = "On efficient band matrix arithmetic",
crossref = "IEEE:1992:ASF",
pages = "457--463",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Gartner:1992:SAA,
author = "B. Gartner",
title = "A subexponential algorithm for abstract optimization
problems",
crossref = "IEEE:1992:ASF",
pages = "464--472",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Alon:1992:AAR,
author = "N. Alon",
title = "The algorithmic aspects of the regularity lemma",
crossref = "IEEE:1992:ASF",
pages = "473--481",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Lovasz:1992:RCV,
author = "L. Lovasz and M. Simonovits",
title = "On the randomized complexity of volume and diameter",
crossref = "IEEE:1992:ASF",
pages = "482--492",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Helmbold:1992:ATN,
author = "D. P. Helmbold and N. Littlestone and P. M. Long",
title = "Apple tasting and nearly one-sided learning",
crossref = "IEEE:1992:ASF",
pages = "493--502",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Ar:1992:RAF,
author = "S. Ar and R. J. Lipton and R. Rubinfeld and M. Sudan",
title = "Reconstructing algebraic functions from mixed data",
crossref = "IEEE:1992:ASF",
pages = "503--512",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Bshouty:1992:ELF,
author = "N. H. Bshouty and R. Cleve",
title = "On the exact learning of formulas in parallel",
crossref = "IEEE:1992:ASF",
pages = "513--522",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Aizenstein:1992:RTD,
author = "H. Aizenstein and L. Hellerstein and L. Pitt",
title = "Read-thrice {DNF} is hard to learn with membership and
equivalence queries",
crossref = "IEEE:1992:ASF",
pages = "523--532",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Tamaki:1992:ESE,
author = "H. Tamaki",
title = "Efficient self-embedding of butterfly networks with
random faults",
crossref = "IEEE:1992:ASF",
pages = "533--541",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Leighton:1992:FTS,
author = "T. Leighton and B. Maggs and R. Sitaraman",
title = "On the fault tolerance of some popular bounded-degree
networks",
crossref = "IEEE:1992:ASF",
pages = "542--552",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Feige:1992:EAH,
author = "U. Feige and P. Raghavan",
title = "Exact analysis of hot-potato routing",
crossref = "IEEE:1992:ASF",
pages = "553--562",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Felperin:1992:TWR,
author = "S. Felperin and P. Raghavan and E. Upfal",
title = "A theory of wormhole routing in parallel computers",
crossref = "IEEE:1992:ASF",
pages = "563--572",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Mitchell:1992:CSL,
author = "J. S. B. Mitchell and C. Piatko and E. M. Arkin",
title = "Computing a shortest $k$-link path in a polygon",
crossref = "IEEE:1992:ASF",
pages = "573--582",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Aggarwal:1992:EMC,
author = "A. Aggarwal and A. Bar-Noy and S. Khuller and D.
Kravets and B. Schieber",
title = "Efficient minimum cost matching using quadrangle
inequality",
crossref = "IEEE:1992:ASF",
pages = "583--592",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Wagener:1992:OPH,
author = "H. Wagener",
title = "Optimal parallel hull construction for simple polygons
in {O}(log log n) time",
crossref = "IEEE:1992:ASF",
pages = "593--599",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Cole:1992:TBE,
author = "R. Cole and R. Hariharan",
title = "Tighter bounds on the exact complexity of string
matching",
crossref = "IEEE:1992:ASF",
pages = "600--609",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kenyon:1992:TPR,
author = "C. Kenyon and R. Kenyon",
title = "Tiling a polygon with rectangles",
crossref = "IEEE:1992:ASF",
pages = "610--619",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Chvatal:1992:MGS,
author = "V. Chvatal and B. Reed",
title = "Mick gets some (the odds are on his side)
(satisfiability)",
crossref = "IEEE:1992:ASF",
pages = "620--627",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Hagerup:1992:WMH,
author = "T. Hagerup and R. Raman",
title = "Waste makes haste: tight bounds for loose parallel
sorting",
crossref = "IEEE:1992:ASF",
pages = "628--637",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Chaudhuri:1992:CPP,
author = "S. Chaudhuri and J. Radhakrishnan",
title = "The complexity of parallel prefix problems on small
domains",
crossref = "IEEE:1992:ASF",
pages = "638--647",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Cohen:1992:AMF,
author = "E. Cohen",
title = "Approximate max flow on small depth networks",
crossref = "IEEE:1992:ASF",
pages = "648--658",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Radzik:1992:NMF,
author = "T. Radzik",
title = "{Newton}'s method for fractional combinatorial
optimization",
crossref = "IEEE:1992:ASF",
pages = "659--669",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Conforti:1992:CLP,
author = "M. Conforti and G. Cornuejols",
title = "A class of logic problems solvable by linear
programming",
crossref = "IEEE:1992:ASF",
pages = "670--675",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Toledo:1992:MNL,
author = "S. Toledo",
title = "Maximizing non-linear concave functions in fixed
dimension",
crossref = "IEEE:1992:ASF",
pages = "676--685",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Ajtai:1992:HES,
author = "M. Ajtai and J. Komlos and E. Szemeredi",
title = "Halvers and expanders (switching)",
crossref = "IEEE:1992:ASF",
pages = "686--692",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Ajtai:1992:FTG,
author = "M. Ajtai and N. Alon and J. Bruck and R. Cypher and C.
T. Ho and M. Naor and E. Szemeredi",
title = "Fault tolerant graphs, perfect hash functions and
disjoint paths",
crossref = "IEEE:1992:ASF",
pages = "693--702",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Pan:1992:PCT,
author = "V. Y. Pan and J. H. Reif and S. R. Tate",
title = "The power of combining the techniques of algebraic and
numerical computing: improved approximate multipoint
polynomial evaluation and improved multipole
algorithms",
crossref = "IEEE:1992:ASF",
pages = "703--713",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Kaltofen:1992:PEP,
author = "E. Kaltofen and V. Pan",
title = "Processor-efficient parallel solution of linear
systems. {II}. {The} positive characteristic and
singular cases",
crossref = "IEEE:1992:ASF",
pages = "714--723",
year = "1992",
bibdate = "Thu Apr 5 06:13:50 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Blum:1993:LAI,
author = "A. Blum and P. Chalasani",
title = "An on-line algorithm for improving performance in
navigation",
crossref = "IEEE:1993:ASF",
pages = "2--11",
year = "1993",
bibdate = "Thu Apr 5 06:13:51 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Irani:1993:VIC,
author = "S. Irani and Y. Rabani",
title = "On the value of information in coordination games",
crossref = "IEEE:1993:ASF",
pages = "12--21",
year = "1993",
bibdate = "Thu Apr 5 06:13:51 MDT 2001",
acknowledgement = ack-nhfb,
}
@InProceedings{Awerbuch:1993:HDC,
author = "B. Awerbuch and Y. Bartal and A. Fiat",
title = "{Heat and Dump}: competitiv