Information Theory
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Monday 11 May
Folded Reed-Solomon codes, introduced by Guruswami and Rudra in 2007, have been shown to achieve the information-theoretically best possible trade-off between the rate of a code and the error-correction radius. In 2024, Bergamaschi, Golowich and Gunn extended this framework by constructing folded quantum Reed-Solomon codes (CSS codes obtained by folding) demonstrating that these codes tolerate errors up to the quantum Singleton bound. In this paper, we construct folded quantum Hermitian codes using the CSS framework and show that these codes are also list-decodable, tolerating errors up to the quantum Singleton bound. Compared to Reed-Solomon codes, Hermitian codes admit comparable lengths over smaller alphabets, enabling more efficient implementations.
Optimization and Control
Randomized Max-Vertex-Coverage Interdiction under Matroid Constraints
We study a class of bilevel interdiction problems in which the follower's optimization problem is computationally intractable. Motivated by network defense applications, we introduce the Randomized Max-Vertex-Coverage Interdiction (RMVCI) problem under matroid constraints. In this zero-sum Stackelberg game, the leader commits to a randomized interdiction strategy over feasible vertex subsets, while the follower, after observing the induced protection probabilities, chooses a matroid-constrained attack to maximize the expected coverage of network edges. The main challenge stems from the fact that the follower's problem is a matroid-constrained maximum vertex coverage problem and is therefore NP-hard. To address this difficulty, we first develop a general approximation framework for bilevel optimization problems with hard follower responses. The framework is based on replacing the follower's value function by a surrogate objective that approximates the follower's optimal payoff while preserving tractability of the leader's optimization problem. For the RMVCI problem, we formulate the follower's problem as an integer linear program, establish a tight integrality gap of $4/3$ for its linear relaxation, and derive a polynomial-time $4/3$-approximation algorithm via pipage rounding. We then show that a carefully designed surrogate objective admits a marginal-probability reformulation that transforms the randomized interdiction problem into a tractable optimization problem over the leader's matroid polytope. This yields a polynomial-time $2$-approximation algorithm for RMVCI under general matroid constraints. Beyond the specific application studied here, our results provide a new perspective on approximation methods for {general} bilevel optimization problems.
Read the full abstract
Optimization and Control
Observer Design for a Class of ODE – Continuum-PDE Cascade Systems Inspired by a Control-Theoretic Model of Large-Scale Arterial Networks of Blood Flow
We develop a backstepping-based observer design for a class of ODE - continuum-PDE cascade systems, which can be viewed as the limit, of a finite collection of ODE - $2 \times 2$ hyperbolic systems, as the number of individual PDE system components tends to infinity. The large-scale collection of ODE - $2 \times 2$ hyperbolic systems is motivated by a dynamic model that we present, of a network of peripheral arteries, to which central (aortic) blood flow/pressure enters. We address a case in which average (boundary) measurements, over the ensemble dimension, are available, which is motivated by the availability of non-invasive, peripheral flow/pressure measurements. Exponential stability of the estimation error system is shown by proving well-posedness of the kernel equations and constructing a Lyapunov functional. We also establish that part of the backstepping kernels derived coincide with the solution of a Sylvester equation. We then apply the continuum-based observer for state estimation of the large-scale counterpart and, in particular, of the blood flow system, introducing an approach for optimal construction of continuum approximations. We also introduce an implementation method, adopting a spectral-based approach for computing the observer dynamics, which we illustrate in an academic, numerical simulation example. Furthermore, we illustrate the design in the problem of central flow/pressure estimation using realistic parameters and flow/pressure waveforms.
Read the full abstract
Combinatorics
Ehrhart quasi-polynomials of rational polytopes by real dilations
This paper is to study the Ehrhart function $L(P,t)$ of a rational $n$-polytope $P$, defined as the number of lattice points of dilated polytopes $tP$ with real numbers $t\geq 0$. It turns out that $L(P,t)$ is a quasi-polynomial of real variable $t$ in the sense that \[ L(P,t)=\sum_{k=0}^{n} c_k(P,t)t^k, \quad t\geq 0, \] where $c_k(P,t)$ are periodic piecewise polynomials of degree $n-k$ if ${\rm aff}\,P$ contains the origin, and are periodic functions vanishing almost everywhere otherwise. When $P$ is a rational simplex $\sigma$, the coefficient functions $c_k(\sigma,t)$ are given explicitly in terms of vertex information of the simplex $\sigma$. Moreover, the reciprocity law still holds.
Read the full abstract
Geometric Topology
Combinatorial extension of a simple construction of Lefschetz fibrations
In a previous work, we introduced a simple and systematic method for constructing a positive allowable Lefschetz fibration (PALF) from a 2-handlebody decomposition of a given Stein surface. In this paper, we present a combinatorial extension of this construction, focusing on the flexibility of the regular fiber. By introducing variations in the isotopy of the 0-handle during the construction process, we obtain PALFs whose total spaces are diffeomorphic to the original Stein surface but which possess different regular fibers. As a primary application, we prove the existence of PALFs with genus $1$ regular fibers whose total spaces are diffeomorphic to the knot traces of Legendrian positive twist knots and positive torus knots $T_{2, 2n+1}$. Furthermore, we explicitly compare our PALF associated with the positive torus knot $T_{2, 2n+1}$ to the specific open book decomposition generated by Avdek's Algorithm 2, demonstrating that the regular fiber and monodromy of our construction coincide with the page and monodromy of the corresponding open book.
Read the full abstract
Number Theory
Reciprocals of Subsum Polynomials
We introduce the subsum polynomial of a partition $\lambda=(\lambda_1, \lambda_2, \ldots, \lambda_k)$ defined by $\mathrm{sp}(\lambda, x)=\prod_{i=1}^k(1+x^{\lambda_i})$. We study the sum of reciprocals of $\mathrm{sp}(\lambda, x)$ over all partitions of $n$. We prove arithmetic properties of related polynomials and offer connections to other combinatorial objects.
Read the full abstract
Information Theory
Optimal Repair Bandwidth and Repair I/O of $(n,n-2,2)$ MDS Array Codes
We give a complete determination of the exact optimal worst-case repair bandwidth and repair I/O for linear exact repair of $(n,n-2,2)$ MDS array codes over every finite field $\mathbb{F}_q$ and for every admissible code length $3\le n\le q^2+1$. For repair bandwidth, we prove that the optimum is governed, up to a short explicit list of small exceptional cases, by the maximum of the sharpened $n$-only lower bound $\lceil(5n-8)/4\rceil$ and the projective counting, equivalently incidence-multiplicity, bound $2n-q-3$. For repair I/O, we obtain the analogous exact formula with $\lceil(4n-6)/3\rceil$ in place of $\lceil(5n-8)/4\rceil$, with the single special value at $n=4$. Thus, we completely resolve the first non-trivial redundancy and sub-packetization regime $(r,\ell)=(2,2)$ for both repair bandwidth and repair I/O.
Read the full abstract
Numerical Analysis
Mathematical analysis and numerical methods for the computation of transport coefficients in molecular dynamics
We review various numerical approaches to compute transport coefficients in molecular dynamics. These approaches can be broadly classified into three groups: (i) nonequilibrium methods based on applying an external driving field to the system, measuring the average response in the system, and evaluating the related linear response coefficient; (ii) approaches reformulating the transport coefficient of interest through a time correlation function for the equilibrium dynamics (the most popular instances being Green–Kubo and Einstein formulas); (iii) transient techniques, where the transport coefficient can be computed by monitoring the return to the steady state of a dynamics perturbed off its stationary distribution. For all three classes of methods, we provide elements of numerical analysis, allowing to estimate or at least quantify the level of numerical errors in the estimator of the transport coefficient; and also briefly present recent attempts to more efficiently compute transport coefficients with variance reduction approaches such as control variates, importance sampling and coupling methods. The computation of transport coefficients remains nonetheless challenging and will continue requiring research efforts in the foreseeable future.
Read the full abstract
Analysis of PDEs
Global uniform regularity for the 3D compressible MHD equations near a background magnetic field
This paper resolves the global regularity problem for the three-dimensional compressible magnetohydrodynamics (MHD) equations in the three-dimensional whole space, in the presence of a background magnetic field. Motivated by geophysical applications, we consider an anisotropic compressible MHD system with weak dissipation in the $x_2$ and $x_3$ directions and small vertical magnetic diffusion. By exploiting the stabilizing effect induced by the background magnetic field and constructing a hierarchy of four energy functionals, we establish global-in-time uniform bounds that are independent of the viscosity in the $x_2$ and $x_3$ directions and the vertical resistivity. A key innovation in our analysis is the development of a two-tier energy method, which couples the boundedness of vertical derivatives with the decay of horizontal derivatives. The analysis of time scale, together with global regularity estimates and sharp decay rates, enable us to rigorously justify the vanishing dissipation limit and derive explicit long-time convergence rates to the compressible MHD system with vanishing dissipation in the $x_2$ and $x_3$ directions and no vertical magnetic diffusion. In the absence of magnetic field and background magnetic field, the global-in-time well-posedness and vanishing viscosity limit for the 3D compressible Navier-Stokes equations with only one direction dissipation remains a challenging open problem. This work reveals the mechanism by which the magnetic field enhances dissipation and stabilizes the fluid dynamics in the global well-posedness and vanishing viscosity limit.
Read the full abstract
Geometric Topology
On T-positive links
T-positive links form a subset of strongly quasipositive links that strictly contains the set of all non-split braid positive links. Analogous to Baader's characterisation of positive links as precisely the strongly quasipositive and homogeneous links, we show that T-positive links are precisely the strongly quasipositive links that are the closures of T-homogeneous braids. This complements previous characterizations of T-positive links by Rudolph and Banfield as links arising as boundaries of positive Hopf-plumbed baskets, or closures of staircase braids. We examine the behavior of T-positive links under cabling operations and connected sums, and demonstrate that all strongly quasipositive, fibered knots with at most 12 crossings are T-positive. Additionally, we compare T-positivity with other positivity notions for links and compile open questions.
Read the full abstract
Optimization and Control
A PAC-Bayes Approach for Controlling Unknown Linear Discrete-time Systems
This paper presents a PAC-Bayes framework for learning controllers for unknown stochastic linear discrete-time systems, where the system parameters are drawn from a fixed but unknown distribution. We derive a data-dependent high probability bound on the performance of any learned (stochastic) controller, and propose novel efficient learning algorithms with theoretical guarantees, which can be implemented for both finite and infinite controller spaces. Compared to prior work, our bound holds for unbounded quadratic cost. In the special case where LQG is optimal, our numerical results suggest that the learned controllers achieve comparable performance to LQG.
Read the full abstract
Probability
Zero-couplings of infinite measures with cyclically monotone support and multivariate regular variation
We study cyclically monotone transport plans between measures in $\mathrm{M}_0(\mathbb{R}^d)$, the class of Borel measures on $\mathbb{R}^d \setminus \{0\}$ that are finite on sets bounded away from the origin but may have infinite total mass. We avoid moment assumptions and allow the transport cost to be infinite. This framework naturally arises for exponent measures in multivariate regular variation and includes other examples such as Lévy measures. We introduce the notion of a zero-coupling and establish existence of cyclically monotone zero-couplings for arbitrary pairs of measures in $\mathrm{M}_0(\mathbb{R}^d)$. Under a Hausdorff-dimension condition on the first measure and when at least one of the two measures has infinite mass, we prove uniqueness of the cyclically monotone zero-coupling, yielding an analogue of the Brenier–McCann theorem in this infinite-measure setting. We further derive a representation of such couplings through gradients of closed convex functions and identify conditions under which the zero-coupling is proper in the sense that the second measure is equal to the restriction to the punctured space of the push-forward of the first measure by a cyclically monotone transport map. Finally, we apply these results to regularly varying probability measures. We show that a cyclically monotone coupling between two such distributions admits a tail limit that coincides with the unique proper cyclically monotone zero-coupling between the corresponding exponent measures.
Read the full abstract
Combinatorics
Algorithm for finding vertex-edge domination number on graphs with bounded treewidth and related problems on planar graphs
Given a graph $G=(V,E)$, a vertex $u \in V$ ve-dominates all edges incident to any vertex of $N_G[u]$. A set $S \subseteq V$ is a ve-dominating set if for all edges $e\in E$, there exists a vertex $u\in S$ such that $u$ ve-dominates $e$. The minimum cardinality among all ve-dominating sets is known as the vertex-edge domination number (or simply ve-domination number) and denoted by $\gamma_{ve}(G)$. Finding a minimum ve-dominating set was proved to be NP-complete. Restricted to trees, the problem admits a linear-time algorithm. Treewidth is a commonly used parameter for solving NP-hard problems. In this paper, we present a polynomial-time algorithm for finding a minimum ve-dominating set on graphs with bounded treewidth. Moreover, we show that the treewidth of a planar graph $G$ with ve-domination number $\gamma_{ve}(G)$ is $O(\sqrt{\gamma_{ve}(G)})$ and present an $O(c^{\sqrt{k}}|V(G)|)$-time algorithm for the $k$-ve-domination problem on planar graphs.
Read the full abstract
Probability
Poisson approximation of random lattices
Fix a subset $S \subset \mathbb{R}^n$ of volume at most $c n$ that satisfies $S \cap (-S) = \emptyset$. We consider two point processes in $S$: the first is the Poisson point process of intensity one, and the second is the restriction of a random lattice to $S$, where the random lattice is distributed uniformly in the space of covolume-one lattices. We show that the total variation distance between these two point processes is at most $C e^{-c' n}$, where $c, C, c' > 0$ are universal constants.
Read the full abstract
Analysis of PDEs
Nonexistence of vanishing-viscosity limits for mechanical Hamiltonian ergodic problems
For $\varepsilon>0$, let $\phi^\varepsilon$ be the solution of the ergodic problem \[ \frac12 |D\phi^\varepsilon|^2+F(x)-\varepsilon\Delta\phi^\varepsilon=c(\varepsilon) \qquad \text{on } \mathbb{T}^n, \] normalized by $\phi^\varepsilon(0)=0$. We construct a one-dimensional example with $F\in C^3$ for which the vanishing-viscosity limit $\lim_{\varepsilon\to0}\phi^\varepsilon$ does not exist. This gives a negative answer to a problem proposed by Jauslin, Kreiss, and Moser [10].
Read the full abstract
Complex Variables
The norm of the backward shift on $H^4$ is $\sqrt[4]{\varphi}$
We prove that the backward shift operator on $H^4$ has norm equal to $\sqrt[4]{\varphi}$, with $\varphi = \frac{1 + \sqrt{5}}{2}$. Furthermore, we characterize all extremal functions; they are precisely the functions of the form \[ f(z) = \mu \left( I(z) - \sqrt{\frac{1}{2\varphi}}\right), \] where $\mu \in \mathbb{C}$ and $I$ is an inner function with $I(0) = \sqrt{\frac{\varphi}{2}}$.
Read the full abstract
Analysis of PDEs
Gradient-flow characterizations of one-dimensional quasistatic viscoelasticity with Bhattacharya-like viscosity
We study the equation of one-dimensional quasistatic nonlinear viscoelasticity with Dirichlet boundary conditions, in the particular case that the underlying dissipation geometry (provided by the viscosity) is comparable to the Bhattacharya metric on probability densities. We establish a global existence result for weak solutions, with an approach based on a spatial discretization allowing us to work directly with the Riemannian metric associated to the viscosity. Strong convergence of spatially discrete solutions is shown directly - this is possible thanks to Lipschitz estimates achieved locally on energy sublevels enabled by an explicit derivation of the stretching of tangent vectors under the flow in the discrete setting and the relationship to the Bhattacharya metric. We furthermore prove gradient-flow representations for the solutions: they are curves of maximal slope and, under a global convexity hypothesis on the energy sublevels, we prove they satisfy a metric evolutionary variational inequality.
Read the full abstract
Probability · Cross-listed from cs.CR
A Note on Banaszczyk's Inequality
Banaszczyk's inequality establishes a tail estimate for the discrete Gaussian measure on a lattice in $\mathbb{R}^n$. This classic result has been influential and plays an important role in lattice-based cryptography. An improvement of the inequality with a transparent proof was given by Tian, Liu and Xu. In this note, we further improve this inequality by imposing an appropriate condition, obtaining a significantly better bound. This refined inequality can be used to investigate dual attacks against the Learning With Errors (LWE) problem.
Read the full abstract
Probability
A secretary for Messrs. Luce and Mallows
We analyze the secretary problem in the case that the $n$ ranked items arrive not in uniformly random order but rather according to a certain type of Luce distribution or according to a Mallows distribution on the set $S_n$ of permutations of $[n]$. The secretary problem for the Mallows distributions with parameter $q\in(0,1)$ was analyzed in a previous paper; in this paper the case $q>1$ is also analyzed. The Luce distribution with the class $\{q_j\}_{j=1}^\infty$ of weights is related in a certain sense to the Mallows distribution with parameter $q$, but is more difficult to analyze. It turns out that for every $n$ and every strategy, the probabilities for the secretary problem when the smallest number is considered of highest rank for the Luce distribution with this class of weights coincides with those for the corresponding Mallows distribution. We analyze the asymptotic optimal strategy and corresponding limiting probability for the above cases, as well as for the Luce distributions with other classes of weights, such as the Sukhatme weights.
Read the full abstract
Numerical Analysis · Cross-listed from cs.LG
Don't Fix the Basis – Learn It: Spectral Representation with Adaptive Basis Learning for PDEs
Spectral neural operators achieve strong performance for PDE learning, but rely on fixed global bases that limit their ability to represent spatially heterogeneous and multiscale dynamics. We propose Adaptive Basis Learning (ABLE), a framework that learns data-dependent spectral representations instead of relying on predefined bases. ABLE constructs a spatially adaptive Parseval frame via a learned ancillary density, enabling the operator to act in a lifted spectral space while preserving invertibility and maintaining $O(N\log N)$ complexity through FFT-based implementation. This shifts the source of expressivity from spectral coefficients to the representation itself, allowing the model to capture localized structures and non-translation-invariant interactions more efficiently. ABLE integrates seamlessly into existing neural operator architectures as a drop-in replacement for spectral layers. Across a range of benchmarks ABLE improves accuracy over strong baselines, with the largest gains in regimes characterized by sharp gradients and multiscale behavior. Moreover, augmenting existing models (e.g., U-FNO, HPM) with ABLE further enhances their performance, demonstrating its role as a general and complementary spectral refinement. Our results highlight that the data-driven choice of representation, rather than operator complexity alone, is a key bottleneck in neural operator design. By learning the basis itself, ABLE provides a principled and efficient framework for improving spectral methods in PDE learning.
Read the full abstract
Analysis of PDEs
A Volume-Growth Criterion for the p-Laplace Inequality on Weighted Graphs
We prove a nonexistence result for nonnegative solutions of the quasi-linear elliptic inequality \[ -\Delta_p u\ge \sigma(x)u^q \] on infinite locally finite connected weighted graphs, where $1<p<\infty$ and $q>p-1$, $\sigma$ is a nonnegative Radon measure. Under the non-$p$-parabolic setting, we show that every nonnegative solution is identically zero, provided the volume of intrinsic balls satisfy \[ \int_1^\infty \frac{r^{\frac{pq}{p-1}-1}} {\nu(B_\rho(o,r))^{\frac{q-p+1}{p-1}}} \dd r =\infty, \] This criterion recovers the known sharp pointwise critical volume-growth threshold and is strictly more flexible, since it allows irregular growth and does not require uniform upper bounds at every large radius. The proof adapts the finite-network current method to the $p$-Laplace setting, combining a path decomposition with one-dimensional Hardy estimates, $p$-parallel-sum bounds across metric cuts, and the global $p$-Green function furnished by non-$p$-parabolicity.
Read the full abstract
Information Theory
Syndrome Adaptive Gain Control for Min-Sum Decoding of Quantum LDPC Codes
Min-Sum (MS) decoding is a popular low-complexity alternative to belief propagation (BP), retaining only the minimum incoming message magnitude during check-node (CN) processing, at the cost of systematic message magnitude overestimation. The scaled MS (SMS) decoder compensates for this effect using a fixed scaling factor. We propose the syndrome adaptive gain Min-Sum (SAGMS) decoder for quantum low-density parity-check (QLDPC) codes, which adapts the message gain online based on the fraction of unsatisfied stabilizers, requiring no per-code or per-noise level optimization. We show that the scaling factor required for SMS to match belief propagation decreases with the CN degree, so any fixed scaling optimized for one degree incurs into a growing penalty as the CN degree varies. SAGMS avoids this limitation by adapting the gain during decoding. Simulations on generalized bicycle QLDPC codes demonstrate that SAGMS matches or outperforms the frame error rate (FER) of an offline optimized SMS decoder. Moreover, SAGMS approaches BP performance and, under certain conditions outperforms it while retaining MS-level complexity.
Read the full abstract
Optimization and Control · Cross-listed from eess.SY
Hierarchical 2-degree-of-freedom control combining Youla-Kucera parameterization and model predictive control
A hierarchical 2DOF (2-degree-of-freedom) structure combining Youla-Kucera (YK) parameterization and model predictive control (MPC) is presented in this paper. The YK parameterization employs the coprime factorization of the nominal system and controller, thereby introducing an auxiliary feedforward channel dedicated to system optimization and a controller parameterization channel. The feedforward channel is utilized to implement cascaded MPC for system optimization. The controller parameterization channel is utilized to achieve offset-free MPC by designing an appropriate YK parameter through the H2 optimal controller design.
Read the full abstract
Analysis of PDEs
The Three-Dimensional Divergence-Curl Problem with Homogeneous Boundary Conditions and Pseudo-Harmonic Fields
This article addresses the solvability of the three-dimensional divergence-curl problem with a no-slip boundary condition. A solvability criterion is derived as an orthogonality condition of the vorticity function to pseudo-harmonic fields. A countable family of such fields, sufficient for the solvability of the three-dimensional problem in the exterior of a sphere, is also presented.
Read the full abstract
Dynamical Systems
Long-time dynamics for time-nonlocal generalized Rayleigh-Stokes equations
In this paper, we consider an autonomous semi-dynamical system driven by semilinear time-nonlocal evolution equations, these type equations are used to describe the Rayleigh-Stokes problem for a non-Newtonain fluid to a generalized second grade fluid. We first investigate the global well-posedness of solutions consisting of global Lipschitz condition by a weighted space $\mathcal C$. Utilizing the topology convergence on compact subsets of $\mathcal C$, we construct a semi-dynamical system that satisfies the semi-group structure. It also is shown that this semi-dynamical system has an attracting set when the vector field function satisfies a dissipativity condition and a local Lipschitz condition. With the asymptotic compactness, we also establish the existence of generalized attractors in $\mathcal C_\alpha$ of subspace of $\mathcal C$ the weighted norm.
Read the full abstract
Numerical Analysis
PCELM: Perturbation-Correction Extreme Learning Machine for the Stefan problem
For Stefan problems, characterized by moving boundaries and discontinuous coefficients due to phase changes, the inherent nonconvexity of the objective functional frequently causes optimization difficulty in randomized neural network approximations; to address this, we propose a Perturbation-Correction Extreme Learning Machine (PCELM) framework, built upon the extreme learning machine framework. This method first establishes a basic approximation during an initialization step by minimizing the original nonconvex residual, typically achieving only moderate accuracy, and then, in a subsequent correction step, determines a correction term by solving a subproblem based on a perturbation expansion around this basic approximation, thereby transforming it into a convex optimization problem for the output coefficients that ensures rapid convergence. We further provide a rigorous a convexity analysis, demonstrating that PCELM method solves a convex sub-problem. Numerical experiments on various Stefan problems, including multi-phase and multi-dimensional Stefan problems, confirm that the proposed PCELM method successfully overcomes optimization plateaus, with the correction step consistently delivering a significant improvement of 2-6 orders of magnitude in the relative L2 accuracy.
Read the full abstract
Group Theory
Every finite group admits a just finite presentation
A finite presentation < X | R > of a finite group is called `just finite' if removing any relation from R results in a presentation for an infinite group. It has been an open question (Kourovka Notebook, Problem 21.10) whether every finite group admits such a presentation. We resolve this conjecture in the affirmative.
Read the full abstract
Optimization and Control · Cross-listed from cs.AI
LLM4Branch: Large Language Model for Discovering Efficient Branching Policies of Integer Programs
Efficient branching policies are essential for accelerating Mixed Integer Linear Programming (MILP) solvers. Their design has long relied on hand-crafted heuristics, and now machine learning has emerged as a promising paradigm to automate this process. However, existing learning-based methods are often hindered by their dependence on expensive expert demonstrations and the gap between training objectives and the solver's end-to-end performance. In this work, we propose LLM4Branch, a novel framework that leverages Large Language Models (LLMs) to automate the discovery of efficient branching policies. Specifically, the discovered policy is an executable program with a program skeleton generated by the LLM and a parameter vector, which is optimized via a zeroth-order method over a few instances with their end-to-end performance feedback. Extensive experiments on standard MILP benchmarks demonstrate that LLM4Branch establishes a new state-of-the-art among CPU-based methods and achieves performance competitive with advanced GPU-based models. Codes are available at https://github.com/hzn18/LLM4Branch.
Read the full abstract
Information Theory · Cross-listed from stat.ML
Sharp feature-learning transitions and Bayes-optimal neural scaling laws in extensive-width networks
We study the information-theoretic limits of learning a one-hidden-layer teacher network with hierarchical features from noisy queries, in the context of knowledge transfer to a smaller student model. We work in the high-dimensional regime where the teacher width $k$ scales linearly with the input dimension $d$ – a setting that captures large-but-finite-width networks and has only recently become analytically tractable. Using a heuristic leave-one-out decoupling argument, validated numerically throughout, we derive asymptotically sharp characterizations of the Bayes-optimal generalization error and individual feature overlaps via a system of closed fixed-point equations. These equations reveal that feature learnability is governed by a sequence of sharp phase transitions: as data grows, teacher features become recoverable sequentially, each through a discontinuous jump in overlap. This sequential acquisition underlies a precise notion of effective width $k_c$ – the number of learnable features at a given data budget $n$ – which unifies two distinct scaling regimes: a feature-learning regime in which the Bayes-optimal generalization error $\varepsilon^{\rm BO}$ scales as $ n^{1/(2\beta)-1}$, and a refinement regime in which it scales as $n^{-1}$, where $\beta>1/2$ is the exponent of the power-law feature hierarchy. Both laws collapse to the single relation $\varepsilon^{\rm BO}=\Theta(k_c d/n)$. We further show empirically that a student trained with Adam near the effective width $k_c$ achieves these optimal scaling laws (up to a small algorithmic gap), and provide an information-theoretic account of the associated scaling in model size.
Read the full abstract
Numerical Analysis
hp-Finite Elements for Elastoplasticity
This article considers a model problem of elastoplasticity with linearly kinematic hardening and presents hp-finite element discretizations of two equivalent weak formulations each having their respective advantages. A mixed variational formulation is introduced to resolve the non-differentiablility of the so-called plasticity functional appearing in the weak formulation of the model problem as a variational inequality of the second kind. The discretization of the mixed formulation is then represented as a system of decoupled nonlinear equations which allows the application of an efficient semismooth Newton solver. Finally, an a priori and a posteriori error analysis is given.