5 citations · 13 across the 10 of their papers we have counts for
13 papers
The Information Bottleneck is NP-hard
Roberto Bruno, Ugo Vaccaro
Given a joint distribution on a finite alphabet, the information bottleneck method seeks a representation of that is as informative as possible about while com…
Wyner's Common Information and the Common Entropy are NP-Hard to Compute
Roberto Bruno, Ugo Vaccaro
Wyner's common information and the common entropy of a pair of random variables with finite ranges and joint distribution are both defined by an optimizat…
Finite-Sample Binary Hypothesis Testing via Rényi Divergences: Strong Converse and Local Privacy
Roberto Bruno, Adrien Vandenbroucque, Amedeo Roberto Esposito
We study asymmetric simple binary hypothesis testing between and , based on independent and identically distributed observations. Leveraging a variat…
Constrained Maximum Entropy Contiguous Aggregations
Roberto Bruno, Ugo Vaccaro
Given a probability distribution and an integer , a contiguous aggregation of is a probability distribution such…
An Information Theoretic Treatment of Yager's Probability Distribution Negation
Roberto Bruno, Ugo Vaccaro
In the seminal paper (Yager 2015), Yager defined the negation of a probability distribution , as the distribution $\overline{\mathbf{p}} = (\overline{p}…
The Sharma-Mittal Entropy is Subadditive and Supermodular on the Majorization Lattice
Roberto Bruno, Ugo Vaccaro
We prove that Sharma-Mittal entropy is a subadditive and supermodular function on the lattice of all -dimensional probability distributions, ordered according to the partial ord…
A Finite-Sample Strong Converse for Binary Hypothesis Testing via (Reverse) Rényi Divergence
Roberto Bruno, Adrien Vandenbroucque, Amedeo Roberto Esposito
This work investigates binary hypothesis testing between and in the finite-sample regime under asymmetric error constraints. By employing the ``reverse"…
Old and New Results on Alphabetic Codes
Roberto Bruno, Roberto De Prisco, Ugo Vaccaro
This comprehensive survey examines the field of alphabetic codes, tracing their development from the 1960s to the present day. We explore classical alphabetic codes and their varia…
Optimal Binary Variable-Length Codes with a Bounded Number of 1's per Codeword: Design, Analysis, and Applications
Roberto Bruno, Roberto De Prisco, Ugo Vaccaro
In this paper, we consider the problem of constructing optimal average-length binary codes under the constraint that each codeword must contain at most ones, where is a giv…
Bounds and Algorithms for Alphabetic Codes and Binary Search Trees
Roberto Bruno, Roberto De Prisco, Alfredo De Santis +1
Alphabetic codes and binary search trees are combinatorial structures that abstract search procedures in ordered sets endowed with probability distributions. In this paper, we desi…
Hardness and Approximability of Dimension Reduction on the Probability Simplex
Roberto Bruno
Dimension reduction is a technique used to transform data from a high-dimensional space into a lower-dimensional space, aiming to retain as much of the original information as poss…
A Note on Equivalent Conditions for Majorization
Roberto Bruno, Ugo Vaccaro
In this paper, we introduce novel characterizations of the classical concept of majorization in terms of upper triangular (resp., lower triangular) row-stochastic matrices, and in…
Entropic Bounds on the Average Length of Codes with a Space
Roberto Bruno, Ugo Vaccaro
We consider the problem of constructing prefix-free codes in which a designated symbol, a space, can only appear at the end of codewords. We provide a linear-time algorithm to cons…