Umberto Nanni

NeurIPS Conference 2025 Conference Paper

What are you sinking? A geometric approach on attention sink

• Valeria Ruscio
• Umberto Nanni
• Fabrizio Silvestri

Attention sink (AS) is a consistent pattern in transformer attention maps where certain tokens (often special tokens or positional anchors) disproportionately attract attention from other tokens. We show that in transformers, AS is not an architectural artifact, but it is the manifestation of a fundamental geometric principle: the establishment of reference frames that anchor representational spaces. We analyze several architectures and identify three distinct reference frame types, centralized, distributed, and bidirectional, that correlate with the attention sink phenomenon. We show that they emerge during the earliest stages of training as optimal solutions to the problem of establishing stable coordinate systems in high-dimensional spaces. We show the influence of architecture components, particularly position encoding implementations, on the specific type of reference frame. This perspective transforms our understanding of transformer attention mechanisms and provides insights for both architecture design and the relationship with AS.

TCS Journal 2011 Journal Article

Linear time analysis of properties of conflict-free and general Petri nets

• Paola Alimonti
• Esteban Feuerstein
• Luigi Laura
• Umberto Nanni

We introduce the notion of a T -path within Petri nets, and propose to adopt the model of directed hypergraphs in order to determine properties of nets; in particular, we study the relationships between T -paths and firable sequences of transitions. Let us consider a Petri net P = 〈 P, T, A, M 0 〉 and the set of places with a positive marking in M 0, i. e. , P 0 = { p ∣ M 0 ( p ) > 0 }. If we regard the net as a directed graph, the existence of a simple path from any place in P 0 to a transition t is, of course, a necessary condition for the potential firability of t. This is sufficient only if the net is a state machine, where | • t | = | t • | = 1 for all t ∈ T. In this paper we show that the existence of a T -path from any subset of P 0 to a transition t is a more restrictive condition and is, again, a necessary condition for the potential firability of t. But, in this case: (a) if P is a conflict-free Petri net, this is also a sufficient condition, (b) if P is a general Petri net, t is potentially firable by increasing the number of tokens in P 0. For conflict-free nets (CFPN) we consider the following problems: (a) determining the set of firable transitions, (b) determining the set of coverable places, (c) determining the set of live transitions, (d) deciding the boundedness of the net. For all these problems we provide algorithms requiring linear space and time, i. e. , O ( | P | + | T | + | A | ), for a net P = 〈 P, T, A, M 0 〉. Previous results for this class of networks are given by Howell et al. (1987) [20], providing algorithms for solving problems in conflict-free nets in O ( | P | × | T | ) time and space. Given a Petri net and a marking M, the well-known coverability problem consists in finding a reachable marking M ′ such that M ′ ≥ M; this problem is known to be EXPSPACE hard (Rackoff (1978)[33]). For general Petri nets we provide a partial answer to this problem. M is coverable by augmentation if it is coverable from an augmented marking M 0 ′ of the initial marking M 0: M 0 ′ ≥ M 0 and, for all p ∈ P, M 0 ′ ( p ) = 0 if M 0 ( p ) = 0. We solve this problem in linear time. The algorithms for computing T -paths are incremental: it is possible to modify the network (adding new places, transitions, arcs, tokens), and update the set of potentially firable transitions and coverable places without recomputing them from scratch. This feature is meaningful when used during the interactive design of a system.

TCS Journal 2003 Journal Article

A fully dynamic algorithm for distributed shortest paths

• Serafino Cicerone
• Gabriele Di Stefano
• Daniele Frigioni
• Umberto Nanni

We propose a fully dynamic distributed algorithm for the all-pairs shortest paths problem on general networks with positive real edge weights. If Δ σ is the number of pairs of nodes changing the distance after a single edge modification σ (insert, delete, weight decrease, or weight increase) then the message complexity of the proposed algorithm is O(nΔ σ ) in the worst case, where n is the number of nodes of the network. If Δσ = o(n2), this is better than recomputing everything from scratch after each edge modification. Up to now only a result of Ramarao and Venkatesan was known, stating that the problem of updating shortest paths in a dynamic distributed environment is as hard as that of computing shortest paths.

