OpenRaiser/Intern-Atlas huggingface dataset:
On the Existence of Algebraic Natural Proofs
Venue: arXiv cs.CC 2025
Year: 2025

The framework of algebraically natural proofs was independently introduced in the works of Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017), to study the efficacy of commonly used techniques for proving lower bounds in algebraic complexity. We use the known connections between algebraic hardness and pseudorandomness to shed some more light on the question relating to this framework, as follows. 1. The subclass of $\mathsf{VP}$ that contains polynomial families with bounded coefficients, has efficient equations. Over finite fields, this result holds without any restriction on coefficients. Further, both these results extend to \emph{any} class that admits a low-variate, low-degree universal map: a generator for all polynomials in the class. Most well-studied classes have this property, e.g. \textsf{VNP}, \textsf{VBP}, \textsf{VF}. 2. Over fields of characteristic zero, $\mathsf{VNP}$ does not have any efficient equations, if the Permanent is exponentially hard for algebraic circuits. Moreover, exponential hardness of the Permanent in the approximative sense, even rules out efficient equations of large degree. This gives the only known barrier to ``natural'' lower bound techniques (that follows from believable hardness assumptions), and also shows that the restriction on coefficients in the first category of results about $\mathsf{VNP}$ is necessary. The first set of results follows essentially by algebraizing the well-known method of generating hardness from non-trivial hitting sets (e.g. Heintz and Schnorr 1980). The conditional hardness of equations for $\mathsf{VNP}$ uses the fact that pseudorandomness against a class can be extracted from a polynomial that is (sufficiently) hard for that class (Kabanets and Impagliazzo, 2004).
LIMEtree: Consistent and Faithful Surrogate Explanations of Multiple Classes
Venue: arXiv cs.LG 2025
Year: 2025

Explainable artificial intelligence provides tools to better understand predictive models and their decisions, but many such methods are limited to producing insights with respect to a single class. When generating explanations for several classes, reasoning over them to obtain a comprehensive view may be difficult since they can present competing or contradictory evidence. To address this challenge we introduce the novel paradigm of multi-class explanations. We outline the theory behind such techniques and propose a local surrogate model based on multi-output regression trees -- called LIMEtree -- that offers faithful and consistent explanations of multiple classes for individual predictions while being post-hoc, model-agnostic and data-universal. On top of strong fidelity guarantees, our implementation delivers a range of diverse explanation types, including counterfactual statements favoured in the literature. We evaluate our algorithm with respect to explainability desiderata, through quantitative experiments and via a pilot user study, on image and tabular data classification tasks, comparing it to LIME, which is a state-of-the-art surrogate explainer. Our contributions demonstrate the benefits of multi-class explanations and wide-ranging advantages of our method across a diverse set of scenarios.
Normalized Convolutional Neural Network
Venue: arXiv cs.CV 2025
Year: 2025

We introduce a Normalized Convolutional Neural Layer, a novel approach to normalization in convolutional networks. Unlike conventional methods, this layer normalizes the rows of the im2col matrix during convolution, making it inherently adaptive to sliced inputs and better aligned with kernel structures. This distinctive approach differentiates it from standard normalization techniques and prevents direct integration into existing deep learning frameworks optimized for traditional convolution operations. Our method has a universal property, making it applicable to any deep learning task involving convolutional layers. By inherently normalizing within the convolution process, it serves as a convolutional adaptation of Self-Normalizing Networks, maintaining their core principles without requiring additional normalization layers. Notably, in micro-batch training scenarios, it consistently outperforms other batch-independent normalization methods. This performance boost arises from standardizing the rows of the im2col matrix, which theoretically leads to a smoother loss gradient and improved training stability.
Zone Theorem for Arrangements in three dimensions
Venue: arXiv cs.CG 2025
Year: 2025

In this note, a simple description of zone theorem in three dimensions is given.Arrangements in three dimensions are useful for constructing higher-order Voronoi diagrams in plane. An elementary and very intuitive treatment of this result is also given.
Algorithmically Optimal Outer Measures
Venue: arXiv cs.CC 2025
Year: 2025

We investigate the relationship between algorithmic fractal dimensions and the classical local fractal dimensions of outer measures in Euclidean spaces. We introduce global and local optimality conditions for lower semicomputable outer measures. We prove that globally optimal outer measures exist. Our main theorem states that the classical local fractal dimensions of any locally optimal outer measure coincide exactly with the algorithmic fractal dimensions. Our proof uses an especially convenient locally optimal outer measure $\boldsymbolκ$ defined in terms of Kolmogorov complexity. We discuss implications for point-to-set principles.
Local structure of idempotent algebras I
Venue: arXiv cs.LO 2025
Year: 2025

We refine and advance the study of the local structure of idempotent finite algebras started in [A.Bulatov, The Graph of a Relational Structure and Constraint Satisfaction Problems, LICS, 2004]. We introduce a graph-like structure on an arbitrary finite idempotent algebra including those admitting type 1. We show that this graph is connected, its edges can be classified into 4 types corresponding to the local behavior (set, semilattice, majority, or affine) of certain term operations. We also show that if the variety generated by the algebra omits type 1, then the structure of the algebra can be `improved' without introducing type 1 by choosing an appropriate reduct of the original algebra. Taylor minimal idempotent algebras introduced recently is a special case of such reducts. Then we refine this structure demonstrating that the edges of the graph of an algebra omitting type 1 can be made `thin', that is, there are term operations that behave very similar to semilattice, majority, or affine operations on 2-element subsets of the algebra. Finally, we prove certain connectivity properties of the refined structures. This research is motivated by the study of the Constraint Satisfaction Problem, although the problem itself does not really show up in this paper.
Coinductive proof search for polarized logic with applications to full intuitionistic propositional logic
Venue: arXiv cs.LO 2025
Year: 2025

The approach to proof search dubbed "coinductive proof search" (CoIPS), and previously developed by the authors for implicational intuitionistic logic, is in this paper extended to LJP, a focused sequent-calculus presentation of polarized intuitionistic logic, including an array of positive and negative connectives. As before, this includes developing a coinductive description of the search space generated by a sequent, an equivalent inductive syntax describing the same space, and decision procedures for inhabitation problems in the form of predicates defined by recursion on the inductive syntax. Inhabitation is taken in a generalized sense, because we also consider when a sequent has a solution, that is a (possibly infinite) run of bottom-up proof search which never fails to apply another inference rule. We provide a very general scheme whose instances are decision problems concerning solutions in LJP having algorithms through the inductive syntax. Polarized logic and LJP can be used as a platform from which proof search for other logics is understood. We illustrate this for the proof systems LJT and LJQ for intuitionistic logic, both equipped with all the connectives. For that we work out respectively a negative and a positive interpretation into LJP, which map formulas of the source logic into formulas in LJP of the said polarity; and this even at the level of the coinductive versions of the three involved proof systems. The interpretations are proved to be, not only faithful, but actually full embeddings, establishing a bijection between the solutions (resp. proofs) of a sequent and the solutions (resp. proofs) of its polarized interpretation. This allows the inheritance to the source systems of the decidability and other results previously obtained for LJP, thereby vastly generalizing the previous results of CoIPS, which were confined to LJT and implicational intuitionistic logic.
Stable Matching Games
Venue: arXiv cs.GT 2025
Year: 2025

Gale and Shapley introduced a matching problem between two sets of agents where each agent on one side has an exogenous preference ordering over the agents on the other side. They defined a matching as stable if no unmatched pair can both improve their utility by forming a new pair. They proved, algorithmically, the existence of a stable matching. Shapley and Shubik, Demange and Gale, and many others extended the model by allowing monetary transfers. We offer a further extension by assuming that matched couples obtain their payoff endogenously as the outcome of a strategic game they have to play in a usual non-cooperative sense (without commitment) or in a semi-cooperative way (with commitment, as the outcome of a bilateral binding contract in which each player is responsible for her part of the contract). Depending on whether the players can commit or not, we define in each case a solution concept that combines Gale-Shapley pairwise stability with a (generalized) Nash equilibrium stability. In each case we give necessary and sufficient conditions for the set of solutions to be non-empty and provide an algorithm to compute a solution.
Error Resilient Space Partitioning
Venue: arXiv cs.CG 2025
Year: 2025

A major research area in discrete geometry is to consider the best way to partition the $d$-dimensional Euclidean space $\mathbb{R}^d$ under various quality criteria. In this paper we introduce a new type of space partitioning that is motivated by the problem of rounding noisy measurements from the continuous space $\mathbb{R}^d$ to a discrete subset of representative values. Specifically, we study partitions of $\mathbb{R}^d$ into bounded-size tiles colored by one of $k$ colors, such that tiles of the same color have a distance of at least $t$ from each other. Such tilings allow for \emph{error-resilient} rounding, as two points of the same color and distance less than $t$ from each other are guaranteed to belong to the same tile, and thus, to be rounded to the same point. The main problem we study in this paper is characterizing the achievable tradeoffs between the number of colors $k$ and the distance $t$, for various dimensions $d$. On the qualitative side, we show that in $\mathbb{R}^d$, using $k=d+1$ colors is both sufficient and necessary to achieve $t>0$. On the quantitative side, we achieve numerous upper and lower bounds on $t$ as a function of $k$. In particular, for $d=3,4,8,24$, we obtain sharp asymptotic bounds on $t$, as $k \to \infty$. We obtain our results with a variety of techniques including isoperimetric inequalities, the Brunn-Minkowski theorem, sphere packing bounds, Bapat's connector-free lemma, and Čech cohomology.
How to organize an in-person, online or hybrid hackathon -- A revised planning kit
Venue: arXiv cs.CY 2025
Year: 2025

