Research

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 long-standing 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 EL-shellable; 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.

Inspired by long-standing open problems in algebraic combinatorics, we show that modern machine learning can meaningfully contribute to verifiable mathematical discoveries. In particular, we focus on the construction of simple mathematical functions under exact distributional constraints, a setting we formalize as Simple Learning Under Rigid Proportions (SLURP). We tackle this problem by introducing two methods: MapSeek-Functional, which models the desired function alternating pseudo-labeling and supervised training steps; and MapSeek-Symbolic, designed to directly produce symbolic formulas. We successfully apply both methods to a research problem in algebraic combinatorics, discovering a new combinatorial interpretation of the \(q,t\)-Narayana polynomials arising from representation theory. To our knowledge, this is the first such interpretation based on noncrossing partitions. Using one discovered statistic, we find a combinatorial proof of the symmetry of these polynomials in a previously unsolved case. To streamline verification and reproducibility, we release all code, including a formalization of all the mathematical discoveries of this paper in Lean 4.

In this paper, we formulate a rational analog of the fall Delta theorem and the Delta square conjecture. We find a new dinv statistic on fall-decorated paths on a \( (m+k) \times (n+k) \) rectangle that simultaneously extends the previously known dinv statistics on decorated square objects and non-decorated rectangular objects. We prove a symmetric function formula for the \( q,t \)-generating function of fall-decorated rectangular Dyck paths as a skewing operator applied to \( e_{m,n+km} \) and, conditionally on the rectangular paths conjecture, an analog formula for fall-decorated rectangular paths.

We report on the Equational Theories Project (ETP), an online collaborative pilot project to explore new ways to collaborate in mathematics with machine assistance. The project successfully determined all 22 028 942 edges of the implication graph between the 4694 simplest equational laws on magmas, by a combination of human-generated and automated proofs, all validated by the formal proof assistant language Lean. As a result of this project, several new constructions of magmas satisfying specific laws were discovered, and several auxiliary questions were also addressed, such as the effect of restricting attention to finite magmas.

We extend the theory of dual Coxeter and Artin groups to all rank-three Coxeter systems, beyond the previously studied spherical and affine cases. Using geometric, combinatorial, and topological techniques, we show that rank-three noncrossing partition posets are EL-shellable lattices and give rise to Garside groups isomorphic to the associated standard Artin groups. Within this framework, we prove the \(K(\pi,1)\) conjecture, the triviality of the center, and the solubility of the word problem for rank-three Artin groups. Some of our constructions apply to general Artin groups; we hope they will help develop complete solutions to the \(K(\pi,1)\) conjecture and other open problems in the area.

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 task-specific discriminative classifiers, we frame it as a translation task between augmented natural languages, from which the task-relevant information can be easily extracted. Our approach can match or outperform task-specific models on all tasks, and in particular achieves new state-of-the-art results on joint entity and relation extraction (CoNLL04, ADE, NYT, and ACE2005 datasets), relation classification (FewRel and TACRED), and semantic role labeling (CoNLL-2005 and CoNLL-2012). 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 (multi-task learning). Finally, we show that our framework can also significantly improve the performance in a low-resource regime, thanks to better use of label semantics.

We prove several results on the model theory of Artin groups, focusing on Artin groups which are "far from right-angled Artin groups". The first result is that if \(\mathcal{C}\) is a class of Artin groups whose irreducible components are acylindrically hyperbolic and torsion-free, then the model theory of Artin groups of type \(\mathcal{C}\) reduces to the model theory of its irreducible components. The second result is that the problem of superstability of a given non-abelian Artin group \(A\) reduces to certain dihedral parabolic subgroups of \(A\) being \(n\)-pure in \(A\), for certain large enough primes \(n \in \mathbb{N}\). The third result is that two spherical Artin groups are elementary equivalent if and only if they are isomorphic. Finally, we prove that the affine Artin groups of type \(\tilde{A}_n\), for \(n \geq 4\), can be distinguished from the other simply laced affine Artin groups using existential sentences; this uses homology results of independent interest relying on the recent proof of the \(K(\pi, 1)\) conjecture for affine Artin groups.

