Search

Catamorphisms are functions that are recursively defined on list and trees and, in general, on Algebraic Data Types (ADTs), and are often used to compute suitable abstractions of programs that manipulate ADTs. Examples of catamorphisms include functions that compute size of lists, orderedness of lists, and height of trees. It is well known that program properties specified through catamorphisms can be proved by showing the satisfiability of suitable sets of Constrained Horn Clauses (CHCs). We address the problem of checking the satisfiability of those sets of CHCs, and we propose a method for transforming sets of CHCs into equisatisfiable sets where catamorphisms are no longer present. As a consequence, clauses with catamorphisms can be handled without extending the satisfiability algorithms used by existing CHC solvers. Through an experimental evaluation on a non-trivial benchmark consisting of many list and tree processing algorithms expressed as sets of CHCs, we show that our technique is indeed effective and significantly enhances the performance of state-of-the-art CHC solvers., Comment: Under consideration in Theory and Practice of Logic Programming (TPLP)

This work continues to investigate the link between differentially private (DP) and online learning. Alon, Livni, Malliaris, and Moran (2019) showed that for binary concept classes, DP learnability of a given class implies that it has a finite Littlestone dimension (equivalently, that it is online learnable). Their proof relies on a model-theoretic result by Hodges (1997), which demonstrates that any binary concept class with a large Littlestone dimension contains a large subclass of thresholds. In a follow-up work, Jung, Kim, and Tewari (2020) extended this proof to multiclass PAC learning with a bounded number of labels. Unfortunately, Hodges's result does not apply in other natural settings such as multiclass PAC learning with an unbounded label space, and PAC learning of partial concept classes. This naturally raises the question of whether DP learnability continues to imply online learnability in more general scenarios: indeed, Alon, Hanneke, Holzman, and Moran (2021) explicitly leave it as an open question in the context of partial concept classes, and the same question is open in the general multiclass setting. In this work, we give a positive answer to these questions showing that for general classification tasks, DP learnability implies online learnability. Our proof reasons directly about Littlestone trees, without relying on thresholds. We achieve this by establishing several Ramsey-type theorems for trees, which might be of independent interest.

MV-monoids are algebras $\langle A,\vee,\wedge, \oplus,\odot, 0,1\rangle$ where $\langle A, \vee, \wedge, 0, 1\rangle$ is a bounded distributive lattice, both $\langle A, \oplus, 0 \rangle$ and $\langle A, \odot, 1\rangle$ are commutative monoids, and some further connecting axioms are satisfied. Every MV-algebra in the signature $\{\oplus,\neg,0\}$ is term equivalent to an algebra that has an MV-monoid as a reduct, by defining, as standard, $1:= \neg 0$, $x \odot y := \neg(\neg x \oplus\neg y)$, $x \vee y := (x \odot \neg y) \oplus y$ and $x \wedge y := \neg(\neg x \vee \neg y)$. Particular examples of MV-monoids are positive MV-algebras, i.e. the $\{\vee, \wedge, \oplus, \odot, 0, 1\}$-subreducts of MV-algebras. Positive MV-algebras form a peculiar quasivariety in the sense that, albeit having a logical motivation (being the quasivariety of subreducts of MV-algebras), it is not the equivalent quasivariety semantics of any logic. In this paper, we study the lattices of subvarieties of MV-monoids and of positive MV-algebras. In particular, we characterize and axiomatize all almost minimal varieties of MV-monoids, we characterize the finite subdirectly irreducible positive MV-algebras, and we characterize and axiomatize all varieties of positive MV-algebras.

The Plurality rule for linear orders selects the alternatives most frequently appearing in the first position of those orders, while the Anti-Plurality rule selects the alternatives least often occurring in the final position. We explore extensions of these rules to partial orders, offering axiomatic characterizations for these extensions.

The layer stacking morphology in nanocarbons is paramount for achieving new properties and outperforming applications. Here, we demonstrate that graphene quantum dots (GQDs) retain crystallinity and a stacking structure from CVD graphene grown on Ni foam. Our results reveal that GQD subdomains comprise a few-layer graphene structure in the AB -- AB and ABC -- ABC stacking configuration. HR-TEM images along with a multiple-approach characterization (XRD, XPS, UV-vis, AFM, and ATR-IR) exhibit 3.0 to 8.0 nm crystalline GQDs with 2-6 graphene layers thick indicating a disk-shape structure. The UV-vis profiles show changes in color of the dispersion (from colorless to red) during and after the electrochemistry, suggesting a systematic electrooxidation of graphene into smaller, highly crystalline, and more complex sp2/sp3 structures. Importantly, a control experiment performed under the same conditions but with a graphitic rod exhibited large, polydisperse, and multilayer carbon structures. This work demonstrates a relatively easy electrochemical synthesis to obtain GQDs which retain the pristine and, in turn, distinctive structure of graphene grown on Ni foam., Comment: 33 pages