Hackathons and similar time-bounded events are a global phenomenon. Their proliferation in various domains and their usefulness for a variety of goals has led to the emergence of different formats. While there are a multitude of guidelines available on how to prepare and run a hackathon, most of them focus on a particular format that was created for a specific purpose within a domain for a certain type of participant. This makes it difficult, in particular, for novice organizers to decide how to run an event that fits their needs. To address this gap we developed the original version of this planning kit in 2020 which focused on in-person events that were the dominant form of hackathons then. That planning kit was organized around 12 key decisions that organizers need to take when preparing for, running, and following up on a hackathon. Fast forward to 2025, after going through a global pandemic that forced all events to move online, we now see different forms of events - in-person, online, and hybrid - taking place across the globe, and while they can be all valuable, they have different affordances and require different considerations when planning. To account for these differences, we decided to update the original planning kit by adding a section that discusses the affordances and requirements of in-person, online, and hybrid events to each of the 12 decisions. In addition, we modified the original example timelines to include different forms and types of events. We also updated the planning kit in general based on insights we gained through continuing to organize and study hackathons. The main planning kit is available online while this report is meant to be a downloadable and citable resource.
Formal Methods for An Iterated Volunteer's Dilemma
Venue: arXiv cs.MA 2025
Year: 2025

Game theory provides a framework for studying communication dynamics and emergent phenomena arising from rational agent interactions. We present a model framework for the Volunteer's Dilemma with four key contributions: (1) formulating it as a stochastic concurrent nn n-player game, (2) developing properties to verify model correctness and reachability, (3) constructing strategy synthesis graphs to identify optimal game trajectories, and (4) analyzing parameter correlations with expected local and global rewards over finite time horizons.
On SkipGram Word Embedding Models with Negative Sampling: Unified Framework and Impact of Noise Distributions
Venue: arXiv cs.CL 2025
Year: 2025

SkipGram word embedding models with negative sampling, or SGN in short, is an elegant family of word embedding models. In this paper, we formulate a framework for word embedding, referred to as Word-Context Classification (WCC), that generalizes SGN to a wide family of models. The framework, which uses some ``noise examples'', is justified through theoretical analysis. The impact of noise distribution on the learning of the WCC embedding models is studied experimentally, suggesting that the best noise distribution is, in fact, the data distribution, in terms of both the embedding performance and the speed of convergence during training. Along our way, we discover several novel embedding models that outperform existing WCC models.
AMReX: Block-Structured Adaptive Mesh Refinement for Multiphysics Applications
Venue: arXiv cs.MS 2025
Year: 2025

Block-structured adaptive mesh refinement (AMR) provides the basis for the temporal and spatial discretization strategy for a number of ECP applications in the areas of accelerator design, additive manufacturing, astrophysics, combustion, cosmology, multiphase flow, and wind plant modelling. AMReX is a software framework that provides a unified infrastructure with the functionality needed for these and other AMR applications to be able to effectively and efficiently utilize machines from laptops to exascale architectures. AMR reduces the computational cost and memory footprint compared to a uniform mesh while preserving accurate descriptions of different physical processes in complex multi-physics algorithms. AMReX supports algorithms that solve systems of partial differential equations (PDEs) in simple or complex geometries, and those that use particles and/or particle-mesh operations to represent component physical processes. In this paper, we will discuss the core elements of the AMReX framework such as data containers and iterators as well as several specialized operations to meet the needs of the application projects. In addition we will highlight the strategy that the AMReX team is pursuing to achieve highly performant code across a range of accelerator-based architectures for a variety of different applications.
On The Convergence of Euler Discretization of Finite-Time Convergent Gradient Flows
Venue: arXiv cs.LG 2025
Year: 2025

