%%% -*-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}: competitive distributed paging", crossref = "IEEE:1993:ASF", pages = "22--31", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Awerbuch:1993:TCL, author = "B. Awerbuch and Y. Azar and S. Plotkin", title = "Throughput-competitive on-line routing", crossref = "IEEE:1993:ASF", pages = "32--40", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Gottlob:1993:NTC, author = "G. Gottlob", title = "{NP} trees and {Carnap}'s modal logic", crossref = "IEEE:1993:ASF", pages = "42--51", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Cosmadakis:1993:LRM, author = "S. S. Cosmadakis", title = "Logical reducibility and monadic {NP}", crossref = "IEEE:1993:ASF", pages = "52--61", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Gupta:1993:GAC, author = "V. Gupta and V. Pratt", title = "Gates accept concurrent behavior", crossref = "IEEE:1993:ASF", pages = "62--71", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Clote:1993:PCH, author = "P. Clote and A. Ignjatovic and B. Kapron", title = "Parallel computable higher type functionals", crossref = "IEEE:1993:ASF", pages = "72--81", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Karker:1993:RSM, author = "D. R. Karker", title = "Random sampling in matroids, with applications to graph connectivity and minimum spanning trees", crossref = "IEEE:1993:ASF", pages = "84--93", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Jerrum:1993:SAG, author = "M. Jerrum and G. B. Sorkin", title = "Simulated annealing for graph bisection", crossref = "IEEE:1993:ASF", pages = "94--103", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Chen:1993:UDP, author = "S. Chen and J. H. Reif", title = "Using difficulty of prediction to decrease computation: fast sort, priority queue and convex hull on entropy bounded inputs", crossref = "IEEE:1993:ASF", pages = "104--112", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Hastad:1993:SE, author = "J. Hastad", title = "The shrinkage exponent is $2$", crossref = "IEEE:1993:ASF", pages = "114--123", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Hastad:1993:TLB, author = "J. Hastad and S. Jukna and P. Pudlak", title = "Top-down lower bounds for depth $3$ circuits", crossref = "IEEE:1993:ASF", pages = "124--129", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Smolensky:1993:RLD, author = "R. Smolensky", title = "On representations by low-degree polynomials", crossref = "IEEE:1993:ASF", pages = "130--138", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Agarwala:1993:PTA, author = "R. Agarwala and D. Fernandez-Baca", title = "A polynomial-time algorithm for the perfect phylogeny problem when the number of character states is fixed", crossref = "IEEE:1993:ASF", pages = "140--147", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Bafna:1993:GRS, author = "V. Bafna and P. A. Pevzner", title = "Genome rearrangements and sorting by reversals", crossref = "IEEE:1993:ASF", pages = "148--157", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Teng:1993:ASS, author = "Shang-Hua Teng and F. Yao", title = "Approximating shortest superstrings", crossref = "IEEE:1993:ASF", pages = "158--165", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Raz:1993:LRC, author = "R. Raz and B. Spieker", title = "On the ``log rank''-conjecture in communication complexity", crossref = "IEEE:1993:ASF", pages = "168--176", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Juedes:1993:CDH, author = "D. W. Juedes and J. H. Lutz", title = "The complexity and distribution of hard problems", crossref = "IEEE:1993:ASF", pages = "177--185", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Chaudhuri:1993:SFA, author = "S. Chaudhuri", title = "Sensitive functions and approximate problems", crossref = "IEEE:1993:ASF", pages = "186--193", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Aiek:1993:SPD, author = "Y. Aiek and G. Stupp", title = "Synchronization power depends on the register size", crossref = "IEEE:1993:ASF", pages = "196--205", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Chaudhuri:1993:TLB, author = "S. Chaudhuri and M. Herlihy and N. A. Lynch and M. R. Tuttle", title = "A tight lower bound for $k$-set agreement", crossref = "IEEE:1993:ASF", pages = "206--215", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Poon:1993:SBG, author = "C. K. Poon", title = "Space bounds for graph connectivity problems on node-named {JAG}s and node-ordered {JAG}s", crossref = "IEEE:1993:ASF", pages = "218--227", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Barnes:1993:TSL, author = "G. Barnes and J. A. Edmonds", title = "Time-space lower bounds for directed $s$--$t$ connectivity on {JAG} models", crossref = "IEEE:1993:ASF", pages = "228--237", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Feige:1993:RTS, author = "U. Feige", title = "A randomized time-space tradeoff of {$O\tilde(mR\circ)$} for {USTCON}", crossref = "IEEE:1993:ASF", pages = "238--246", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Cole:1993:OFP, author = "R. Cole and M. Crochemore and Z. Galil and L. Gasieniec and R. Eariharan and S. Muthukrishnan and K. Park and W. Rytter", title = "Optimally fast parallel algorithms for preprocessing and pattern matching in one and two dimensions", crossref = "IEEE:1993:ASF", pages = "248--258", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Klein:1993:LPP, author = "P. N. Klein and S. Subramanian", title = "A linear-processor polylog-time algorithm for shortest paths in planar graphs", crossref = "IEEE:1993:ASF", pages = "259--270", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Aumann:1993:HEA, author = "Y. Aumann and Z. M. Kedum and K. V. Palem and M. O. Rabin", title = "Highly efficient asynchronous execution of large-grained parallel programs", crossref = "IEEE:1993:ASF", pages = "271--280", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Aslam:1993:GBS, author = "J. A. Aslam and S. E. Decatur", title = "General bounds on statistical query learning and {PAC} learning with noise via hypothesis boosting", crossref = "IEEE:1993:ASF", pages = "282--291", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Alon:1993:SSD, author = "N. Alon and S. Ben-David and N. Cesa-Bianchi and D. Haussler", title = "Scale-sensitive dimensions, uniform convergence, and learnability", crossref = "IEEE:1993:ASF", pages = "292--301", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Bshouty:1993:ELM, author = "N. H. Bshouty", title = "Exact learning via the {Monotone} theory", crossref = "IEEE:1993:ASF", pages = "302--311", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Blum:1993:LIK, author = "A. Blum and R. Kannan", title = "Learning an intersection of $k$ halfspaces over a uniform distribution", crossref = "IEEE:1993:ASF", pages = "312--320", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Rajagopalan:1993:PDR, author = "S. Rajagopalan and V. V. Vazirani", title = "Primal-dual {RNC} approximation algorithms for (multi)-set (multi)-cover and covering integer programs", crossref = "IEEE:1993:ASF", pages = "322--331", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Callahan:1993:OPA, author = "P. B. Callahan", title = "Optimal parallel all-nearest-neighbors using the well-separated pair decomposition", crossref = "IEEE:1993:ASF", pages = "332--340", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Kaklamanis:1993:UES, author = "C. Kaklamanis and D. Krizanc and S. Rao", title = "Universal emulations with sublogarithmic slowdown", crossref = "IEEE:1993:ASF", pages = "341--350", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Yao:1993:QCC, author = "A. Chi-Chih Yao", title = "Quantum circuit complexity", crossref = "IEEE:1993:ASF", pages = "352--361", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Brassard:1993:QBC, author = "G. Brassard and C. Crepeau and R. Jozsa and D. Langlois", title = "A quantum bit commitment scheme provably unbreakable by both parties", crossref = "IEEE:1993:ASF", pages = "362--371", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Gilleron:1993:SSS, author = "R. Gilleron and S. Tison and M. Tommasi", title = "Solving systems of set constraints with negated subset relationships", crossref = "IEEE:1993:ASF", pages = "372--380", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Halperin:1993:NQB, author = "D. Halperin and M. Sharir", title = "Near-quadratic bounds for the motion planning problem for a polygon in a polygonal environment", crossref = "IEEE:1993:ASF", pages = "382--391", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Chazelle:1993:GDR, author = "B. Chazelle", title = "Geometric discrepancy revisited", crossref = "IEEE:1993:ASF", pages = "392--399", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Bronnimann:1993:PRS, author = "H. Bronnimann and B. Chazelle and J. Matousek", title = "Product range spaces, sensitive sampling, and derandomization", crossref = "IEEE:1993:ASF", pages = "400--409", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Egidi:1993:CTA, author = "L. Egidi", title = "The complexity of the theory of $p$-adic numbers", crossref = "IEEE:1993:ASF", pages = "412--421", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Ge:1993:TEM, author = "Guoqiang Ge", title = "Testing equalities of multiplicative representations in polynomial time", crossref = "IEEE:1993:ASF", pages = "422--426", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Beals:1993:VAM, author = "R. Beals and L. Babai", title = "{Las Vegas} algorithms for matrix groups", crossref = "IEEE:1993:ASF", pages = "427--436", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Radzik:1993:FAG, author = "T. Radzik", title = "Faster algorithms for the generalized network flow problem", crossref = "IEEE:1993:ASF", pages = "438--448", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Gabow:1993:FCS, author = "H. N. Gabow", title = "A framework for cost-scaling algorithms for submodular flow problems", crossref = "IEEE:1993:ASF", pages = "449--458", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Awerbuch:1993:SLC, author = "B. Awerbuch and T. Leighton", title = "A simple local-control approximation algorithm for multicommodity flow", crossref = "IEEE:1993:ASF", pages = "459--468", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Frandsen:1993:DWP, author = "G. S. Frandsen and P. B. Miltersen and S. Skyum", title = "Dynamic word problems", crossref = "IEEE:1993:ASF", pages = "470--479", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Hampapuram:1993:OBW, author = "H. Hampapuram and M. L. Fredman", title = "Optimal bi-weighted binary trees and the complexity of maintaining partial sums", crossref = "IEEE:1993:ASF", pages = "480--485", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Koiran:1993:WVB, author = "P. Koiran", title = "A weak version of the {Blum}, {Shub} and {Smale} model", crossref = "IEEE:1993:ASF", pages = "486--495", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Sharir:1993:ATU, author = "M. Sharir", title = "Almost tight upper bounds for lower envelopes in higher dimensions", crossref = "IEEE:1993:ASF", pages = "498--507", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Hershberger:1993:ECE, author = "J. Hershberger and S. Suri", title = "Efficient computation of {Euclidean} shortest paths in the plane", crossref = "IEEE:1993:ASF", pages = "508--517", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Aronov:1993:UCP, author = "B. Aronov and M. Sharir", title = "The union of convex polyhedra in three dimensions", crossref = "IEEE:1993:ASF", pages = "518--527", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Erickson:1993:BLB, author = "J. Erickson and R. Seidel", title = "Better lower bounds on detecting affine and spherical degeneracies", crossref = "IEEE:1993:ASF", pages = "528--536", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Ben-Amram:1993:WCW, author = "A. M. Ben-Amram and Z. Galil", title = "What can we sort in $o(n \log n)$ time?", crossref = "IEEE:1993:ASF", pages = "538--546", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Chang:1993:BQA, author = "R. Chang and W. I. Gasarch", title = "On bounded queries and approximation", crossref = "IEEE:1993:ASF", pages = "547--556", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Shallcross:1993:NEP, author = "D. Shallcross and V. Pan and Yu Lin-Kriz", title = "The {NC} equivalence of planar integer linear programming and {Euclidean} {GCD}", crossref = "IEEE:1993:ASF", pages = "557--564", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Barvinok:1993:PTA, author = "A. I. Barvinok", title = "A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed", crossref = "IEEE:1993:ASF", pages = "566--572", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{McAllister:1993:CPL, author = "M. McAllister and D. Kirkpatrick and J. Snoeyink", title = "A compact piecewise-linear {Voronoi} diagram for convex sites in the plane", crossref = "IEEE:1993:ASF", pages = "573--582", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Mitchell:1993:RTP, author = "S. A. Mitchell", title = "Refining a triangulation of a planar straight-line graph to eliminate large angles", crossref = "IEEE:1993:ASF", pages = "583--592", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Evans:1993:SPA, author = "W. Evans and L. J. Schulman", title = "Signal propagation, with application to a lower bound on the depth of noisy formulas", crossref = "IEEE:1993:ASF", pages = "594--603", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Halldorsson:1993:DVU, author = "M. M. Halldorsson and J. Radhakrishnan and K. V. Subrahmanyam", title = "Directed vs. undirected monotone contact networks for threshold functions", crossref = "IEEE:1993:ASF", pages = "604--613", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Huang:1993:CRP, author = "Ming-Deh Huang and D. Ierardi", title = "Counting rational points on curves over finite fields", crossref = "IEEE:1993:ASF", pages = "616--625", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Reif:1993:ARR, author = "J. H. Reif", title = "An {$O(n \log^3 n)$} algorithm for the real root problem", crossref = "IEEE:1993:ASF", pages = "626--635", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Awerbuch:1993:NLC, author = "B. Awerbuch and B. Berger and L. Cowen and D. Peleg", title = "Near-linear cost sequential and distributed constructions of sparse neighborhood covers", crossref = "IEEE:1993:ASF", pages = "638--647", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Cohen:1993:FAC, author = "E. Cohen", title = "Fast algorithms for constructing $t$-spanners and paths with stretch $t$", crossref = "IEEE:1993:ASF", pages = "648--658", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Garay:1993:SLT, author = "J. A. Garay and S. Kutten and D. Peleg", title = "A sub-linear time distributed algorithm for minimum-weight spanning trees", crossref = "IEEE:1993:ASF", pages = "659--668", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Franklin:1993:EGG, author = "M. Franklin and Z. Galil and M. Yung", title = "Eavesdropping games: a graph-theoretic approach to privacy in distributed systems", crossref = "IEEE:1993:ASF", pages = "670--679", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Gillman:1993:CBR, author = "D. Gillman", title = "A {Chernoff} bound for random walks on expander graphs", crossref = "IEEE:1993:ASF", pages = "680--691", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Kortsarz:1993:CDS, author = "G. Kortsarz and D. Peleg", title = "On choosing a dense subgraph", crossref = "IEEE:1993:ASF", pages = "692--701", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Leiserson:1993:ECA, author = "C. E. Leiserson and S. Rao and S. Toledo", title = "Efficient out-of-core algorithms for linear relaxation using blocking covers", crossref = "IEEE:1993:ASF", pages = "704--713", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Goodrich:1993:EMC, author = "M. T. Goodrich and Jyh-Jong Tsay and D. E. Vengroff and J. S. Vitter", title = "External-memory computational geometry", crossref = "IEEE:1993:ASF", pages = "714--723", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Arora:1993:HAO, author = "S. Arora and L. Babai and J. Stern and Z. Sweedyk", title = "The hardness of approximate optima in lattices, codes, and systems of linear equations", crossref = "IEEE:1993:ASF", pages = "724--733", year = "1993", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Karger:1994:AGC, author = "D. Karger and R. Motwani and M. Sudan", title = "Approximate graph coloring by semidefinite programming", crossref = "Goldwasser:1994:P", pages = "2--13", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Garg:1994:FSC, author = "N. Garg and H. Saran and V. V. Vazirani", title = "Finding separator cuts in planar graphs within twice the optimal", crossref = "Goldwasser:1994:P", pages = "14--23", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Alon:1994:PTR, author = "N. Alon and A. Frieze and D. Welsh", title = "Polynomial time randomised approximation schemes for the {Tutte} polynomial of dense graphs", crossref = "Goldwasser:1994:P", pages = "24--35", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Szegedy:1994:NNL, author = "M. Szegedy", title = "A note on the $\theta$ number of {Lovasz} and the generalized {Delsarte} bound", crossref = "Goldwasser:1994:P", pages = "36--39", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Jackson:1994:EMQ, author = "J. Jackson", title = "An efficient membership-query algorithm for learning {DNF} with respect to the uniform distribution", crossref = "Goldwasser:1994:P", pages = "42--53", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Bshouty:1994:LDG, author = "N. H. Bshouty and Zhixiang Chen and S. Homer", title = "On learning discretized geometric concepts", crossref = "Goldwasser:1994:P", pages = "54--63", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Dhagat:1994:PLI, author = "A. Dhagat and L. Hellerstein", title = "{PAC} learning with irrelevant attributes", crossref = "Goldwasser:1994:P", pages = "64--74", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Bender:1994:PTE, author = "M. A. Bender and D. K. Slonim", title = "The power of team exploration: two robots can learn unlabeled directed graphs", crossref = "Goldwasser:1994:P", pages = "75--85", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Adleman:1994:ANT, author = "L. M. Adleman", title = "Algorithmic number theory-the complexity contribution", crossref = "Goldwasser:1994:P", pages = "88--113", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Simon:1994:PQC, author = "D. R. Simon", title = "On the power of quantum computation", crossref = "Goldwasser:1994:P", pages = "116--123", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Shor:1994:AQC, author = "P. W. Shor", title = "Algorithms for quantum computation: discrete logarithms and factoring", crossref = "Goldwasser:1994:P", pages = "124--134", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Cai:1994:CMP, author = "Jin-yi Cai and R. J. Lipton and Y. Zalcstein", title = "The complexity of the membership problem for $2$-generated commutative semigroups of rational matrices", crossref = "Goldwasser:1994:P", pages = "135--142", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Cai:1994:EAC, author = "Jin-Yi Cai and W. H. Fuchs and D. Kozen and Zicheng Lui", title = "Efficient average-case algorithms for the modular group", crossref = "Goldwasser:1994:P", pages = "143--152", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Eppstein:1994:FKS, author = "D. Eppstein", title = "Finding the $k$ shortest paths", crossref = "Goldwasser:1994:P", pages = "154--165", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Kosaraju:1994:LTS, author = "S. R. Kosaraju and J. K. Park and C. Stein", title = "Long tours and short superstrings", crossref = "Goldwasser:1994:P", pages = "166--177", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Weihe:1994:MFP, author = "K. Weihe", title = "Maximum (s,t)-flows in planar networks in {O}(|{V}|log|{V}|) time", crossref = "Goldwasser:1994:P", pages = "178--189", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Cohen:1994:EST, author = "E. Cohen", title = "Estimating the size of the transitive closure in linear time", crossref = "Goldwasser:1994:P", pages = "190--200", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Ravi:1994:RRR, author = "R. Ravi", title = "Rapid rumor ramification: approximating the minimum broadcast time", crossref = "Goldwasser:1994:P", pages = "202--213", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Naor:1994:LCA, author = "M. Naor and A. Wool", title = "The load, capacity and availability of quorum systems", crossref = "Goldwasser:1994:P", pages = "214--225", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Itkis:1994:FLS, author = "G. Itkis and L. Levin", title = "Fast and lean self-stabilizing asynchronous protocols", crossref = "Goldwasser:1994:P", pages = "226--239", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Awerbuch:1994:LOG, author = "B. Awerbuch and Y. Azar", title = "Local optimization of global objectives: competitive distributed deadlock resolution and resource allocation", crossref = "Goldwasser:1994:P", pages = "240--249", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Karger:1994:RCS, author = "D. R. Karger and D. Koller", title = "(De)randomized construction of small sample spaces in {$\cal NC$}", crossref = "Goldwasser:1994:P", pages = "252--263", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Srinivasan:1994:CVW, author = "A. Srinivasan and D. Zuckerman", title = "Computing with very weak random sources", crossref = "Goldwasser:1994:P", pages = "264--275", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Bellare:1994:REO, author = "M. Bellare and J. Rompel", title = "Randomness-efficient oblivious sampling", crossref = "Goldwasser:1994:P", pages = "276--287", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Rubinfeld:1994:RFE, author = "R. Rubinfeld", title = "On the robustness of functional equations", crossref = "Goldwasser:1994:P", pages = "288--299", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Yao:1994:LBM, author = "A. C.-C. Yao", title = "A lower bound for the monotone depth of connectivity", crossref = "Goldwasser:1994:P", pages = "302--308", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Sinha:1994:EOB, author = "R. K. Sinha and J. S. Thathachar", title = "Efficient oblivious branching programs for threshold functions", crossref = "Goldwasser:1994:P", pages = "309--317", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Nisan:1994:PHB, author = "N. Nisan and S. Rudich and M. Saks", title = "Products and help bits in decision trees", crossref = "Goldwasser:1994:P", pages = "318--329", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Kleitman:1994:DRB, author = "D. Kleitman and T. Leighton and Y. Ma", title = "On the design of reliable {Boolean} circuits that contain partially unreliable gates", crossref = "Goldwasser:1994:P", pages = "332--346", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Ranade:1994:NTB, author = "A. Ranade and S. Schleimer and D. S. Wilkerson", title = "Nearly tight bounds for wormhole routing", crossref = "Goldwasser:1994:P", pages = "347--355", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Blumofe:1994:SMC, author = "R. D. Blumofe and C. E. Leiserson", title = "Scheduling multithreaded computations by work stealing", crossref = "Goldwasser:1994:P", pages = "356--368", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Kutylowski:1994:FFP, author = "M. Kutylowski and K. Lorys and B. Oesterdiekhoff and R. Wanka", title = "Fast and feasible periodic sorting networks of constant depth", crossref = "Goldwasser:1994:P", pages = "369--380", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Blum:1994:PRC, author = "M. Blum and H. Wasserman", title = "Program result-checking: a theory of testing meets a test of theory", crossref = "Goldwasser:1994:P", pages = "382--392", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Koutsoupias:1994:BCA, author = "E. Koutsoupias and C. H. Papadimitriou", title = "Beyond competitive analysis [on-line algorithms]", crossref = "Goldwasser:1994:P", pages = "394--400", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Ajtai:1994:TCA, author = "M. Ajtai and J. Aspnes and C. Dwork and O. Waarts", title = "A theory of competitive analysis for distributed algorithms", crossref = "Goldwasser:1994:P", pages = "401--411", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Awerbuch:1994:LAC, author = "B. Awerbuch and R. Gawlick and T. Leighton and Y. Rabani", title = "On-line admission control and circuit routing for high performance computing and communication", crossref = "Goldwasser:1994:P", pages = "412--423", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Lund:1994:ICO, author = "C. Lund and S. Phillips and N. Reingold", title = "{IP} over connection-oriented networks and distributional paging", crossref = "Goldwasser:1994:P", pages = "424--434", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Micali:1994:CP, author = "S. Micali", title = "{CS} proofs", crossref = "Goldwasser:1994:P", pages = "436--453", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Santis:1994:MFC, author = "A. De Santis and G. Di Crescenzo and G. Persiano and M. Yung", title = "On monotone formula closure of {SZK}", crossref = "Goldwasser:1994:P", pages = "454--465", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Kilian:1994:CBI, author = "J. Kilian", title = "On the complexity of bounded-interaction and noninteractive zero-knowledge proofs", crossref = "Goldwasser:1994:P", pages = "466--477", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Kushilevitz:1994:RCM, author = "E. Kushilevitz and S. Micali and R. Ostrovsky", title = "Reducibility and completeness in multi-party private computations", crossref = "Goldwasser:1994:P", pages = "478--489", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Aldous:1994:SWA, author = "D. Aldous and U. Vazirani", title = "``Go with the winners'' algorithms", crossref = "Goldwasser:1994:P", pages = "492--501", year = "1994", bibdate = "Thu Apr 5 06:13:51 MDT 2001", acknowledgement = ack-nhfb, } @InProceedings{Gartner:1994:RSA, author = "B. Gartner and G. M. Ziegler", title = "Randomized simplex algorithms on {Klee-Minty} cubes", crossref = "Goldwasser:1994: