Papers

We study second-order convex optimization under generalized Hessian smoothness, where the local Hessian Lipschitz constant may grow linearly with the gradient norm. For inexact Hessians, we develop adaptive algorithms, including an accelerated Monteiro-Svaiter-type method whose complexity matches the lower bound for second-order methods with $\delta$-inexact Hessians in the classical Lipschitz-Hessian setting. Our methods are parameter-free in the sense that they require no problem-specific parameters as input, including the Hessian inexactness level $\delta$ and smoothness constants. Instead, their backtracking adapts a single regularization parameter that jointly captures Hessian inexactness and local Hessian smoothness. The resulting rates split into two regimes. Far from the solution, the gradient-dependent smoothness term yields geometric convergence. Near the solution, the rate is governed by the ordinary Hessian smoothness and the inexactness level $\delta$, recovering the classical Lipschitz-Hessian guarantees.

We study probability measures minimizing the energy with kernel $|x\cdot y|^p$ on the real unit sphere. For every positive rational $p=a/b$, each minimizer admits a finitely supported minimizing replacement. If $a/b$ is reduced and $b\ge d$, every minimizer on $\mathbb S^{d-1}$ is finitely supported. The latter assertion follows from a finite-rank algebraic lift, Nash curve selection, and a Wronskian multiplicity bound. For irrational exponents, we prove that a positive semidefinite restriction of finite rank cannot have infinite compact support. We also establish local stability and a quantitative support bound under positive-definite Hessians at every contact of every limiting minimizer. This hypothesis is stronger than finite support and does not prove unconditional openness of the discreteness regime. Finally, subtracting a single suitably scaled high even power produces a uniformly nearby kernel whose every minimizer has finite support. We identify the atomic-purity selection of these approximants and prove a target-centered recovery theorem, separating finite approximation from discreteness of the limiting problem.

Minimax optimization is a fundamental framework in machine learning, robust optimization, and game theory, yet finding first-order stationary points of general nonconvex-nonconcave minimax problems remains challenging without additional structural assumptions. Existing guarantees often rely on global PL- or KL-type conditions that connect max-player stationarity to global inner optimality, or on Minty-type conditions that impose a global relation on the game gradient field relative to a reference solution; local KL variants relax the former requirement but typically require initialization and tracking within a near-optimal region. Such conditions may be difficult to satisfy in many applications. In contrast, we develop a first-order method that finds an $\epsilon$-stationary point within $\widetilde{O}(\epsilon^{-2})$ first-order iterations under a local inverse-Lipschitz regularity condition around approximate max-player stationary points, together with a compactness condition on a penalty sublevel set. Our condition places no optimality requirement on stationary points of the inner maximization problem: they need not be globally, or even locally, maximizing. We further provide sufficient conditions for the required regularity. In the unconstrained setting, it follows from uniform nonsingularity of the maximization-variable Hessian near stationary points; for constrained upper Moreau envelopes, it follows from standard KKT regularity conditions. These results establish first-order complexity guarantees for classes of nonconvex-nonconcave minimax problems not covered by the above PL-, KL-, or Minty-type frameworks.

Given a finite transitive group $G\leq \operatorname{Sym}(\Omega)$, the derangement graph $\Gamma_G$ is the graph whose vertex set is $G$, and two vertices $g$ and $h$ are adjacent if the ratio $h^{-1}g$ is a fixed-point-free permutation. In this paper, we show that the automorphism group of the derangement graph of the transitive permutation group corresponding to the natural action of $\operatorname{PGL}_{2}(q)$ on the projective line $\operatorname{PG}_{1}(q)$ is \begin{align*} \operatorname{Aut}(\Gamma_{\operatorname{PGL}_{2}({q})}) = \left(L_{\operatorname{PGL}_2(q)}\times R_{\operatorname{PGL}_2(q)}\right) \rtimes \left(\langle \psi \rangle \times \gamma_{\operatorname{Aut}(\mathbb{F}_q)}\right), \end{align*} where $L_{\operatorname{PGL}_2(q)}$ is the left-regular representation of $\operatorname{PGL}_2(q)$, $R_{\operatorname{PGL}_2(q)}$ is the right-regular representation of $\operatorname{PGL}_2(q)$, $\gamma_{\operatorname{Aut}(\mathbb{F}_q)}$ is the group of conjugation by elements of $\operatorname{Aut}(\mathbb{F}_q)$, and $\psi: \operatorname{PGL}_2(q) \to \operatorname{PGL}_2(q)$ such that $\psi(x) = x^{-1}$.

This paper analyzes finite element approximations for Maxwell's equations with time-dependent coefficients and nonlinear E-H coupling in both the total current density and the Silver-Müller-type boundary condition. The nonlinear coupling and the time-varying material parameters prevent the use of standard analytical tools, including the discrete compactness property and the Minty-Browder argument, making the numerical analysis particularly challenging. As the main novelty, we establish two primary contributions: Uniform convergence on every finite time interval $[0,T]$ and exponential stability on the infinite time horizon $[0,\infty)$. The uniform convergence is established via a Cauchy-type argument within a time-dependent Hilbert space framework that entirely bypasses Minty's trick and the discrete compactness argument. Furthermore, under a positive homogeneity assumption on the nonlinearities, the exponential stability is analyzed by means of a nonlinear sup-max problem arising from ratios of consecutive discrete energies. With this strategy, we ultimately prove a fully discrete unconditional exponential decay result under a specific sufficient condition. In the absence of this condition, a concrete counterexample shows that the energy decay fails to hold. Numerical experiments are provided to validate the theoretical findings.

Gradient clipping is widely used to stabilize training, but it need not improve the statistical accuracy of averaged SGD, even under heavy-tailed noise. We derive a finite-sample comparison of clipped and unclipped Polyak-Ruppert averaged SGD under finite conditional $p$-th moments, $p\ge2$. Our main result gives explicit accuracy and confidence conditions under which, for $p>2$, the Gaussian term dominates the unclipped deviation bound, so clipping need not improve its leading order. By balancing clipping bias and concentration, we obtain a bound in which the heavy-tail correction depends logarithmically rather than polynomially on the inverse failure probability. At $p=2$, this improves the confidence dependence of the leading bound. We establish sharpness of the unclipped heavy-tail term through an exact one-dimensional quadratic recursion and extend the comparison to projected convex SGD. We also prove concrete costs of clipping: every fixed finite threshold increases asymptotic variance on a scalar Gaussian quadratic, while whole-gradient clipping can shift the limiting point under asymmetric noise.

Let $R_{n,p}$ be the determinantal hypersurface ring defined by the determinant of a generic $n \times n$ matrix in characteristic $p$ where $n \geq 2$. In this paper, we obtain explicit bounds for the $F$-signature of $R_{n,p}$. For the upper bound, we prove that this $F$-signature is decreasing in $n$, so the $F$-signature of $R_{2,p}$ serves as an upper bound, which is $2/3$. For the lower bound, we find a toric degeneration $B_n$ of $R_{n,p}$, so the $F$-signature of $B_n$ serves as a lower bound. This $F$-signature can be computed using either Gröbner basis or Han-Monsky machinery, and its value is $\frac{(n!)^2}{(2n-1)!}$.

For planar convex bodies $A_0,A_1,A_2$ satisfying $\frac12(A_0+A_2)\subseteq A_1$, we prove that the union of the three slices $\{i\}\times A_i\subseteq\mathbb{R}^3$, $i=0,1,2$, contains a point such that every closed halfspace containing it captures at least $2/9$ of their total area. This establishes the three-slice case of Oertel's mixed-integer centerpoint conjecture in $\mathbb{Z}\times\mathbb{R}^2$ with the best possible constant.