In large language model training, input documents are typically concatenated together and then split into sequences of equal length to avoid padding tokens. Despite its efficiency, the concatenation approach compromises data integrity -- it inevitably breaks many documents into incomplete pieces, leading to excessive truncations that hinder the model from learning to compose logically coherent and factually consistent content that is grounded on the complete context. To address the issue, we propose Best-fit Packing, a scalable and efficient method that packs documents into training sequences through length-aware combinatorial optimization. Our method completely eliminates unnecessary truncations while retaining the same training efficiency as concatenation. Empirical results from both text and code pre-training show that our method achieves superior performance (e.g., relatively +4.7% on reading comprehension; +16.8% in context following; and +9.2% on program synthesis), and reduces closed-domain hallucination effectively by up to 58.3%.

This paper introduces ZeusAI, an artificial intelligence system developed to play the board game 7 Wonders Duel. Inspired by the AlphaZero reinforcement learning algorithm, ZeusAI relies on a combination of Monte Carlo Tree Search and a Transformer Neural Network to learn the game without human supervision. ZeusAI competes at the level of top human players, develops both known and novel strategies, and allows us to test rule variants to improve the game's balance. This work demonstrates how AI can help in understanding and enhancing board games.

We enumerate all genus two handlebody-knots with seven crossings, up to mirror image, extending the Ishii-Kishimoto-Moriuchi-Suzuki table.

We study tangle replacement in the context of spatial graphs. The main results show that, for certain spatial handcuff graphs, there is a one-to-one correspondence between the neighborhood equivalence classes of the spatial graphs obtained by tangle replacement and the tangles with which the replacement is performed, up to possibly some permutation. As corollaries, we distinguish handlebody-knots difficult to differentiate with computational invariants and determine their chirality and symmetry groups.

In this summary paper, we present the key ideas behind the recent proof of the \( K(\pi,1) \) conjecture for affine Artin groups, which states that complements of locally finite affine hyperplane arrangements with real equations and stable under orthogonal reflections are aspherical. We survey three facets of the argument: the combinatorics of noncrossing partition posets associated with Coxeter groups; the appearance of dual Artin groups and the question of their isomorphism with standard Artin groups; the topological models and their interplay in the proof.

Dual presentations of Coxeter groups have recently led to breakthroughs in our understanding of affine Artin groups. In particular, they led to the proof of the \(K(\pi, 1)\) conjecture and to the solution of the word problem. Will the "dual approach" extend to more general classes of Coxeter and Artin groups? In this paper, we describe the techniques used to prove the \(K(\pi, 1)\) conjecture for affine Artin groups and we ask a series of questions that are mostly open beyond the spherical and affine cases.

Synthetic data generation with Large Language Models is a promising paradigm for augmenting natural data over a nearly infinite range of tasks. Given this variety, direct comparisons among synthetic data generation algorithms are scarce, making it difficult to understand where improvement comes from and what bottlenecks exist. We propose to evaluate algorithms via the makeup of synthetic data generated by each algorithm in terms of data quality, diversity, and complexity. We choose these three characteristics for their significance in open-ended processes and the impact each has on the capabilities of downstream models. We find quality to be essential for in-distribution model generalization, diversity to be essential for out-of-distribution generalization, and complexity to be beneficial for both. Further, we emphasize the existence of Quality-Diversity trade-offs in training data and the downstream effects on model performance. We then examine the effect of various components in the synthetic data pipeline on each data characteristic. This examination allows us to taxonomize and compare synthetic data generation algorithms through the components they utilize and the resulting effects on data QDC composition. This analysis extends into a discussion on the importance of balancing QDC in synthetic data for efficient reinforcement learning and self-improvement algorithms. Analogous to the QD trade-offs in training data, often there exist trade-offs between model output quality and output diversity which impact the composition of synthetic data. We observe that many models are currently evaluated and optimized only for output quality, thereby limiting output diversity and the potential for self-improvement. We argue that balancing these trade-offs is essential to the development of future self-improvement algorithms and highlight a number of works making progress in this direction.