TCS Journal 2001 Journal Article

Dynamic algorithms for classes of constraint satisfaction problems

• Daniele Frigioni
• Alberto Marchetti-Spaccamela
• Umberto Nanni

Many fundamental tasks in artificial intelligence and in combinatorial optimization can be formulated as a Constraint Satisfaction Problem (CSP). It is the problem of finding an assignment of values for a set of variables, each defined on a finite domain of feasible values, subject to a given collection of constraints. Each constraint is defined over a set of variables and specifies the allowed combinations of values as a collection of tuples. In general, the problem of finding a solution to a CSP is NP-complete, but in some cases it has shown to be polynomially solvable. We consider the dynamic version of some polynomially solvable constraint satisfaction problems, and present solutions that are better than recomputing everything from scratch after each update. The updates we consider are either restrictions, i. e. , deletions of values from existing constraints and introduction of new constraints, or relaxations, i. e. , insertions of values or deletions of constraints.

TCS Journal 1998 Journal Article

A uniform approach to semi-dynamic problems on digraphs

• Serafino Cicerone
• Daniele Frigioni
• Umberto Nanni
• Francesco Pugliese

In this paper we propose a uniform approach to deal with incremental problems on digraphs and with decremental problems on dags generalizing a technique used by La Poutré and van Leeuwen in [17] for updating the transitive closure and the transitive reduction of a dag. We define a propagation property on a binary relationship over the vertices of a digraph as a simple sufficient condition to apply this approach. The proposed technique is suitable for a very simple implementation which does not depend on the particular problem; in other words, the same procedures can be used to deal with different problems by simply setting appropriate boundary conditions. In particular, we provide semi-dynamic algorithms and data structures for maintaining a binary relationship over the vertices of a digraph (dag) with n vertices and m edges, requiring O(n max {q, m}) total time for any sequence of q edge insertions (deletions). This gives O(n) amortized time per operation over a sequence of Ω(m) edge insertions (deletions). Queries can be answered in constant time. The space required is O(n 2). We apply the proposed technique to various problems about dominance, providing a solution to the problems of maintaining the dominance relationship, the dominator tree, and the nearest common dominator of a digraph in the incremental case, and of a dag in the decremental case; no dynamic solution was previously known for some of these problems. Finally we mention that the algorithms indeed work correctly also for interleaved sequences of insertion and deletion of edges in a dag, although the complexity bound holds for monotone sequence of updates only.

MFCS Conference 1998 Invited Paper

Hypergraph Traversal Revisited: Cost Measures and Dynamic Algorithms

• Giorgio Ausiello
• Giuseppe F. Italiano
• Umberto Nanni

Abstract Directed hypergraphs are used in several applications to model different combinatorial structures. A directed hypergraph is defined by a set of nodes and a set of hyperarcs, each connecting a set of source nodes to a single target node. A hyperpath, similarly to the notion of path in directed graphs, consists of a connection among nodes using hyperarcs. Unlike paths in graphs, however, hyperpaths are suitable of many different definitions of measure, corresponding to different concepts arising in various applications. In this paper we consider the problem of finding optimal hyperpaths according to several measures. We also provide results that may shed some light on the intrinsic complexity of finding optimal hyperpaths.

TCS Journal 1998 Journal Article

Multidimensional interval routing schemes

• Michele Flammini
• Giorgio Gambosi
• Umberto Nanni
• Richard B. Tan

Interval routing scheme (k-IRS) is a compact routing scheme on general networks. It has been studied extensively and recently been implemented on the latest generation INMOS Transputer Router chip. In this paper we introduce an extension of the Interval Routing Scheme k-IRS to the multidimensional case 〈k, d〉-MIRS, where k is the number of intervals and d is the number of dimensions. Whereas k-IRS only represents compactly a single shortest path between any two nodes, with this new extension we are able to represent all shortest paths compactly. This is useful for fault-tolerance and traffic distribution in a network. We study efficient representations of all shortest paths between any pair of nodes for general network topologies, for product graphs and for specific interconnection networks such as rings, grids, tori, hypercubes and chordal rings. For these interconnection networks we show that for about the same space complexity as k-IRS we can represent all shortest paths in 〈k, d〉-MIRS (as compared to only a single shortest path in k-IRS). Moreover, trade-offs are derived between the dimension d and the number of intervals k in multidimensional interval routing schemes on hypercubes, grids and tori.

