- isn = "00045411"
- Artículo:
Randomized Shellsort: A Simple Data-Oblivious Sorting Algorithm
- Autor:
Michael T. Goodrich
- Resumen:
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
- Página:
27
- Publicación:
Journal of the ACM
- Volúmen:
58
- Número:
6
- Periodo:
Diciembre 2011
- ISSN:
00045411
- SrcID:
00045411-2011-06.txt
- Documento número 1145670
- Actualizado el martes, 10 de julio de 2018 11:26:08 a. m.
- Creado el martes, 10 de julio de 2018 11:26:08 a. m.
- Enlace directo
- Artículo:
New Constructive Aspects of the Lovász Local Lemma
- Autor:
Bernhard Haeupler
- Resumen:
The Lovász Local Lemma (LLL) is a powerful tool that gives sufficient conditions for avoiding all of a given set of “bad” events, with positive probability. A series of results have provided algorithms to efficiently construct structures
- Página:
28
- Publicación:
Journal of the ACM
- Volúmen:
58
- Número:
6
- Periodo:
Diciembre 2011
- ISSN:
00045411
- SrcID:
00045411-2011-06.txt
- Documento número 1145671
- Actualizado el martes, 10 de julio de 2018 11:26:08 a. m.
- Creado el martes, 10 de julio de 2018 11:26:08 a. m.
- Enlace directo
- Artículo:
QIP = PSPACE
- Autor:
Victor Vianu
- Resumen:
This work considers the quantum interactive proof system model of computation, which is the (classical) interactive proof system model’s natural quantum computational analogue. An exact characterization of the expressive power of quantum interactive
- Página:
30
- Publicación:
Journal of the ACM
- Volúmen:
58
- Número:
6
- Periodo:
Diciembre 2011
- ISSN:
00045411
- SrcID:
00045411-2011-06.txt
- Documento número 1145672
- Actualizado el martes, 10 de julio de 2018 11:26:08 a. m.
- Creado el martes, 10 de julio de 2018 11:26:08 a. m.
- Enlace directo
- Artículo:
Probabilistic ?-automata
- Autor:
Christel Baier
Marcus Grösser
Nathalie Bertrand
- Resumen:
Probabilistic ?-automata are variants of nondeterministic automata over infinite words where all choices are resolved by probabilistic distributions. Acceptance of a run for an infinite input word can be defined using traditional acceptance criteria ...
- Publicación:
Journal of the ACM
- Volúmen:
59
- Número:
1
- Periodo:
febrero 2012
- ISSN:
00045411
- SrcID:
00045411-2012-01.txt
- Documento número 1145673
- Actualizado el martes, 10 de julio de 2018 11:26:08 a. m.
- Creado el martes, 10 de julio de 2018 11:26:08 a. m.
- Enlace directo
- Artículo:
Polylogarithmic concurrent data structures from monotone circuits
- Autor:
James Aspnes
Hagit Attiya
Keren Censor-Hillel
- Resumen:
This article presents constructions of useful concurrent data structures, including max registers and counters, with step complexity that is sublinear in the number of processes, n. This result avoids a well-known lower bound by having step complexity ...
- Publicación:
Journal of the ACM
- Volúmen:
59
- Número:
1
- Periodo:
febrero 2012
- ISSN:
00045411
- SrcID:
00045411-2012-01.txt
- Documento número 1145674
- Actualizado el martes, 10 de julio de 2018 11:26:08 a. m.
- Creado el martes, 10 de julio de 2018 11:26:08 a. m.
- Enlace directo