Many of the recent capabilities demonstrated by Large Language Models (LLMs) arise primarily from their ability to exploit contextual information. In this paper, we explore ways to improve reasoning capabilities of LLMs through (1) exploration of different chains of thought and (2) validation of the individual steps of the reasoning process. We propose three general principles that a model should adhere to while reasoning: (i) Relevance, (ii) Mathematical Accuracy, and (iii) Logical Consistency. We apply these constraints to the reasoning steps generated by the LLM to improve the accuracy of the final generation. The constraints are applied in the form of verifiers: the model itself is asked to verify if the generated steps satisfy each constraint. To further steer the generations towards high-quality solutions, we use the perplexity of the reasoning steps as an additional verifier. We evaluate our method on 4 distinct types of reasoning tasks, spanning a total of 9 different datasets. Experiments show that our method is always better than vanilla generation, and, in 6 out of the 9 datasets, it is better than best-of N sampling which samples N reasoning chains and picks the lowest perplexity generation.

We explore how weak supervision on abundant unlabeled data can be leveraged to improve few-shot performance in aspect-based sentiment analysis (ABSA) tasks. We propose a pipeline approach to construct a noisy ABSA dataset, and we use it to adapt a pre-trained sequence-to-sequence model to the ABSA tasks. We test the resulting model on three widely used ABSA datasets, before and after fine-tuning. Our proposed method preserves the full fine-tuning performance while showing significant improvements (15.84 absolute F1) in the few-shot learning scenario for the harder tasks. In zero-shot (i.e., without fine-tuning), our method outperforms the previous state of the art on the aspect extraction sentiment classification (AESC) task and is, additionally, capable of performing the harder aspect sentiment triplet extraction (ASTE) task.

Training a Named Entity Recognition (NER) model often involves fixing a taxonomy of entity types. However, requirements evolve and we might need the NER model to recognize additional entity types. A simple approach is to re-annotate entire dataset with both existing and additional entity types and then train the model on the re-annotated dataset. However, this is an extremely laborious task. To remedy this, we propose a novel approach called Partial Label Model (PLM) that uses only partially annotated datasets. We experiment with 6 diverse datasets and show that PLM consistently performs better than most other approaches (0.5 - 2.5 F1), including in novel settings for taxonomy expansion not considered in prior work. The gap between PLM and all other approaches is especially large in settings where there is limited data available for the additional entity types (as much as 11 F1), thus suggesting a more cost effective approaches to taxonomy expansion.

In this paper, we extend the rectangular side of the shuffle conjecture by stating a rectangular analogue of the square paths conjecture. In addition, we describe a set of combinatorial objects and one statistic that are a first step towards a rectangular extension of (the rise version of) the Delta conjecture, and of (the rise version of) the Delta square conjecture, corresponding to the case \( q=1 \) of an expected general statement. We also prove our new rectangular paths conjecture in the special case when the sides of the rectangle are coprime.

We introduce À-la-carte Prompt Tuning (APT), a transformer-based scheme to tune prompts on distinct data so that they can be arbitrarily composed at inference time. The individual prompts can be trained in isolation, possibly on different devices, at different times, and on different distributions or domains. Furthermore each prompt only contains information about the subset of data it was exposed to during training. During inference, models can be assembled based on arbitrary selections of data sources, which we call "à-la-carte learning". À-la-carte learning enables constructing bespoke models specific to each user's individual access rights and preferences. We can add or remove information from the model by simply adding or removing the corresponding prompts without retraining from scratch. We demonstrate that à-la-carte built models achieve accuracy within 5% of models trained on the union of the respective sources, with comparable cost in terms of training and inference time. For the continual learning benchmarks Split CIFAR-100 and CORe50, we achieve state-of-the-art performance.

