Entry Goodrich:2011:RSS from jalg.bib

Last update: Sat Oct 14 02:35:45 MDT 2017                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{Goodrich:2011:RSS,
  author =       "Michael T. Goodrich",
  title =        "Randomized {Shellsort}: a Simple Data-Oblivious
                 Sorting Algorithm",
  journal =      j-J-ACM,
  volume =       "58",
  number =       "6",
  pages =        "27:1--27:??",
  month =        dec,
  year =         "2011",
  CODEN =        "JACOAH",
  DOI =          "https://doi.org/10.1145/2049697.2049701",
  ISSN =         "0004-5411 (print), 1557-735X (electronic)",
  bibdate =      "Thu Dec 15 09:33:01 MST 2011",
  bibsource =    "http://portal.acm.org/;
                 http://www.math.utah.edu/pub/tex/bib/jacm.bib;
                 http://www.math.utah.edu/pub/tex/bib/jalg.bib",
  note =         "For other Shellsort bounds, see
                 \cite{Yao:1980:AS,Sedgewick:1986:NUB,Weiss:1990:TLB,Poonen:1993:WCS,Plaxton:1997:LBS}.",
  abstract =     "In this article, we describe a randomized Shellsort
                 algorithm. This algorithm is a simple, randomized,
                 data-oblivious version of the Shellsort algorithm that
                 always runs in $O(n \log n)$ time and succeeds in sorting
                 any given input permutation with very high probability.
                 Taken together, these properties imply applications in
                 the design of new efficient privacy-preserving
                 computations based on the secure multiparty computation
                 (SMC) paradigm. In addition, by a trivial conversion of
                 this Monte Carlo algorithm to its Las Vegas equivalent,
                 one gets the first version of Shellsort with a running
                 time that is provably O$(n \log n)$ with very high
                 probability.",
  acknowledgement = ack-nhfb,
  articleno =    "27",
  fjournal =     "Journal of the ACM",
  journal-URL =  "http://portal.acm.org/browse_dl.cfm?idx=J401",
}

Related entries