Entry Goodrich:2011:RSS from jalg.bib
Last update: Sat Oct 14 02:35:45 MDT 2017
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
- $O(n \log n)$,
3(3)245,
5(3)422,
7(3)358
- addition,
2(1)13,
4(3)282,
9(3)354,
10(3)403,
12(2)281,
42(2)205,
42(2)304,
42(2)317,
47(1)60
- any,
6(1)138,
35(2)129
- application,
3(1)45,
11(2)252,
12(1)57,
12(3)375,
12(3)490,
13(3)446,
14(2)258,
15(2)284,
16(1)67,
17(3)292,
25(2)221,
26(2)209,
28(1)40,
30(1)33,
33(2)204,
35(1)50,
35(2)129,
36(2)205,
36(2)241,
37(1)121,
38(1)184,
39(2)162,
41(1)52,
42(2)334,
44(1)177,
46(1)27,
49(1)42,
55(1)58,
62(3)148
- article,
15(1)173,
43(1)153
- based,
14(3)344,
45(1)1,
63(1)114
- bound,
1(1)14,
1(2)142,
2(1)77,
3(1)1,
5(1)1,
6(3)393,
7(2)159,
8(1)53,
9(3)321,
11(2)242,
13(1)55,
15(1)101,
19(3)402,
21(3)476,
23(2)221,
23(2)329,
24(1)1,
24(2)395,
25(1)1,
25(2)221,
27(1)1,
28(2)197,
32(1)1,
34(1)148,
34(2)222,
36(1)63,
38(1)184,
39(2)145,
44(1)4,
44(1)52,
45(2)192,
46(1)27,
48(1)2,
48(1)91,
55(2)101,
61(1)20
- computation,
1(3)259,
1(4)359,
2(1)88,
7(2)185,
7(3)369,
8(2)216,
9(1)92,
9(3)365,
13(3)431,
16(3)431,
20(1)1,
22(1)30,
28(2)315
- conversion,
38(1)25
- design,
21(2)403,
28(1)142,
29(2)358
- efficient,
4(2)121,
5(1)80,
5(2)281,
6(4)455,
6(4)577,
7(1)105,
8(1)39,
8(2)192,
8(2)260,
9(1)47,
9(2)254,
10(4)518,
11(1)132,
12(1)57,
12(3)409,
13(1)2,
13(1)128,
13(3)394,
14(2)171,
14(2)244,
16(3)453,
18(2)203,
19(1)116,
20(1)20,
20(2)375,
20(3)445,
20(3)602,
21(2)331,
21(2)358,
22(1)1,
23(1)180,
23(2)386,
25(1)144,
26(1)166,
26(2)370,
28(2)315,
34(1)90,
34(1)109,
34(2)337,
35(1)122,
37(2)283,
38(1)110,
38(2)354,
38(2)374,
39(2)205,
41(1)41,
41(2)212,
41(2)360,
41(2)443,
43(1)51,
47(2)63,
48(1)194,
50(1)106,
52(1)1,
52(1)82,
54(2)205,
59(2)107,
60(2)85
- first,
7(1)105,
13(2)177,
21(1)102,
52(2)193
- given,
6(3)359,
13(3)468,
33(1)124
- Goodrich, Michael T.,
10(3)327,
23(1)51,
37(2)399,
38(1)303
- Goodrich:2011:RSS,
1(1)14,
7(2)159,
11(2)242,
15(1)101,
23(2)221
- new,
2(1)50,
5(4)451,
5(4)557,
6(1)49,
7(2)159,
9(1)129,
11(1)44,
20(2)375,
25(2)221,
27(1)75,
34(2)222,
36(1)63,
36(1)89,
37(2)283,
39(2)162,
40(2)135,
42(2)304,
47(1)60,
48(2)294,
58(2)118,
63(1)17
- one,
12(3)375,
17(3)409,
25(1)194,
37(2)309,
43(1)1
- other,
1(1)14,
4(4)332,
7(2)159,
9(4)538,
11(2)242,
14(3)395,
15(1)76,
15(1)101,
19(3)402,
20(2)205,
21(3)476,
23(2)221,
44(1)4,
44(1)52
- paradigm,
14(2)316
- permutation,
2(2)139,
2(3)227,
4(2)163,
5(3)375,
6(3)309,
7(1)60,
7(4)449,
13(2)297,
16(3)453,
22(1)111,
25(2)321,
32(1)58,
34(2)309,
47(2)104
- Plaxton:1997:LBS,
1(1)14,
7(2)159,
11(2)242,
15(1)101,
23(2)221
- Poonen:1993:WCS,
1(1)14,
7(2)159,
11(2)242,
15(1)101,
23(2)221
- probability,
9(2)245,
10(1)151
- property,
12(3)375,
29(2)204,
31(1)211,
42(1)20,
42(2)277,
42(2)304,
43(1)1,
47(1)60
- provably,
29(2)358
- randomized,
7(4)567,
11(3)441,
13(4)657,
14(3)414,
17(1)157,
21(1)149,
23(1)101,
25(1)19,
25(1)177,
25(2)205,
25(2)311,
28(2)290,
37(2)344,
39(1)1,
42(2)205,
46(2)140,
55(2)192
- running,
1(2)187,
10(4)531,
14(2)316,
22(2)329
- Sedgewick:1986:NUB,
1(1)14,
7(2)159,
11(2)242,
15(1)101,
23(2)221
- see,
1(1)14,
1(3)235,
2(1)105,
7(2)159,
11(2)242,
13(1)33,
14(3)395,
15(1)76,
15(1)101,
15(1)173,
19(3)402,
20(2)205,
21(3)476,
23(2)221,
37(2)267,
41(2)404,
42(2)304,
43(1)153,
44(1)4,
44(1)52,
46(1)21,
47(1)60
- Shellsort,
1(1)14,
7(2)159,
11(2)242,
15(1)101,
23(2)221
- simple,
4(4)324,
7(4)567,
8(2)192,
9(1)92,
10(2)287,
10(3)366,
14(1)69,
14(1)139,
15(1)160,
16(1)24,
20(2)312,
20(3)459,
20(3)602,
22(1)142,
25(1)177,
26(2)291,
34(1)1,
35(2)235,
36(1)102,
39(1)68,
40(1)82,
43(1)1,
52(1)57,
54(1)31
- sorting,
2(1)1,
2(1)88,
3(1)79,
4(2)150,
7(2)270,
9(3)321,
10(3)413,
11(4)622,
12(4)573,
13(2)211,
13(3)374,
17(1)157,
19(3)361,
31(1)66,
42(2)205,
50(1)96
- time,
1(2)187,
3(4)344,
5(1)1,
8(1)106,
8(2)236,
10(3)305,
10(4)451,
10(4)531,
11(4)523,
13(3)353,
14(1)1,
14(1)24,
14(1)45,
14(3)414,
15(1)160,
15(3)482,
16(2)218,
17(1)110,
18(3)378,
22(2)199,
22(2)329,
23(1)121,
23(2)281,
25(2)321,
26(1)1,
28(1)125,
29(1)132,
29(1)165,
30(2)253,
33(1)1,
33(1)51,
33(1)112,
33(1)124,
35(1)1,
36(1)1,
36(2)182,
37(1)2,
40(1)82,
42(2)205,
43(2)155,
44(1)29,
44(2)287,
44(2)359,
45(2)167,
45(2)192,
47(1)40,
48(2)273,
50(1)96,
51(1)1,
54(1)1,
54(1)31,
54(1)45,
54(2)168,
55(1)42,
55(1)76,
56(1)1,
57(2)95,
58(1)67,
59(1)37,
62(1)19
- version,
5(4)502,
9(1)1,
25(2)221
- very,
21(1)71,
37(2)283
- Weiss:1990:TLB,
1(1)14,
7(2)159,
11(2)242,
15(1)101,
23(2)221
- Yao:1980:AS,
1(1)14,
7(2)159,
11(2)242,
15(1)101,
23(2)221