A handlebody link is a union of handlebodies of positive genus embedded in 3-space, which generalizes the notion of links in classical knot theory. In this paper, we consider handlebody links with a genus 2 handlebody and \(n-1\) solid tori, \(n>1\). Our main result is the classification of such handlebody links with six crossings or less, up to ambient isotopy.

We present a method to compute the derivative of a learning task with respect to a dataset. A learning task is a function from a training set to the validation error, which can be represented by a trained deep neural network (DNN). The "dataset derivative" is a linear operator, computed around the trained model, that informs how perturbations of the weight of each training sample affect the validation error, usually computed on a separate validation dataset. Our method, DIVA (Differentiable Validation) hinges on a closed-form differentiable expression of the leave-one-out cross-validation error around a pre-trained DNN. Such expression constitutes the dataset derivative. DIVA could be used for dataset auto-curation, for example removing samples with faulty annotations, augmenting a dataset with additional relevant samples, or rebalancing. More generally, DIVA can be used to optimize the dataset, along with the parameters of the model, as part of the training process without the need for a separate validation dataset, unlike bi-level optimization methods customary in AutoML. To illustrate the flexibility of DIVA, we report experiments on sample auto-curation tasks such as outlier rejection, dataset extension, and automatic aggregation of multi-modal data.

Let \(V\) be a vector space endowed with a non-degenerate 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.

We present an end-to-end differentiable neural network architecture to perform anomaly detection in multivariate time series by incorporating a Sequential Probability Ratio Test on the prediction residual. The architecture is a cascade of dynamical systems designed to separate linearly predictable components of the signal such as trends and seasonality, from the non-linear ones. The former are modeled by local Linear Dynamic Layers, and their residual is fed to a generic Temporal Convolutional Network that also aggregates global statistics from different time series as context for the local predictions of each one. The last layer implements the anomaly detector, which exploits the temporal structure of the prediction residuals to detect both isolated point anomalies and set-point changes. It is based on a novel application of the classic CUMSUM algorithm, adapted through the use of a variational approximation of f-divergences. The model automatically adapts to the time scales of the observed signals. It approximates a SARIMA model at the get-go, and auto-tunes to the statistics of the signal and its covariates, without the need for supervision, as more data is observed. The resulting system, which we call STRIC, outperforms both state-of-the-art robust statistical methods and deep neural network architectures on multiple anomaly detection benchmarks.

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 real-world architectures, such as pre-trained ResNets. We apply these measures to several problems, such as dataset summarization, analysis of under-sampled 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 over-parametrized models, which makes it possible to apply it to real-world networks.

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 well-studied 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.

We study the representability problem for torsion-free 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.

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 pre-trained for a task, and then used for another after fine-tuning. The framework we develop is intrinsically non-asymptotic, 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 large-scale models and real-world 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.

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.

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 trade-off 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 PAC-Bayes 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.

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 EL-shellability 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.

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 square-free 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.

We prove that the posets of connected components of intersections of toric and elliptic arrangements defined by root systems are EL-shellable and we compute their homotopy type. Our method rests on Bibby's description of such posets by means of "labeled partitions": after giving an EL-labeling and counting homology chains for general posets of labeled partitions, we obtain the stated results by considering the appropriate subposets.

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).

In this paper we extend the works of Tancer and of Malgouyres and Francés, showing that \((d,k)\)-collapsibility is NP-complete 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 NP-completeness of \((d,0)\) and \((d,1)\)-collapsibility (for \(d \geq 3\)). Our extended result, together with the known polynomial-time algorithms for \((2,0)\) and \(d=k+1\), answers the question completely.

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 worst-case 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.