In this paper, we complete the analysis initiated in [AFV24] establishing some higher order $C^{k+2,\alpha}$ Schauder estimates ($k \in \mathbb{N}$) for a a class of parabolic equations with weights that are degenerate/singular on a characteristic hyperplane. The $C^{2,\alpha}$-estimates are obtained through a blow-up argument and a Liouville theorem, while the higher order estimates are obtained by a fine iteration procedure. As a byproduct, we present two applications. First, we prove similar Schauder estimates when the degeneracy/singularity of the weight occurs on a regular hypersurface of cylindrical type. Second, we provide an alternative proof of the higher order boundary Harnack principles established in [BG16,Kuk22]., Comment: 30 pages

We consider the problem where a set of individuals has to classify $m$ objects into $p$ categories and does so by aggregating the individual classifications. We show that if $m\geq 3$, $m\geq p\geq 2$, and classifications are fuzzy, that is, objects belong to a category to a certain degree, then an optimal and independent aggregator rule that satisfies a weak unanimity condition belongs to the family of Weighted Arithmetic Means. We also obtain characterization results for $m= p= 2$.

This paper considers a strongly connected network of agents, each capable of partially observing and controlling a discrete-time linear time-invariant (LTI) system that is jointly observable and controllable. Additionally, agents collaborate to achieve a shared estimated state, computed as the average of their local state estimates. Recent studies suggest that increasing the number of average consensus steps between state estimation updates allows agents to choose from a wider range of state feedback controllers, thereby potentially enhancing control performance. However, such approaches require that agents know the input matrices of all other nodes, and the selection of control gains is, in general, centralized. Motivated by the limitations of such approaches, we propose a new technique where: (i) estimation and control gain design is fully distributed and finite-time, and (ii) agent coordination involves a finite-time exact average consensus algorithm, allowing arbitrary selection of estimation convergence rate despite the estimator's distributed nature. We verify our methodology's effectiveness using illustrative numerical simulations.

Formal verification of smart contracts has become a hot topic in academic and industrial research, given the growing value of assets managed by decentralized applications and the consequent incentive for adversaries to tamper with them. Most of the current research on the verification of contracts revolves around Solidity, the main high-level language supported by Ethereum and other leading blockchains. Although bug detection tools for Solidity have been proliferating almost since the inception of Ethereum, only in the last few years we have seen verification tools capable of proving that a contract respects some desirable properties. An open issue is how to evaluate and compare the effectiveness of these tools: indeed, the existing benchmarks for general-purpose programming languages cannot be adapted to Solidity, given substantial differences in the programming model and in the desirable properties. We address this problem by proposing an open benchmark for Solidity verification tools. By exploiting our benchmark, we compare two leading tools, SolCMC and Certora, discussing their completeness, soundness and expressiveness limitations.

We establish some $C^{0,\alpha}$ and $C^{1,\alpha}$ regularity estimates for a class of weighted parabolic problems in divergence form. The main novelty is that the weights may vanish or explode on a characteristic hyperplane $\Sigma$ as a power $a > -1$ of the distance to $\Sigma$. The estimates we obtain are sharp with respect to the assumptions on coefficients and data. Our methods rely on a regularization of the equation and some uniform regularity estimates combined with a Liouville theorem and an approximation argument. As a corollary of our main result, we obtain similar $C^{1,\alpha}$ estimates when the degeneracy/singularity of the weight occurs on a regular hypersurface of cylindrical type., Comment: Add some references

We give a geometric characterisation of those groups that arise as fixed subgroups of finite-order untwisted automorphisms of right-angled Artin groups (RAAGs). They are precisely the fundamental groups of a class of compact special cube complexes that we term "divisible". The main corollary is that surface groups arise as fixed subgroups of finite-order automorphisms of RAAGs, as do all commutator subgroups of right-angled Coxeter groups. These appear to be the first examples of such fixed subgroups that are not themselves isomorphic to RAAGs. Using a variation of canonical completions, we also observe that every special group arises as the fixed subgroup of an automorphism of a finite-index subgroup of a RAAG., Comment: 27 pages, 5 figures; v2: minor edits, to appear in Transactions of the AMS

