Zobrazeno 1 - 10
of 40
pro vyhledávání: '"Alfredo Viola"'
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AQ,..., Iss Proceedings (2012)
In this paper, we show that data streams can sometimes usefully be studied as random permutations. This simple observation allows a wealth of classical and recent results from combinatorics to be recycled, with minimal effort, as estimators for vario
Externí odkaz:
https://doaj.org/article/6781d0dbaea7469299c7aef01fa0c38e
Autor:
Alfredo Viola
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol Vol. 12 no. 2 (2010)
This paper presents the first distributional analysis of both, a parking problem and a linear probing hashing scheme with buckets of size b. The exact distribution of the cost of successful searches for a b alpha-full table is obtained, and moments a
Externí odkaz:
https://doaj.org/article/0aecce095c1c4aa89133774f7ec36b58
Autor:
Alfredo Viola
Publikováno v:
Discrete Mathematics & Theoretical Computer Science, Vol DMTCS Proceedings vol. AD,..., Iss Proceedings (2005)
This paper presents the first distributional analysis of a linear probing hashing scheme with buckets of size $b$. The exact distribution of the cost of successful searches for a $b \alpha$ -full table is obtained, and moments and asymptotic results
Externí odkaz:
https://doaj.org/article/6e1cdf1116cd4c2cbeee476fc41f76b2
Publikováno v:
Communications of the ACM. 63:53-55
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::7ebe529e80530fe8a2bfe7c0021aa6d8
https://doi.org/10.1145/3422826
https://doi.org/10.1145/3422826
Autor:
Yoshiharu Kohayakawa, Sergio Rajsbaum, Marcos Kiwi, Francisco Rodríguez-Henríquez, Jayme Luiz Szwarcfiter, Alfredo Viola
Publikováno v:
Repositório Institucional da USP (Biblioteca Digital da Produção Intelectual)
Universidade de São Paulo (USP)
instacron:USP
Universidade de São Paulo (USP)
instacron:USP
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::14c1e43aed692a16617a606a7734db2b
Autor:
Alfredo Viola, Patricio V. Poblete
Publikováno v:
Combinatorics, Probability and Computing. 28:600-617
Thirty years ago, the Robin Hood collision resolution strategy was introduced for open addressing hash tables, and a recurrence equation was found for the distribution of its search cost. Although this recurrence could not be solved analytically, it
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::d45b35ef4a3aacf051fa2d4b865b89f0
https://doi.org/10.1017/s0963548318000408
https://doi.org/10.1017/s0963548318000408
Publikováno v:
LATIN 2018
LATIN 2018, Apr 2018, Buenos Aeres, Argentina
LATIN 2018: Theoretical Informatics ISBN: 9783319774039
LATIN
LNCS
13th Latin American Symposium
13th Latin American Symposium, Apr 2018, Buenos Aires, Argentina. pp.849-863, ⟨10.1007/978-3-319-77404-6_61⟩
LATIN 2018, Apr 2018, Buenos Aeres, Argentina
LATIN 2018: Theoretical Informatics ISBN: 9783319774039
LATIN
LNCS
13th Latin American Symposium
13th Latin American Symposium, Apr 2018, Buenos Aires, Argentina. pp.849-863, ⟨10.1007/978-3-319-77404-6_61⟩
The Continued Logarithm Algorithm - CL for short- introduced by Gosper in 1978 computes the gcd of two integers; it seems very efficient, as it only performs shifts and subtractions. Shallit has studied its worst-case complexity in 2016 and showed it
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::3a1046576d3c3bd421a8de80a93074f1
https://hal.archives-ouvertes.fr/hal-01709404
https://hal.archives-ouvertes.fr/hal-01709404
Autor:
Alfredo Viola
Publikováno v:
Algorithmica. 76:932-934
This special issue contains the journal versions of a selection of papers from the 11th Latin American Symposium on Theoretical Informatics (LATIN), held on March 31–April 4 2014, in Montevideo, Uruguay. The conference covered a broad range of topi
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2a6d63aa69d463cd3fa445f0cffd2dd8
https://doi.org/10.1007/s00453-016-0181-4
https://doi.org/10.1007/s00453-016-0181-4
Publikováno v:
ACM Transactions on Algorithms. 6:1-45
Quickselect with median-of-3 is largely used in practice and its behavior is fairly well understood. However, the following natural adaptive variant, which we call proportion-from-3 , had not been previously analyzed: “choose as pivot the smallest
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::73724915269d36e1090a341117961b66
https://doi.org/10.1145/1798596.1798606
https://doi.org/10.1145/1798596.1798606
Autor:
Alfredo Viola, J.-M. Le Bars
Publikováno v:
IEEE Transactions on Information Theory. 56:1239-1246
This paper presents a complete characterization of the first order correlation immune Boolean functions that includes the functions that are 1-resilient. The approach consists in defining an equivalence relation on the full set of Boolean functions w
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::802b5d4954065eb13c89c81ce3676a9a
https://doi.org/10.1109/tit.2009.2039083
https://doi.org/10.1109/tit.2009.2039083