
Proof of the \(K(\pi,1)\) conjecture for affine Artin groups
with Mario Salvetti
arXiv preprint 1907.11795,
2019
Show abstract
arXiv version
We prove the \(K(\pi,1)\) conjecture for affine Artin groups: the complexified complement of an affine reflection arrangement is a classifying space. This is a longstanding problem, due to Arnol'd, Pham, and Thom. Our proof is based on recent advancements in the theory of dual Coxeter and Artin groups, as well as on several new results and constructions. In particular: we show that all affine noncrossing partition posets are ELshellable; we use these posets to construct finite classifying spaces for dual affine Artin groups; we introduce new CW models for the orbit configuration spaces associated with arbitrary Coxeter groups; we construct finite classifying spaces for the braided crystallographic groups introduced by McCammond and Sulway.

Where is the information in a deep neural network?
with Alessandro Achille and Stefano Soatto
arXiv preprint 1905.12213,
2020
Show abstract
arXiv version
Whatever information a deep neural network has gleaned from past data is encoded in its weights. How this information affects the response of the network to future data is largely an open question. In fact, even how to define and measure information in a network entails some subtleties. We measure information in the weights of a deep neural network as the optimal tradeoff between accuracy of the network and complexity of the weights relative to a prior. Depending on the prior, the definition reduces to known information measures such as Shannon Mutual Information and Fisher Information, but in general it affords added flexibility that enables us to relate it to generalization, via the PACBayes bound, and to invariance. For the latter, we introduce a notion of effective information in the activations, which are deterministic functions of future inputs. We relate this to the information in the weights, and use this result to show that models of low (information) complexity not only generalize better, but are bound to learn invariant representations of future inputs. These relations hinge not only on the architecture of the model, but also on how it is trained.

Impossibility results on stability of phylogenetic consensus methods
with Emanuele Delucchi and Linard Hoessly
Systematic Biology 69 (3), pp. 557565,
2020
Show abstract
arXiv version
Published version
Code
We answer two questions raised by Bryant, Francis and Steel in their work on consensus methods in phylogenetics. Consensus methods apply to every practical instance where it is desired to aggregate a set of given phylogenetic trees (say, gene evolution trees) into a resulting, "consensus" tree (say, a species tree). Various stability criteria have been explored in this context, seeking to model desirable consistency properties of consensus methods as the experimental data is updated (e.g., more taxa, or more trees, are mapped). However, such stability conditions can be incompatible with some basic regularity properties that are widely accepted to be essential in any meaningful consensus method. Here, we prove that such an incompatibility does arise in the case of extension stability on binary trees and in the case of associative stability. Our methods combine general theoretical considerations with the use of computer programs tailored to the given stability requirements.

Shellability of generalized Dowling posets
Journal of Combinatorial Theory, Series A 171,
2020
Show abstract
arXiv version
Published version
A generalization of Dowling lattices was recently introduced by Bibby and Gadish, in a work on orbit configuration spaces. The authors left open the question as to whether these posets are shellable. In this paper we prove ELshellability and use it to determine the homotopy type. Our result generalizes shellability of Dowling lattices and of posets of layers of abelian arrangements defined by root systems. We also show that subposets corresponding to invariant subarrangements are not shellable in general.

A table of \(n\)component handlebody links of genus \(n+1\) up to six crossings
with Giovanni Bellettini, Maurizio Paolini, and YiSheng Wang
arXiv preprint 2003.03748,
2020
Show abstract
arXiv version
A handlebody link is a union of handlebodies of positive genus embedded in 3space, which generalizes the notion of links in classical knot theory. In this paper, we consider handlebody links with one genus 2 handlebody and \(n1\) solid tori, \(n>1\). Our main result is the complete classification of such handlebody links with six crossings or less, up to ambient isotopy.

On the local homology of Artin groups of finite and affine type
Algebraic & Geometric Topology 19 (7), pp. 36153639,
2019
Show abstract
arXiv version
Published version
Code
We study the local homology of Artin groups using weighted discrete Morse theory. In all finite and affine cases, we are able to construct Morse matchings of a special type (we call them "precise matchings"). The existence of precise matchings implies that the homology has a squarefree torsion. This property was known for Artin groups of finite type, but not in general for Artin groups of affine type. We also use the constructed matchings to compute the local homology in all exceptional cases, correcting some results in the literature.

Shellability of posets of labeled partitions and arrangements defined by root systems
with Emanuele Delucchi and Noriane Girard
Electronic Journal of Combinatorics 26 (4),
2019
Show abstract
arXiv version
Published version
We prove that the posets of connected components of intersections of toric and elliptic arrangements defined by root systems are ELshellable and we compute their homotopy type. Our method rests on Bibby's description of such posets by means of "labeled partitions": after giving an ELlabeling and counting homology chains for general posets of labeled partitions, we obtain the stated results by considering the appropriate subposets.

Representations of torsionfree arithmetic matroids
with Roberto Pagaria
arXiv preprint 1908.04137,
2019
Show abstract
arXiv version
Code
We study the representability problem for torsionfree arithmetic matroids. By using a new operation called "reduction" and a "signed Hermite normal form", we provide and implement an algorithm to compute all the representations, up to equivalence. As an application, we disprove two conjectures about the poset of layers and the independence poset of a toric arrangement.