Santos asked when intersections of dilated Hadamard simplices with cubes are integral, smooth, or normal, in a prescribed affine lattice. We construct a nonintegral example in dimension eleven and prove that no smaller-dimensional example exists. We characterize smoothness completely and show that every smooth member of this family is normal. An explicit example in dimension fifteen shows that integrality alone does not imply normality. For Sylvester simplices of order at least sixteen, we establish a sharp uniform integrality bound and construct counterexamples immediately below it. We also obtain sufficient normality bounds for general Hadamard simplices and stronger bounds for the Sylvester family. The proofs use integer decomposition for boxes with separated corner cuts and rounding under three signed slab constraints. All numbered results have formal counterparts verified in Lean.

We calculate the exact values of the relative isoperimetric profile for a unit square with a central square removed. In other words, given a removed central square of a fixed size, we provide a function which produces the smallest relative perimeter which bounds any possible area within this shape.

We prove that there is an absolute positive constant $c$ such that every bipartite graph with $N$ vertices in each part and at least $N^2/2$ edges contains a complete bipartite graph $K_{t,t}$ whenever $N\ge c\, 2^{t}$. This improves the classical Kővári-Sós-Turán bound requiring $N$ of order $t\,2^t $. As a consequence, the diagonal bipartite Ramsey number has upper bound $b(t,t)=O(2^t)$, improving the previous best bound $b(t,t) = O(2^t\, \log t )$ due to Conlon. The proof was found by GPT-6 Astra, and the method will probably have further applications.

We give a strict generalization of the LLL algorithm over number fields, based on the reduction theory of $\GL(n)$ over the adele ring of a number field. Our algorithm is free of heuristics, with rigorous bounds on output quality and complexity. As a consequence, we obtain a hierarchy of reductions from module-(H)SVP to ideal-HSVP, an example of which has runtime and approximation factors subexponential in the field degree. More importantly, we uncover a close connection between structured lattice reduction and a Diophantine approximation over number fields.

Lebesgue's universal covering problem asks for the minimum area convex planar region capable of containing a congruent copy of every planar set of diameter at most one. In this paper, we develop an exact dual formulation of this problem through a minimum diameter analogue of Bellman's lost-in-a-forest problem. For a compact convex forest $F$, we define the critical escape diameter $D(F)$ as the minimum diameter of a closed path whose trace cannot be placed, under any rigid motion, entirely in the interior of $F$. We prove attainment of this minimum and establish a diameter cover/escape duality showing that the normalized body $D(F)^{-1}F$ is a Lebesgue universal cover. Consequently, the Lebesgue universal covering constant admits the exact representation \[ \mathcal L=\inf_F\frac{\operatorname{Area}(F)}{D(F)^2}, \] where the infimum ranges over compact convex planar bodies with nonempty interior. By reversing the rigid motion, we further characterize escape as intersection of a fixed path with every oppositely transformed boundary of $F$, and derive equivalent continuous curve, convex body, and support function optimization formulations. To make the infinite dimensional problem computationally tractable while retaining rigorous control of approximation error, we discretize the compact configuration space by an $\eta_m$-net and formulate the resulting problem as a minimum diameter traveling salesman problem with neighborhoods; for polygonal forests, an exact mixed-integer second-order cone formulation is obtained. We prove the quantitative certification, which yields convergent, rigorously certified universal cover bounds. The framework replaces finite tests of prescribed constant width shapes by a unified optimization over the full configuration space and extends naturally to other congruent and translative universal cover problems.

We prove a sharp boundedness result on $L^4(\mathbb R^2)$ for mollifications of the disc multiplier.

