Source author record

Stefano Della Fiore

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Information Theory math.IT Data Structures and Algorithms

Catalog footprint

Research overview

7works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Achievable Rates and Algorithms for Group Testing with Runlength Constraints

In this paper, we study bounds on the minimum length of $(k,n,d)$ -superimposed codes introduced by Agarwal et al. [1], in the context of Non-Adaptive Group Testing algorithms with runlength constraints. A $(k,n,d)$ -superimposed code of length $t$ is a $t \times n$ binary matrix such that any two 1's in each column are separated by a run of at least $d$ 0's, and such that for any column $\mathbf{c}$ and any other $k-1$ columns, there exists a row where $\mathbf{c}$ has $1$ and all the remaining $k-1$ columns have $0$ . Agarwal et al. proved the existence of such codes with $t=Θ(dk\log(n/k)+k^2\log(n/k))$ . Here we investigate more in detail the coefficients in front of these two main terms as well as the role of lower order terms. We show that improvements can be obtained over the construction in [1] by using different constructions and by an appropriate exploitation of the Lovász Local Lemma in this context. Our findings also suggest $O(n^k)$ randomized Las Vegas algorithms for the construction of such codes. We also extend our results to Two-Stage Group Testing algorithms with runlength constraints.

preprint2022arXiv

Improved Bounds for $(b,k)$ -hashing

For fixed integers $b\geq k$ , a problem of relevant interest in computer science and combinatorics is that of determining the asymptotic growth, with $n$ , of the largest set for which a $(b, k)$ -hash family of $n$ functions exists. Equivalently, determining the asymptotic growth of a largest subset of $\{1,2,\ldots,b\}^n$ such that, for any $k$ distinct elements in the set, there is a coordinate where they all differ. An important asymptotic upper bound for general $b, k$ , was derived by Fredman and Komlós in the '80s and improved for certain $b\neq k$ by Körner and Marton and by Arikan. Only very recently better bounds were derived for the general $b,k$ case by Guruswami and Riazanov while stronger results for small values of $b=k$ were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan and by Costa and Dalai. In this paper, we both show how some of the latter results extend to $b\neq k$ and further strengthen the bounds for some specific small values of $b$ and $k$ . The method we use, which depends on the reduction of an optimization problem to a finite number of cases, shows that further results might be obtained by refined arguments at the expense of higher complexity which could be reduced by using more sophisticated and optimized algorithmic approaches.

preprint2022arXiv

Non-zero sum Heffter arrays and their applications

In this paper we introduce a new class of partially filled arrays that, as Heffter arrays, are related to difference families, graph decompositions and biembeddings. A non-zero sum Heffter array $\mathrm{N}\mathrm{H}(m,n; h,k)$ is an $m \times n$ p. f. array with entries in $\mathbb{Z}_{2nk+1}$ such that: each row contains $h$ filled cells and each column contains $k$ filled cells; for every $x\in \mathbb{Z}_{2nk+1}\setminus\{0\}$ , either $x$ or $-x$ appears in the array; the sum of the elements in every row and column is different from $0$ (in $\mathbb{Z}_{2nk+1}$ ). Here first we explain the connections with relative difference families and with path decompositions of the complete multipartite graph. Then we present a complete solution for the existence problem and a constructive complete solution for the square case and for the rectangular case with no empty cells when the additional, very restrictive, property of "globally simple" is required. Finally, we show how these arrays can be used to construct biembeddings of complete graphs.

preprint2022arXiv

On Sequences in Cyclic Groups with Distinct Partial Sums

A subset of an abelian group is {\em sequenceable} if there is an ordering $(x_1, \ldots, x_k)$ of its elements such that the partial sums $(y_0, y_1, \ldots, y_k)$ , given by $y_0 = 0$ and $y_i = \sum_{j=1}^i x_i$ for $1 \leq i \leq k$ , are distinct, with the possible exception that we may have $y_k = y_0 = 0$ . We demonstrate the sequenceability of subsets of size $k$ of $\mathbb{Z}_n \setminus \{ 0 \}$ when $n = mt$ in many cases, including when $m$ is either prime or has all prime factors larger than $k! /2$ for $k \leq 11$ and $t \leq 5$ and for $k=12$ and $t \leq 4$ . We obtain similar, but partial, results for $13 \leq k \leq 15$ . This represents progress on a variety of questions and conjectures in the literature concerning the sequenceability of subsets of abelian groups, which we combine and summarize into the conjecture that if a subset of an abelian group does not contain 0 then it is sequenceable.