In this study, we investigate the performance of two novel first-order optimization algorithms, namely the rescaled-gradient flow (RGF) and the signed-gradient flow (SGF). These algorithms are derived from the forward Euler discretization of finite-time convergent flows, comprised of non-Lipschitz dynamical systems, which locally converge to the minima of gradient-dominated functions. We first characterize the closeness between the continuous flows and the discretizations, then we proceed to present (linear) convergence guarantees of the discrete algorithms (in the general and the stochastic case). Furthermore, in cases where problem parameters remain unknown or exhibit non-uniformity, we further integrate the line-search strategy with RGF/SGF and provide convergence analysis in this setting. We then apply the proposed algorithms to academic examples and deep neural network training, our results show that our schemes demonstrate faster convergences against standard optimization alternatives.
Online and Customizable Fairness-aware Learning
Venue: arXiv cs.LG 2025
Year: 2025

While artificial intelligence (AI)-based decision-making systems are increasingly popular, significant concerns on the potential discrimination during the AI decision-making process have been observed. For example, the distribution of predictions is usually biased and dependents on the sensitive attributes (e.g., gender and ethnicity). Numerous approaches have therefore been proposed to develop decision-making systems that are discrimination-conscious by-design, which are typically batch-based and require the simultaneous availability of all the training data for model learning. However, in the real-world, the data streams usually come on the fly which requires the model to process each input data once ``on arrival'' and without the need for storage and reprocessing. In addition, the data streams might also evolve over time, which further requires the model to be able to simultaneously adapt to non-stationary data distributions and time-evolving bias patterns, with an effective and robust trade-off between accuracy and fairness. In this paper, we propose a novel framework of online decision tree with fairness in the data stream with possible distribution drifting. Specifically, first, we propose two novel fairness splitting criteria that encode the data as well as possible, while simultaneously removing dependence on the sensitive attributes, and further adapts to non-stationary distribution with fine-grained control when needed. Second, we propose two fairness decision tree online growth algorithms that fulfills different online fair decision-making requirements. Our experiments show that our algorithms are able to deal with discrimination in massive and non-stationary streaming environments, with a better trade-off between fairness and predictive performance.
Learning to Actively Learn: A Robust Approach
Venue: arXiv cs.LG 2025
Year: 2025

This work proposes a procedure for designing algorithms for specific adaptive data collection tasks like active learning and pure-exploration multi-armed bandits. Unlike the design of traditional adaptive algorithms that rely on concentration of measure and careful analysis to justify the correctness and sample complexity of the procedure, our adaptive algorithm is learned via adversarial training over equivalence classes of problems derived from information theoretic lower bounds. In particular, a single adaptive learning algorithm is learned that competes with the best adaptive algorithm learned for each equivalence class. Our procedure takes as input just the available queries, set of hypotheses, loss function, and total query budget. This is in contrast to existing meta-learning work that learns an adaptive algorithm relative to an explicit, user-defined subset or prior distribution over problems which can be challenging to define and be mismatched to the instance encountered at test time. This work is particularly focused on the regime when the total query budget is very small, such as a few dozen, which is much smaller than those budgets typically considered by theoretically derived algorithms. We perform synthetic experiments to justify the stability and effectiveness of the training procedure, and then evaluate the method on tasks derived from real data including a noisy 20 Questions game and a joke recommendation task.
AI Discovering a Coordinate System of Chemical Elements: Dual Representation by Variational Autoencoders
Venue: arXiv cs.LG 2025
Year: 2025

The periodic table is a fundamental representation of chemical elements that plays essential theoretical and practical roles. The research article discusses the experiences of unsupervised training of neural networks to represent elements on the 2D latent space based on their electron configurations. To emphasize chemical properties of the elements, the original data of electron configurations has been realigned towards valence orbitals. Recognizing seven shells and four subshells, the input data has been arranged as 7x4 images. Latent space representation has been performed using a convolutional beta variational autoencoder (beta-VAE). Despite discrete and sparse input data, the beta-VAE disentangles elements of different periods, blocks, groups, and types. The unsupervised representation of elements on the latent space reveals pairwise symmetries of periods and elements related to the invariance of quantum numbers of corresponding elements. In addition, it isolates outliers that turned out to be known cases of Madelung's rule violations for lanthanide and actinide elements. Considering the generative capabilities of beta-VAE, the supervised machine learning has been set to find out if there are insightful patterns distinguishing electron configurations between real elements and decoded artificial ones. Also, the article addresses the capability of dual representation by autoencoders. Conventionally, autoencoders represent observations of input data on the latent space. By transposing and duplicating original input data, it is possible to represent variables on the latent space which can lead to the discovery of meaningful patterns among input variables. Applying that unsupervised learning for transposed data of electron configurations, the order of input variables that has been arranged by the encoder on the latent space has turned out to exactly match the sequence of Madelung's rule.