Let $X=G/H$ be a real reductive symmetric space. We consider the support of the Plancherel measure for the regular representation of $G$ on $L^2(X)$, and its Fell topology. We first recall how the Plancherel formula for $X$ (known from work of Delorme and van den Ban–Schlicktrull, among others) yields a description of the support in terms of the discrete spectra of smaller symmetric spaces. We then point out that this description simplifies for a class of real symmetric spaces $X$ which we call well-tempered. These are the spaces whose tangent space at the identity coset admits a Cartan subspace whose centralizer in the Lie algebra of $G$ is abelian. Well-tempered spaces are tempered in the sense of Benoist and Kobayashi. Under mild assumptions on the disconnectedness of $G$, we give a description of the support of the Plancherel measure for well-tempered symmetric spaces in terms of characters of Cartan subgroups of $G$, and describe the Fell topology of the support. If $G$ is a complex group and $H$ a real form, then the support decomposes as a union of explicit quotients of relative continuous-parameter spaces by finite Weyl groups. As an application, we describe the $C^*$-algebra associated to the regular representation of $G$ on $L^2(X)$, and its $K$-theory.

The long-run statistics of chaotic dissipative partial differential equations are described by invariant measures, and when the equation carries a parameter these measures form a family whose members can differ in kind, from steady states to sustained spatiotemporal chaos. We ask whether a single generative model can cover such a family. We train a single conditional diffusion model once, on states of the Kuramoto-Sivashinsky equation at 160 values of its hyperviscosity, and evaluate it against held-out data at interleaved parameter values not seen in training, using a classifier two-sample test supported by spectral, geometric and tail statistics. Over most of the family, agreement improves as the dynamics become more chaotic. We identify a structural cause: the weakly chaotic members have invariant measures concentrated on low-dimensional sets, which a model with full support output cannot represent, and the target approaches full dimensionality as chaos increases. Restricting training to the strongly chaotic members reduces the classifier's excess over chance on those members by roughly 40%, and this restricted conditional model matches or exceeds models trained at single parameter values. On those members, generated samples reproduce energy spectra to within a resampling floor, with a small systematic deficit at the largest scales, and match the energy balance of held-out data.

Optimal first-order methods on non-Euclidean domains such as the $\ell_1$ ball $B_1^n(R)=\{x\in\mathbb R^n:\|x\|_1\le R\}$ pair the prox-function with the norm in which smoothness is measured. When the gradient is $L$-Lipschitz in the Euclidean norm only, the accelerated method with a Euclidean prox-setup reduces the functional gap $f(x_N)-\min_{B_1^n(R)}f$ to $O(LR^2/N^2)$ after $N$ first-order queries (an entropic $\ell_1$ prox-setup replaces $L$ by the $\ell_1\to\ell_\infty$ constant $L_1\le L$, at the cost of a factor $\log n$ and with the same exponent). The lower bound of Guzmán and Nemirovski is of order $LR^2/N^3$, and whether the upper bound can be brought down to that order is a question of A. S. Nemirovski. We show that for this mismatched problem the minimax value of the gap is of order $LR^2/N^3$ up to logarithmic factors, for deterministic and for randomized methods alike, and already in dimension proportional to the number of queries. The upper bound is attained by a Steiner-point level method: every supporting hyperplane seen so far is kept as a level cut, and the next query is made near the Steiner point of the resulting localization polytope. The analysis rests on a single geometric fact: along nested subsets of the ball the Steiner points travel a distance that is polylogarithmic in the dimension, in contrast to $\sqrt n$ for the Euclidean ball. All queries stay feasible, and a randomized selector keeps the internal work polynomial. The same geometry yields optimal rates for nonsmooth objectives, Hölder gradients, higher-order oracles and Lipschitz monotone operators, the last with a matching deterministic lower bound. For convex quadratics, a curvature-learning method attains the optimal rate on every $\ell_p$ ball with $1\le p<2$ and without logarithmic loss. Experiments confirm the predicted $N^{-3}$ behaviour on objectives that are hard for Euclidean methods.

