
Proof of the \(K(\pi,1)\) conjecture for affine Artin groups
with Mario Salvetti
Inventiones Mathematicae 224, pp. 487572,
2021
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.

Structured prediction as translation between augmented natural languages
with Ben Athiwaratkun, Jason Krone, Jie Ma, Alessandro Achille, Rishita Anubhai, Cicero Nogueira dos Santos, Bing Xiang, and Stefano Soatto
International Conference on Learning Representations (ICLR),
2021
We propose a new framework, Translation between Augmented Natural Languages (TANL), to solve many structured prediction language tasks including joint entity and relation extraction, nested named entity recognition, relation classification, semantic role labeling, event extraction, coreference resolution, and dialogue state tracking. Instead of tackling the problem by training taskspecific discriminative classifiers, we frame it as a translation task between augmented natural languages, from which the taskrelevant information can be easily extracted. Our approach can match or outperform taskspecific models on all tasks, and in particular achieves new stateoftheart results on joint entity and relation extraction (CoNLL04, ADE, NYT, and ACE2005 datasets), relation classification (FewRel and TACRED), and semantic role labeling (CoNLL2005 and CoNLL2012). We accomplish this while using the same architecture and hyperparameters for all tasks, and even when training a single model to solve all tasks at the same time (multitask learning). Finally, we show that our framework can also significantly improve the performance in a lowresource regime, thanks to better use of label semantics.

Factoring isometries of quadratic spaces into reflections
with Jon McCammond
arXiv preprint 2103.02507,
2021
Let \(V\) be a vector space endowed with a nondegenerate quadratic form \(Q\). If the base field \(\mathbb{F}\) is different from \(\mathbb{F}_2\), it is known that every isometry can be written as a product of reflections. In this article, we detail the structure of the poset of all minimal length reflection factorizations of an isometry. If \(\mathbb{F}\) is an ordered field, we also study factorizations into positive reflections, i.e., reflections defined by vectors of positive norm. We characterize such factorizations, under the hypothesis that the squares of \(\mathbb{F}\) are dense in the positive elements (this includes Archimedean and Euclidean fields). In particular, we show that an isometry is a product of positive reflections if and only if its spinor norm is positive. As a final application, we explicitly describe the poset of all factorizations of isometries of the hyperbolic space.

Estimating informativeness of samples with smooth unique information
with Hrayr Harutyunyan, Alessandro Achille, Orchid Majumder, Avinash Ravichandran, Rahul Bhotika, and Stefano Soatto
International Conference on Learning Representations (ICLR),
2021
We define a notion of information that an individual sample provides to the training of a neural network, and we specialize it to measure both how much a sample informs the final weights and how much it informs the function computed by the weights. Though related, we show that these quantities have a qualitatively different behavior. We give efficient approximations of these quantities using a linearized network and demonstrate empirically that the approximation is accurate for realworld architectures, such as pretrained ResNets. We apply these measures to several problems, such as dataset summarization, analysis of undersampled classes, comparison of informativeness of different data sources, and detection of adversarial and corrupted examples. Our work generalizes existing frameworks, but enjoys better computational properties for heavily overparametrized models, which makes it possible to apply it to realworld networks.

Euclidean matchings and minimality of hyperplane arrangements
with Davide Lofano
Discrete Mathematics 344 (3),
2021
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. In particular, we solve a conjecture of Drton and Klivans on the characteristic polynomial of finite reflection arrangements. 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.

Representations of torsionfree arithmetic matroids
with Roberto Pagaria
European Journal of Combinatorics 93,
2021
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
Information and Inference: a Journal of the IMA,
2021
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.

Impossibility results on stability of phylogenetic consensus methods
with Emanuele Delucchi and Linard Hoessly
Systematic Biology 69 (3), pp. 557565,
2020
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.

Where is the information in a deep neural network?
with Alessandro Achille and Stefano Soatto
arXiv preprint 1905.12213,
2020
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.

Shellability of generalized Dowling posets
Journal of Combinatorial Theory, Series A 171,
2020
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
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
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
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.

Weighted sheaves and homology of Artin groups
with Mario Salvetti
Algebraic & Geometric Topology 18 (7), pp. 39434000,
2018
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).

Collapsibility to a subcomplex of a given dimension is NPcomplete
Discrete & Computational Geometry 59 (1), pp. 246251,
2018
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
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
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.