SODA Conference 1996 Conference Paper

Fully Dynamic Output Bounded Single Source Shortest Path Problem (Extended Abstract)

• Daniele Frigioni
• Alberto Marchetti-Spaccamela
• Umberto Nanni

TCS Journal 1993 Journal Article

The weighted list update problem and the lazy adversary

• Fabrizio d'Amore
• Alberto Marchetti-Spaccamela
• Umberto Nanni

The list update problem consists in maintaining a dictionary as an unsorted linear list. Any request specifies an item to be found by sequential scanning through the list. After an item has been found, the list may be rearranged in order to reduce the cost of processing a sequence of requests. Several kinds of adversaries can be considered to analyze the behavior of heuristics for this problem. The move-to-front (MTF) heuristic is 2-competitive against a strong adversary, matching the deterministic lower bound for this problem [Sleator and Tarjan (1985)]. But, for this problem, moving elements does not help the adversary. A lazy adversary has the limitation that he can use only a static arrangement of the list to process (off-line) the sequence of requests: still, no algorithm can be better than 2-competitive against the lazy adversary [Bentley and McGeogh (1985)]. In this paper we consider the weighted list update problem (WLUP), where the cost of accessing an item depends on the item itself. It is shown that MTF is not competitive by any constant factor for this problem against a lazy adversary. Two heuristics, based on the MTF strategy, are presented for WLUP: random move-to-front is randomized and uses biased coins; counting move-to-front is deterministic, and replaces coins by counters. Both are shown to be 2-competitive against a lazy adversary. This is optimal for the deterministic case. We apply this approach for searching items in a tree, proving that any c-competitive heuristic for the weighted list update problem provides a c-competitive heuristic for the tree update problem.

TCS Journal 1992 Journal Article

On-line computation of minimal and maximal length paths

• Giorgio Ausiello
• Giuseppe F. Italiano
• Alberto Marchetti Spaccamela
• Umberto Nanni

We consider the problem of maintaining minimum length paths in a directed graph G=(V, E) with n nodes while inserting new arcs. A data structure which supports the following operations is presented: an add operation, which inserts an arc in the digraph, and a minpath operation, which returns a minimal length path between a pair of nodes. The data structure supports each minpath operation in O(k) worst case time, where k<n is the length of the returned path; moreover, if we assume that the weights of the arcs are integer numbers in the range [1…W], then the expected cost of any sequence of add operations is O(min(n 4, n 3max(W, logn))) time. The space complexity is O(n 2). The same algorithm can be used for solving the problem of maintaining maximum length paths when the digraph is acyclic and add operations preserve acyclicity.

TCS Journal 1990 Journal Article

Dynamic maintenance of directed hypergraphs

• Giorgio Ausiello
• Umberto Nanni
• Giuseppe F. Italiano

In this paper we are concerned with the on-line maintenance of directed hypergraphs, a generalization of directed graphs previously introduced in the literature. In particular, we show how to maintain efficiently information about hyperpaths while new hyperarcs are inserted. We present a data structure which allows us to check whether there exists a hyperpath between an arbitrarily given pair of nodes in constant time and to return such a hyperpath in a time which is linear in its size. The total time required to maintain the data structure during the insertion of new hyperarcs is O(mn), where m is the total size of the description of the hyperarcs and n is the number of nodes. This generalizes a previous result known for directed graphs and has applications in several areas of computer science, such as rewriting systems, database schemes, logic programming and problem solving. An extension of these results to hyperpaths between sets of nodes is also presented.

SODA Conference 1990 Conference Paper

Incremental Algorithms for Minimal Length Paths

• Giorgio Ausiello
• Giuseppe F. Italiano
• Alberto Marchetti-Spaccamela
• Umberto Nanni