Ugo Vaccaro

Prof. Dr. Ugo Vaccaro

Department of Computer Science, University of Salerno, Italy
orcid

Research Focus & Metrics

Academic Career Length

25Years (2002-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
23 January 2019 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
FCFerdinando Cicalese
Ferdinando Cicalese
LGLuisa Gargano
Luisa Gargano
Ugo VaccaroUgo Vaccaro
Ugo Vaccaro
Given two discrete random variables X and Y, with probability distributions p=(p1,…,pn) and q=(q1,…,qm), respectively, denote by C(p,q) the set of all couplings of p and q, that is, the set of all bivariate probability distributions that have p and q as marginals. In this paper, we study the problem of finding a joint probability distribution in C(p,q) of minimum entropy (equivalently, a coupling that maximizes the mutual information between X and Y), and we discuss several situations where the need for this kind of optimization naturally arises. Since the optimization problem is known to be NP-hard, we give an efficient algorithm to find a joint probability distribution in C(p,q) with entropy exceeding the minimum possible at most by 1 bit, thus providing an approximation algorithm with an additive gap of at most 1 bit. Leveraging on this algorithm, we extend our result to the problem of finding a minimum–entropy joint distribution of arbitrary k≥2 discrete random variables X1,…,Xk, consistent with the known k marginal distributions of the individual random variables X1,…,Xk. In this case, our algorithm has an additive gap of at most logk from optimum. We also discuss several related applications of our findings and extensions of our results to entropies different from the Shannon entropy.

28 December 2017 in IEEE Transactions on Information Theory
Verified
Journal Article
Closed access
FCFerdinando Cicalese
Ferdinando Cicalese
LGLuisa Gargano
Luisa Gargano
Ugo VaccaroUgo Vaccaro
Ugo Vaccaro
It is well known that the entropy H(X) of a discrete random variable X is always greater than or equal to the entropy H(f(X)) of a function f of X, with equality if and only if f is one-to-one. In this paper, we give tight bounds on H(f(X)), when the function f is not one-to-one, and we illustrate a few scenarios, where this matters. As an intermediate step toward our main result, we derive a lower bound on the entropy of a probability distribution, when only a bound on the ratio between the maximal and minimal probabilities is known. The lower bound improves on previous results in the literature, and it could find applications outside the present scenario.

26 October 2017 in Algorithmica
Verified
Journal Article
Closed access
PDF file
Gennaro CordascoGennaro Cordasco
Gennaro Cordasco
LGLuisa Gargano
Luisa Gargano
MMMarco Mecchia
Marco Mecchia
ARAdele A. Rescigno
Adele A. Rescigno
Ugo VaccaroUgo Vaccaro
Ugo Vaccaro

1 January 2002 in Theoretical Computer Science
Verified
Journal Article
Closed access
FCFerdinando Cicalese
Ferdinando Cicalese
DMDaniele Mundici
Daniele Mundici
Ugo VaccaroUgo Vaccaro
Ugo Vaccaro

9 December 2015
Verified
Book Chapter
Closed access
PDF file
Gennaro CordascoGennaro Cordasco
Gennaro Cordasco
LGLuisa Gargano
Luisa Gargano
MMMarco Mecchia
Marco Mecchia
ARAdele A. Rescigno
Adele A. Rescigno
Ugo VaccaroUgo Vaccaro
Ugo Vaccaro

2 April 2013 in Theoretical Computer Science
Verified
Journal Article
Closed access
PDF file
JBJean-Claude Bermond
Jean-Claude Bermond
LGLuisa Gargano
Luisa Gargano
SPStephane Perénnes
Stephane Perénnes
ARAdele Anna Rescigno
Adele Anna Rescigno
Ugo VaccaroUgo Vaccaro
Ugo Vaccaro