We construct skew cyclic codes in the rank metric from the torsion of the supersingular Drinfeld module $\phi_T=t+\tau^n$ over $\mathbb{F}_{q^r}$, where $t$ is a root of a monic irreducible $\mathfrak{p}_0\in\mathbb{F}_q[T]$ of degree $r$ coprime to $n$. For every prime $\mathfrak{p}\neq\mathfrak{p}_0$ of degree $d$ and every divisor $m$ of $n$, the torsion $\phi[\mathfrak{p}]$ is a free module over the subring $R_0=\kappa[\pi^m]$ generated by a power of the Frobenius $\pi=\tau^r$, $\kappa=\mathbb{F}_q[T]/\mathfrak{p}$, and the codes are the left ideals of the centralizer $R\cong\mathrm{Mat}_m(R_0)$ of $R_0$. We prove a lattice anti-isomorphism between codes and $R_0$-submodules of $\phi[\mathfrak{p}]$, and a rank-BCH bound whose designed distance is the true distance.

In 2002 Nielsen and Zhou conjectured that the shifted wavelet packet system associated with a Daubechies filter of length at least four fails to be a Schauder basis of $L^p(\mathbb{R})$ for $1\le p\le\infty$, $p\ne2$, and that the packets are not uniformly bounded in $p$-mean across scales for any $p>2$. The basis obstruction throughout the range $1<p<\infty$, $p\ne2$, was previously established for length four, via an explicit computation; the full $p$-mean assertion remained open. We prove both for every Daubechies filter of length at least four: the high-pass transition matrices satisfy $\rho_p\rho_{p'}>2$ for $1<p<\infty$, $p\ne2$, and for $p>2$ the full family of transition matrices has $p$-norm joint spectral radius exceeding the Haar value $4^{1/p}$. The key step is structural: an affine piece of the matrix pressure forces constant spectral radius, which by a theorem of Protasov and Voynov forces simultaneous orthogonality of the transition matrices, incompatible with the double zero of the high-pass symbol. The results extend to every real spectral factor with the Daubechies magnitude response, including the least-asymmetric filters.

The following is a natural and fundamental question for a graph $G$: if an induced subgraph $H$ of $G$ has $x$ more vertices than a maximum independent set, what can be said about the maximum degree of $H$ as a function of $x$? The case $x=1$ is already of considerable interest. For example, in his celebrated proof of the sensitivity conjecture, Hao Huang showed that every induced subgraph of the hypercube $Q_n$ on more than $2^{n-1}$ vertices has maximum degree at least $\sqrt{n}$. Chung, Fúredi, Graham, and Seymour proved that this bound is tight. In this paper, we study this question when $G$ is either the $n$-fold Hamming product or the $n$-fold tensor product of a triangle. For both graphs, we determine the exact minimum possible average degree of an induced subgraph of a prescribed size. We also prove that the tensor product exhibits several Huang-like phenomena. For the Hamming product, we show that, for several size densities and large $n$, the minimum possible maximum degree is asymptotically equal to the minimum possible average degree. Finally, we extend several of the results from the triangle to an arbitrary complete graph $K_k$.

The Skolem–Mahler–Lech Theorem asserts that a non-degenerate linear recurrence sequence (LRS) has only finitely many zeros, but is ineffective in the sense that no general procedure is known to determine them. In this paper a pseudo-effective approach is introduced: rather than seeking effective bounds for every sequence, one obtains explicit bounds valid for all but a controlled number of sequences of bounded height, up to a natural equivalence. Such results are established for order $3$ LRS's, and extended to all higher orders subject to suitable height constraints on the characteristic roots. The underlying mechanism is a quantitative theory for exponential-polynomial equations subject to low-height multiplicative perturbations. In particular, it is shown that the finiteness phenomenon underlying the Skolem–Mahler–Lech Theorem persists under arithmetic perturbations whose height is permitted to grow linearly at a sufficiently small rate. As a further application, a moving-target finiteness result is established for linear orbits entering expanding arithmetic neighbourhoods of proper linear subspaces.

In this paper, we present a multi-period optimization problem arising from the traffic engineering of core IP/MPLS networks, called T-ASR. This problem aims at computing a sequence of segment routing paths that adapt to a multi-period scheduled maintenance, while allowing limited number of path reconfigurations between successive time steps. Rather than focusing solely on minimizing the classical Maximum Link Utilization (MLU) criteria, we introduce a more refined lexicographic objective that minimizes the entire sorted vector of link loads providing a more efficient resource utilization for all the links. We propose a generic approach that decomposes this problem into a sequence of subproblems. To model each subproblem, we introduce two Mixed Integer Linear Programming (MILP) formulations, ALEXA and STELA, resulting in two variants of our approach. Finally, we evaluate and compare the efficiency of both variants on small to medium-sized network instances.

Turbulent flows span a wide range of scales, making direct numerical simulation (DNS) prohibitively expensive at high Reynolds numbers. Large eddy simulation (LES) offers a pragmatic alternative by only resolving the large-scale motions, but its accuracy hinges on the subgrid-scale (SGS) model. We introduce the Tau-orthogonal (TO) framework to the lattice Boltzmann method (LBM) using a macroscopic-velocity forcing. The TO method shifts the modeling target from a high-dimensional SGS field to the time dynamics of a small set of spatially integrated quantities of interest (QoIs). Training data are generated by a predictor-corrector tracking procedure that nudges coarse simulations toward reference QoI trajectories. Lightweight linear regression models with stochastic, multivariate Gaussian residuals (LRS) then drive the LES autonomously. Compact convolution-based kernels replace the sharp Fourier filters of the original formulation, lifting its restriction to rectangular periodic domains. We first evaluate the closure on two-dimensional Kolmogorov flow, where TO-LRS yields stable, statistically accurate online LES. However, bounded high-frequency oscillations are observed in the solution fields. The decisive test is three-dimensional turbulent channel flow, simulated on a grid five times coarser in every direction than the high-fidelity reference. Here the plain BGK solver is unstable, and even calibrated Smagorinsky and WALE models over-dissipate the near-wall flow. TO-LRS, applied on top of an eddy-viscosity substrate and with the QoI set augmented by mean-profile QoIs, reproduces the reference distributions and holds the DNS mean velocity profile, at $40\times$ lower online cost per simulated time unit than the high-fidelity simulation. These results establish reduced, QoI-based closures as an interpretable and inexpensive alternative to high-dimensional neural SGS models for LBM.

We characterize the continuous mappings of the unit disk that preserve every Carleson interpolating sequence. Preservation in one direction is equivalent to being a disk homeomorphism whose inverse is uniformly continuous in the pseudohyperbolic metric and whose associated weighted pushforward is bounded on positive Carleson measures. Preservation in both directions is equivalent to being a disk homeomorphism that, together with its inverse, is uniformly continuous in that metric and has a strongly quasisymmetric boundary extension. Within this class, comparability of the boundary defects is equivalent to a bi-Lipschitz boundary map. Building on the canonical factorization established in our earlier work, we give explicit criteria for membership in the continuous boundary kernel. For a homeomorphism of the closed disk with identity boundary values and a uniform boundary expansion of first order, kernel membership is equivalent to positivity of the determinant of the real boundary differential, or equivalently of the inward normal derivative of the boundary defect. No differentiability in the interior is required. The $C^1$ criterion on the closed disk follows as a corollary, while a counterexample shows that pointwise boundary differentiability does not suffice. We also characterize factorizations with a quasiconformal kernel and record the exact maximal dilatation of its radial factor.

A clear link is established between conventional numerical methods and neural network approximations for solving one-dimensional scalar conservation laws. The focus is on the construction of an appropriate flux term in the case of convex flux functions for improving the classical schemes. The first neural network developed here is able to rediscover Godunov's method, while the second one emulates the behavior of a second-order slope-limiter function. In this way, by merging them, second-order reconstruction-based schemes can be developed. The networks presented here employ a minimal number of parameters, significantly reducing the complexity compared to previous approaches. These networks can also be linked consecutively to get a deep one corresponding to multiple time steps. Training them with an appropriate loss leads to stable schemes, improving even the classical methods without increasing their complexity.

This mostly expository paper gives a unified treatment of many interpolation results for bandwidth-limited functions on locally compact abelian groups, based on reproducing kernel Hilbert spaces. It includes an abstract interpolation theorem phrased in terms of frames.

In this paper, we investigate how adaptive time-integration strategies can be effectively combined with parallel-in-time numerical methods for solving systems of ordinary differential equations. Our focus is particularly on their influence on tolerance proportionality. We examine various grid-refinement strategies within the multigrid reduction-in-time (MGRIT) framework. Our results show that a simple adjustment to the original refinement factor can substantially improve computational stability and reliability. Through numerical experiments on standard test problems using the XBraid library, we demonstrate that parallel-in-time solutions closely match their sequential counterparts. Moreover, with the use of multiple processors, computing time can be significantly reduced.

This paper studies the nonconvex optimization landscape of Linear Quadratic Gaussian (LQG) control under direct state-space parameterization. Although the LQG cost may possess suboptimal stationary points, whether it admits suboptimal local minima has remained open. We answer this question negatively: Every local minimum of the full-order LQG cost is globally optimal. More generally, at any controller order, every local minimum corresponding to an uncontrollable or unobservable realization attains the globally optimal LQG cost over all stabilizing policies of arbitrary orders. We further show that any suboptimal policy can be augmented with decoupled stable controller states, so that the augmented policy admits a direction of negative curvature with probability one. Consequently, any suboptimal stationary point in full-order LQG cost can be converted into a strict saddle with probability one. One key proof idea connects the state-space Hessian to a frequency-domain global-optimality condition derived from the Youla parameterization. These results reveal a benign local-minimum landscape despite the presence of suboptimal stationary points.

We study the Sampled-Max Subgradient Method (SMax-SGM) for large convex finite-max problems. Each iteration maximizes over a fresh random subset of the $N$ components and takes one subgradient of the sampled maximizer. The method is therefore stochastic subgradient descent on a sampled-max surrogate. We bound the surrogate error by an average-top-$k$ gap plus the probability of missing all top-$k$ components. A localization argument requires these quantities only on a near-optimal sublevel set. Under a bounded subgradient-moment assumption, this yields $O(\varepsilon^{-2})$ subgradient queries and, when $k$ components remain nearly active in that set, $\widetilde O((N/k)\varepsilon^{-2})$ component-value queries, capped by the full-scan cost. Conversely, a one-dimensional affine construction shows that $\Omega(N/k)$ component-value queries can be necessary even when the average-top-$k$ gap vanishes everywhere and subgradient queries are unlimited. A tensor-grid specialization explains when the subset size can become independent of grid cardinality. Experiments on finite maxima with $2\times10^5$ and $5\times10^6$ components show that, under the reported protocols, SMax-SGM reaches a 5% numerical-reference gap with fewer component-value queries and lower optimizer time than each comparison method that reaches the target.

Let $G_n$ be the bipartite complement of the even cycle $C_{2n}$, and let $J_{G_n}$ be its binomial edge ideal. For $n\geq5$, we study the interaction between the combinatorial structure of $G_n$ and the algebraic invariants of $S_{G_n}/J_{G_n}$. Our main combinatorial ingredient is a classification of the subsets of $V(G_n)$ having the cut point property, obtained through an analysis of disconnected induced subgraphs of $G_n$. We use this classification to describe the minimal primes and to study dimension and degree-theoretic invariants of $J_{G_n}$ and $S_{G_n}/J_{G_n}$. We also study local Vasconcelos numbers, graded Betti numbers and the Hilbert series, and obtain information on projective dimension and depth. Finally, we analyze induced paths in $G_n$ and derive corresponding bounds for the Castelnuovo–Mumford regularity.