Hedonic Games (HGs) are a classical framework modeling coalition formation of strategic agents guided by their individual preferences. According to these preferences, it is desirable that a coalition structure (i.e. a partition of agents into coalitions) satisfies some form of stability. The most well-known and natural of such notions is arguably core-stability. Informally, a partition is core-stable if no subset of agents would like to deviate by regrouping in a so-called core-blocking coalition. Unfortunately, core-stable partitions seldom exist and even when they do, it is often computationally intractable to find one. To circumvent these problems, we propose the notion of $\varepsilon$-fractional core-stability, where at most an $\varepsilon$-fraction of all possible coalitions is allowed to core-block. It turns out that such a relaxation may guarantee both existence and polynomial-time computation. Specifically, we design efficient algorithms returning an $\varepsilon$-fractional core-stable partition, with $\varepsilon$ exponentially decreasing in the number of agents, for two fundamental classes of HGs: Simple Fractional and Anonymous. From a probabilistic point of view, being the definition of $\varepsilon$-fractional core equivalent to requiring that uniformly sampled coalitions core-block with probability lower than $\varepsilon$, we further extend the definition to handle more complex sampling distributions. Along this line, when valuations have to be learned from samples in a PAC-learning fashion, we give positive and negative results on which distributions allow the efficient computation of outcomes that are $\varepsilon$-fractional core-stable with arbitrarily high confidence., Comment: Accepted as poster at NeurIPS 2023

Achieving versatile routes to generate crystalline carbon-based nanostructures has become a fervent pursuit in photocatalysis-related fields. We demonstrate that the direct electrooxidation of ethanol, performed on Ni foam, yields ultra-small and highly crystalline graphene-like structures named carbon quantum dots (CQDs). We perform simulations of various sp2 and sp3 domains in order to understand the optical properties of CQDs by accounting their contribution as absorbance/luminescent centers in the overall optical response. Experiments and simulations reveal that absorbance bands for as-synthesized CQDs are dominated by small sp2 domains comprised of r7 aromatic-rings. After 48 h synthesis, the dispersion transition from yellow to red, exhibiting new and red shifted absorbance bands. Furthermore, fluorescence emission is governed by medium-sized sp 2 domains (with aromatic ring counts r12) and oxygen-containing groups. These oxygen-rich groups within the CQDs, confirmed by FT-IR and XPS, are responsible for the fast photodegradation of organic dyes, with B90% of methylene blue (MB) being degraded within the first 5 min of light exposure. Our work provides crucial insights about the electrochemical synthesis and overall optical properties of carbon nanostructures, while being effective and reliable toward the degradation of contaminants in water.

We seek to gain more insight into the effect of the crowds on the Home Advantage by analyzing the particular case of Argentinean football (also known as soccer), where for more than ten years, the visiting team fans were not allowed to attend the games. Additionally, during the COVID-19 lockdown, a significant number of games were played without both away and home team fans. The analysis of more than 20 years of matches of the Argentinean tournament indicates that the absence of the away team crowds was beneficial for the Top 5 teams during the first two years after their attendance was forbidden. An additional intriguing finding is that the lack of both crowds affects significantly all the teams, to the point of turning the home advantage into home `disadvantage' for most of the teams.

The rise of Artificial Intelligence (AI) recently empowered researchers to investigate hard mathematical problems which eluded traditional approaches for decades. Yet, the use of AI in Universal Algebra (UA) -- one of the fields laying the foundations of modern mathematics -- is still completely unexplored. This work proposes the first use of AI to investigate UA's conjectures with an equivalent equational and topological characterization. While topological representations would enable the analysis of such properties using graph neural networks, the limited transparency and brittle explainability of these models hinder their straightforward use to empirically validate existing conjectures or to formulate new ones. To bridge these gaps, we propose a general algorithm generating AI-ready datasets based on UA's conjectures, and introduce a novel neural layer to build fully interpretable graph networks. The results of our experiments demonstrate that interpretable graph networks: (i) enhance interpretability without sacrificing task accuracy, (ii) strongly generalize when predicting universal algebra's properties, (iii) generate simple explanations that empirically validate existing conjectures, and (iv) identify subgraphs suggesting the formulation of novel conjectures.

Explainable AI (XAI) aims to address the human need for safe and reliable AI systems. However, numerous surveys emphasize the absence of a sound mathematical formalization of key XAI notions -- remarkably including the term "explanation" which still lacks a precise definition. To bridge this gap, this paper presents the first mathematically rigorous definitions of key XAI notions and processes, using the well-funded formalism of Category theory. We show that our categorical framework allows to: (i) model existing learning schemes and architectures, (ii) formally define the term "explanation", (iii) establish a theoretical basis for XAI taxonomies, and (iv) analyze commonly overlooked aspects of explaining methods. As a consequence, our categorical framework promotes the ethical and secure deployment of AI technologies as it represents a significant step towards a sound theoretical foundation of explainable AI.