preprint2022arXiv

The maximum cardinality of trifferent codes with lengths 5 and 6

A code $\mathcal{C} \subseteq \{0, 1, 2\}^n$ is said to be trifferent with length $n$ when for any three distinct elements of $\mathcal{C}$ there exists a coordinate in which they all differ. Defining $\mathcal{T}(n)$ as the maximum cardinality of trifferent codes with length $n$ , $\mathcal{T}(n)$ is unknown for $n \ge 5$ . In this note, we use an optimized search algorithm to show that $\mathcal{T}(5) = 10$ and $\mathcal{T}(6) = 13$ .

preprint2022arXiv

Weak Sequenceability in Cyclic Groups

A subset $A$ of an abelian group $G$ is sequenceable if there is an ordering $(a_1, \ldots, a_k)$ of its elements such that the partial sums $(s_0, s_1, \ldots, s_k)$ , given by $s_0 = 0$ and $s_i = \sum_{j=1}^i a_i$ for $1 \leq i \leq k$ , are distinct, with the possible exception that we may have $s_k = s_0 = 0$ . In the literature there are several conjectures and questions concerning the sequenceability of subsets of abelian groups, which have been combined and summarized in $[4]$ into the conjecture that if a subset of an abelian group does not contain 0 then it is sequenceable. If the elements of a sequenceable set $A$ do not sum to $0$ then there exists a simple path $P$ in the Cayley graph $Cay[G:\pm A]$ such that $Δ(P) = \pm A$ . In this paper, inspired by this graph-theoretical interpretation, we propose a weakening of this conjecture. Here, under the above assumptions, we want to find an ordering whose partial sums define a walk $W$ of girth bigger than $t$ (for a given $t < k$ ) and such that $Δ(W) = \pm A$ . This is possible given that the partial sums $s_i$ and $s_j$ are different whenever $i$ and $j$ are distinct and $|i-j|\leq t$ . In this case, we say that the set $A$ is $t$ -weak sequenceable. The main result here presented is that any subset $A$ of $\mathbb{Z}_p\setminus \{0\}$ is $t$ -weak sequenceable whenever $t<7$ or when $A$ does not contain pairs of type $\{x,-x\}$ and $t<8$ .

preprint2021arXiv

New upper bounds for $(b,k)$ -hashing

For fixed integers $b\geq k$ , the problem of perfect $(b,k)$ -hashing asks for the asymptotic growth of largest subsets of $\{1,2,\ldots,b\}^n$ such that for any $k$ distinct elements in the set, there is a coordinate where they all differ. An important asymptotic upper bound for general $b, k$ , was derived by Fredman and Komlós in the '80s and improved for certain $b\neq k$ by Körner and Marton and by Arikan. Only very recently better bounds were derived for the general $b,k$ case by Guruswami and Riazanov, while stronger results for small values of $b=k$ were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan and by Costa and Dalai. In this paper, we both show how some of the latter results extend to $b\neq k$ and further strengthen the bounds for some specific small values of $b$ and $k$ . The method we use, which depends on the reduction of an optimization problem to a finite number of cases, shows that further results might be obtained by refined arguments at the expense of higher complexity.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Stefano Della Fiore

Research overview

Is this your work?

7 publications

Achievable Rates and Algorithms for Group Testing with Runlength Constraints

Improved Bounds for $(b,k)$ -hashing

Non-zero sum Heffter arrays and their applications

On Sequences in Cyclic Groups with Distinct Partial Sums

The maximum cardinality of trifferent codes with lengths 5 and 6

Weak Sequenceability in Cyclic Groups

New upper bounds for $(b,k)$ -hashing

See the researcher in context

Building this map preview

Stefano Della Fiore

Research overview

Is this your work?

7 publications

Achievable Rates and Algorithms for Group Testing with Runlength Constraints

Improved Bounds for (b,k)(b,k)(b,k)-hashing

Non-zero sum Heffter arrays and their applications

On Sequences in Cyclic Groups with Distinct Partial Sums

The maximum cardinality of trifferent codes with lengths 5 and 6

Weak Sequenceability in Cyclic Groups

New upper bounds for (b,k)(b,k)(b,k)-hashing

See the researcher in context

Building this map preview

Improved Bounds for $(b,k)$ -hashing

New upper bounds for $(b,k)$ -hashing