The information complexity of learning tasks, their structure and their distance
with Alessandro Achille, Glen Mbeng, and Stefano Soatto
arXiv preprint 1904.03292,
2019
Show abstract
arXiv version
We introduce an asymmetric distance in the space of learning tasks, and a framework to compute their complexity. These concepts are foundational to the practice of transfer learning, ubiquitous in Deep Learning, whereby a parametric model is pretrained for a task, and then used for another after finetuning. The framework we develop is intrinsically nonasymptotic, capturing the finite nature of the training dataset, yet it allows distinguishing learning from memorization. It encompasses, as special cases, classical notions from Kolmogorov complexity, Shannon, and Fisher Information. However, unlike some of those frameworks, it can be applied easily to largescale models and realworld datasets. It is the first framework to explicitly account for the optimization scheme, which plays a crucial role in Deep Learning, in measuring complexity and information.

Weighted sheaves and homology of Artin groups
with Mario Salvetti
Algebraic & Geometric Topology 18 (7), pp. 39434000,
2018
Show abstract
arXiv version
Published version
In this paper we expand the theory of weighted sheaves over posets, and use it to study the local homology of Artin groups. First, we use such theory to relate the homology of classical braid groups with the homology of certain independence complexes of graphs. Then, in the context of discrete Morse theory on weighted sheaves, we introduce a particular class of acyclic matchings. Explicit formulas for the homology of the corresponding Morse complexes are given, in terms of the ranks of the associated incidence matrices. We use such method to perform explicit computations for the new affine case \(\tilde C_n\), as well as for the cases \(A_n\), \(B_n\) and \(\tilde A_n\) (which were already done before by different methods).

Euclidean matchings and minimality of hyperplane arrangements
with Davide Lofano
arXiv preprint 1809.02476,
2018
Show abstract
arXiv version
We construct a new class of maximal acyclic matchings on the Salvetti complex of a locally finite hyperplane arrangement. Using discrete Morse theory, we then obtain an explicit proof of the minimality of the complement. Our construction provides interesting insights also in the wellstudied case of finite arrangements, and gives a nice geometric description of the Betti numbers of the complement. The minimal complex is compatible with restrictions, and this allows us to prove the isomorphism of Brieskorn's Lemma by a simple bijection of the critical cells. Finally, in the case of line arrangements, we describe the algebraic Morse complex which computes the homology with coefficients in an abelian local system.

Collapsibility to a subcomplex of a given dimension is NPcomplete
Discrete & Computational Geometry 59 (1), pp. 246251,
2018
Show abstract
arXiv version
Published version
In this paper we extend the works of Tancer and of Malgouyres and Francés, showing that \((d,k)\)collapsibility is NPcomplete for \(d \geq k+2\) except \((2,0)\). By \((d,k)\)collapsibility we mean the following problem: determine whether a given \(d\)dimensional simplicial complex can be collapsed to some \(k\)dimensional subcomplex. The question of establishing the complexity status of \((d,k)\)collapsibility was asked by Tancer, who proved NPcompleteness of \((d,0)\) and \((d,1)\)collapsibility (for \(d \geq 3\)). Our extended result, together with the known polynomialtime algorithms for \((2,0)\) and \(d=k+1\), answers the question completely.

An algorithm for canonical forms of finite subsets of \(\mathbb{Z}^d\) up to affinities
Discrete & Computational Geometry 58 (2), pp. 293312,
2017
Show abstract
arXiv version
Published version
In this paper, we describe an algorithm for the computation of canonical forms of finite subsets of \(\mathbb{Z}^d\), up to affinities over \(\mathbb{Z}\). For fixed dimension \(d\), the worstcase asymptotic complexity of this algorithm is \(O(n \log^2 n \, s \, \mu(s))\), where \(n\) is the number of points in the given subset, \(s\) is an upper bound to the size of the binary representation of any of the \(n\) points, and \(\mu(s)\) is an upper bound to the number of operations required to multiply two \(s\)bit numbers. This problem arises e.g. in the context of invariants computation of finitely presented groups with abelianized group isomorphic to \(\mathbb{Z}^d\). In that context one needs to decide whether two Laurent polynomials in \(d\) indeterminates, considered as elements of the group ring over the abelianized group, are equivalent with respect to a change of basis.

On the classifying space of Artin monoids
Communications in Algebra 45 (11), pp. 47404757,
2017
Show abstract
arXiv version
Published version
A theorem proved by Dobrinskaya in 2006 shows that there is a strong connection between the \(K(\pi,1)\) conjecture for Artin groups and the classifying space of Artin monoids. More recently Ozornova obtained a different proof of Dobrinskaya's theorem based on the application of discrete Morse theory to the standard CW model of the classifying space of an Artin monoid. In Ozornova's work there are hints at some deeper connections between the abovementioned CW model and the Salvetti complex, a CW complex which arises in the combinatorial study of Artin groups. In this work we show that such connections actually exist, and as a consequence we derive yet another proof of Dobrinskaya's theorem.