Analysis of PDEs
Papers
Fresh from arXiv, typeset properly. Highlighted words trade on the market.
Wednesday 15 April
In this note we show the existence of a residual set (in the sense of Baire) of divergence free initial data $u_0\in L^2(D)$, $D=\mathbb{R}^2$ or $\mathbb{T}^2$, for which global existence and uniqueness of weak solutions to the incompressible 2D Euler equations holds. The associated solutions $u$ satisfy the energy balance and are recovered in the vanishing viscosity limit from solutions to 2D Navier-Stokes, which as a consequence cannot display anomalous dissipation of energy. Additionally, there exists a unique regular Lagrangian flow associated to such $u$, and the associated transport equation is well-posed. Finally, when $D=\mathbb{T}^2$, the solution $u$ is recovered as the limit of Galerkin approximations. The proof relies on global existence of smooth solutions and weak-strong uniqueness arguments.
Differential Geometry
Quantification of $C^0$ Convergence in Dimension Three
We address Gromov's Quantification of $C^0$ Convergence Conjecture in dimension three. Let $B$ be the unit ball in $\mathbb R^3$. Let $g$ and $g_0$ be smooth metrics on $B$. We prove there are constants $C$ and $\epsilon_0$ depending only on $g_0$ so that \[ \inf_{x\in B} R_g(x) \leq R_{g_0}(0) + C \|g-g_0\|_{C^0}^{1/2} \] provided $\|g-g_0\|_{C^0}\leq \epsilon_0$. We also construct examples to show that the exponent $1/2$ is sharp. This explicitly quantifies the fact that scalar curvature lower bounds are preserved under $C^0$ convergence of metrics. When $g_0$ is merely $C^2$ we prove a related estimate with a slightly weaker rate, and when $g_0$ has rotational symmetry we prove a related estimate with a stronger linear rate. To prove these results, we use harmonic functions to define a local quantity that detects the scalar curvature. Then we use classical elliptic PDE estimates to show that this quantity is stable under $C^0$ perturbations of the metric. As a further application of this method, we give a partial answer to a question of Gromov on the preservation of scalar curvature lower bounds for metrics that are converging in measure.
Read the full abstract
Algebraic Geometry
Relative Langlands duality and Koszul duality
Consider a pair of $S$-dual hyperspherical varieties $G\circlearrowright X$ and $G^\vee\circlearrowright X^\vee$ equipped with equivariant quantizations $Q(X)$, $Q(X^\vee)$. Assume that the local conjecture of Ben-Zvi, Sakellaridis and Venkatesh holds for this pair, and also that $X\simeq T^*_\psi(Y)$ is polarized, so that $Q(X)=D_\psi(Y)$. Let $B\subset G$ (resp. $B^\vee\subset G^\vee$) be Borel subgroups. Then using a variant of the $S^1$-equivariant localization of arxiv:0706.0322, we deduce an equivalence between the ${\mathbb Z}/2$-graded $B$-equivariant category $(D_\psi(Y)\operatorname{-mod}^B)^{{\mathbb Z}/2}$ and the ${\mathbb Z}/2$-graded unipotent $B^\vee$-monodromic category $(Q(X^\vee)\operatorname{-mod}^{B^\vee,\operatorname{mon}})^{{\mathbb Z}/2}$.
Read the full abstract
Mathematical Physics
Open WDVV equations and $\bigvee$-systems
The idea of a $\bigvee$-system was introduced by Veselov in the study of rational solutions of the WDVV equations of associativity. These are algebraic/geometric conditions on the set of covectors that appear in rational solutions to the WDVV equations. Here, this idea is generalized to open WDVV equations, which are an additional set of PDEs originating from open Gromow-Witten Theory. We develop – for rank-one extensions – algebraic/geometric conditions on the covectors that supplement the $\bigvee$-system to give rational solutions to the open WDVV equations. Examples, and the relation to superpotentials and to Dubrovin almost-duality, are given.
Read the full abstract
Analysis of PDEs
Coagulation equations with particle emission
We present a model for sticky particles in which cluster sizes after a reaction have $\ell$ fewer total particles than the sum of their reactants. The finite particle system is modeled as a Markov process under a mean-field assumption for selecting reactants. The limiting kinetic equations form an infinite system of nonlinear differential equations similar to the Smoluchowski coagulation equations with multiplicative kernel. We show existence and uniqueness for systems whose cluster sizes are either bounded above or below by the emission size $\ell$. When clusters have at most $\ell$ particles, well-posedness can be extended until an exhaustion time in which certain cluster fractions vanish. For clusters with more than $\ell$ particles, we prove short-time well-posedness, along with explicit formulas for cluster sizes and moments. We also conduct numerical experiments which suggest these formulas hold until a gelation time, at which an infinite-sized cluster forms.
Read the full abstract
Optimization and Control
Multistage Conditional Compositional Optimization
We introduce Multistage Conditional Compositional Optimization (MCCO) as a new paradigm for decision-making under uncertainty that combines aspects of multistage stochastic programming and conditional stochastic optimization. MCCO minimizes a nest of conditional expectations and nonlinear cost functions. It has numerous applications and arises, for example, in optimal stopping, linear-quadratic regulator problems, distributionally robust contextual bandits, as well as in problems involving dynamic risk measures. The naïve nested sampling approach for MCCO suffers from the curse of dimensionality familiar from scenario tree-based multistage stochastic programming, that is, its scenario complexity grows exponentially with the number of nests. We develop new multilevel Monte Carlo techniques for MCCO whose scenario complexity grows only polynomially with the desired accuracy.
Read the full abstract
Statistics Theory
Finite-Step Bounds for Iterated Correlation Matrices
We establish finite-step probabilistic upper bounds on the contraction ratios $\rho_k = \Delta_{k+1}/\Delta_k$ for iterated Pearson correlation dynamics. Let $(P_k)_{k\ge 0}$ be the sequence generated by the Pearson update. Define $\Delta_k := \|P_{k+1}-P_k\|_F$, $\rho_k := \Delta_{k+1}/\Delta_k$ for $\Delta_k > 0$, and $\delta_k := \Delta_k/n$. Although $\Delta_k \to 0$ along convergent trajectories, the ratios $\rho_k$ may exceed unity in finitely many steps. This behavior is invisible to local linearization. Our main contribution is a probabilistic bounding framework that captures these finite-step expansions. We initialize $P_0$ with i.i.d. $\mathcal{U}[-1,1]$ entries and let $\mathbb{P}$ be the induced measure. For $k \ge 2$, we construct state-dependent bounds $B_p : \mathbb{R}_+ \to \mathbb{R}_+$ satisfying $\mathbb{P}(\rho_k \le B_p(\delta_k)) \ge p$. The functions $B^{\mathrm{q}}_p(\delta)$ are empirical conditional $p$-quantiles of $\log \rho_k$ given $\delta_k$ under logarithmic binning. Larger families $B^{\mathrm{TC}}_{p,\tau}(\delta)$ and $B^{\mathrm{tol}}_{p,\tau}(\delta)$ are obtained via multiplicative adjustments, yielding pointwise larger bounds that preserve the $\delta$-dependence. Validation on held-out trajectories confirms the bounds hold with empirical coverage matching nominal levels for all $n \in [3,2000]$. The baseline $0.95$-quantile bound $B^{\mathrm{q}}_{0.95}(\delta)$ yields two concrete results: $\mathbb{P}(\rho \le 1 \mid \delta \le 0.03) \ge 0.95$ uniformly in $n$, and $\mathbb{P}(\rho \le 1.7) \ge 0.95$ for 21 of 22 dimensions. The exception $n = 69$ attains $2.35$, revealing a rare extreme upper tail discontinuity not captured by asymptotic analysis. These are the first finite-step probabilistic bounds for Pearson correlation dynamics. The framework is fully reproducible with provided code and data.
Read the full abstract
Functional Analysis
A study on coreflexive Banach Spaces
In this paper, we study non-reflexive Banach spaces $X$ for which the quotient space $X^{**}/X$ is reflexive. Such spaces were first introduced by James R.~Clark, where they were called coreflexive spaces. We show that a space $X$ is coreflexive if and only if every separable subspace $Y\subseteq X$ is coreflexive, provided that $X$ is w$^*$-sequently dense in its bidual $X^{**}$. We show that coreflexive spaces are stable under $\ell^{p}$-sum for $1<p<\infty$. We show that if $X$ is a coreflexive space such that $X^{**}/X$ is separable, then the space of Bochner $p$-integrable functions, $L^{p}(\mu,X)$ is coreflexive for $1<p<\infty$. We conclude by providing an alternative proof of the fact, in a quasi-reflexive space $X$, w-PC's of the unit ball $X_{1}$ continue to have the same property in all the higher even-order dual unit balls of $X$.
Read the full abstract
Information Theory
Two-Sided Bounds for Entropic Optimal Transport via a Rate-Distortion Integral
We show that the maximum expected inner product between a random vector and the standard normal vector over all couplings subject to a mutual information constraint or regularization is equivalent to a truncated integral involving the rate-distortion function, up to universal multiplicative constants. The proof is based on a lifting technique, which constructs a Gaussian process indexed by a random subset of the type class of the probability distribution involved in the information-theoretic inequality, and then applying a form of the majorizing measure theorem.
Read the full abstract
Information Theory · Cross-listed from quant-ph
Two-Indexed Schatten Quasi-Norms with Applications to Quantum Information Theory
We define 2-indexed $(q,p)$-Schatten quasi-norms for any $q,p > 0$ on operators on a tensor product of Hilbert spaces, naturally extending the norms defined by Pisier's theory of operator-valued Schatten spaces. We establish several desirable properties of these quasi-norms, such as relational consistency and the behavior on block diagonal operators, assuming that $|\frac{1}{q} - \frac{1}{p}| \leq 1$. In fact, we show that this condition is essentially necessary for natural properties to hold. Furthermore, for linear maps between spaces of such quasi-norms, we introduce completely bounded quasi-norms and co-quasi-norms. We prove that the $q \to p$ completely bounded co-quasi-norm is super-multiplicative for tensor products of quantum channels for $q \geq p>0$, extending an influential result of [Devetak, Junge, King, Ruskai, 2006]. Our proofs rely on elementary matrix analysis and operator convexity tools and do not require operator space theory. On the applications side, we demonstrate that these quasi-norms can be used to express relevant quantum information measures such as Rényi conditional entropies for $\alpha \geq \frac{1}{2}$ or the Sandwiched Rényi Umlaut information for $\alpha < 1$. Our multiplicativity results imply a tensorizing notion of reverse hypercontractivity, additivity of the completely bounded minimum output Rényi-$\alpha$-entropy for $\alpha\geq\frac{1}{2}$ extending another important result of [Devetak, Junge, King, Ruskai, 2006], and additivity of the maximum output Rényi-$\alpha$ entropy for $\alpha \geq \frac{1}{2}$.
Read the full abstract
Numerical Analysis
Submatrices with the best-bounded inverses: the equality criterion for $\mathbb{R}^{n \times 2}$
The long-standing hypothesis formulated by Goreinov, Tyrtyshnikov and Zamarashkin \cite{GTZ1997} has recently been solved positively by Sengupta and Pautov \cite{SP2026} in the case of two-column matrices. In this paper, we complement their elegant proof with the equality criterion.
Read the full abstract
Combinatorics
On the Scalability of Quasi-Complementary Sequence Sets: Quadratic and Cubic Laws
This work is concerned with the fundamental scaling laws of quasi-complementary sequence sets (QCSSs) by understanding how large the set size (denoted by $M$) can grow with the flock size ($K$) and the sequence length ($N$). We first establish a geometric framework that transforms a QCSS into a complex unit-norm codebook, through which and by exploiting the density thresholds of the codebooks, certain polynomial upper bounds of the QCSS set size are obtained. Sharp quadratic and cubic scaling laws are then introduced. Specifically, we show that asymptotically optimal QCSSs with tightness factor $\rho=1$ satisfy $M \le (1+o(1))K^2N$, while asymptotically near-optimal QCSSs satisfy $M \le (1+o(1))K^3N^2$ for $\rho < {(1+\sqrt{5})}/{2}$. To validate these upper bounds, we further propose explicit additive-character and mixed-character based constructions for QCSSs that achieve $M = K^2N + K$ and $M = K^3N^2 + 2K^2N + K$, respectively, thereby showing that the quadratic and cubic scaling laws are asymptotically tight. Our proposed constructions admit flexible parameter choices, and their maximum correlation estimates are shown to be tight through explicit extremal examples. Additionally, it is conjectured that the cubic scaling law is universal for all $1<\rho\le 2$, i.e., any asymptotically near-optimal QCSSs should satisfy $M \le (1+o(1))K^3N^2$. This identifies a fundamental cubic barrier for QCSS scalability.
Read the full abstract
Algebraic Geometry
A lower bound on the Calabi functional for a degeneration of polarized varieties
We prove a lower bound on the Calabi functional for degenerations of polarized varieties, involving the difference of CM degrees between generically isomorphic families. This may be viewed as a discretely valued version of Donaldson's lower bound for models, in the sense of non-Archimedean geometry. In particular, this generalizes a result of Donaldson, who considered a single polarized variety. As a main tool, we develop the theory of GIT height, introduced by Wang, and apply it to the family GIT problem of the Chow variety. Using the GIT height, we also give a numerical proof of separatedness of GIT quotients for general and special linear actions, strengthening prior work of Wang–Xu.
Read the full abstract
Algebraic Geometry · Cross-listed from cs.LG
A Complete Symmetry Classification of Shallow ReLU Networks
Parameter space is not function space for neural network architectures. This fact, investigated as early as the 1990s under terms such as “reverse engineering," or “parameter identifiability", has led to the natural question of parameter space symmetries\textemdash the study of distinct parameters in neural architectures which realize the same function. Indeed, the quotient space obtained by identifying parameters giving rise to the same function, called the neuromanifold, has been shown in some cases to have rich geometric properties, impacting optimization dynamics. Thus far, techniques towards complete classifications have required the analyticity of the activation function, notably excising the important case of ReLU. Here, in contrast, we exploit the non-differentiability of the ReLU activation to provide a complete classification of the symmetries in the shallow case.
Read the full abstract
Number Theory
Distribution modulo one of linear recurrent sequences
We study the distribution modulo one of linear recurrent sequences of real numbers. We prove criteria for the finiteness of the set of limit values of the fractional parts of such a sequence and give lower bounds for the maximal distance between two limit values. Our results generalize theorems of Flatto, Lagarias, Pollington, and Dubickas.
Read the full abstract
Functional Analysis
On the divergence of the composition of irregular fields with BV functions
We introduce a family of (nonlinear) pairing measures that ensure the validity of the divergence rule for composite functions $\boldsymbol{B}(x,u(x))$, where $\boldsymbol{B}(\cdot,t)$ is a bounded divergence-measure vector field, and $u$ is a scalar function of bounded variation. The elements of the family depend on the choice of the pointwise representative of $u$ on its jump set. Beyond the standard properties, such as the Coarea and Gauss-Green formulas on sets of finite perimeter, this flexibility allows us to characterize the pairings that ensure the lower semicontinuity of the corresponding functionals along sequences converging in $L^1$ with controlled precise values. We show that these lower semicontinuous pairings arise as the relaxation of integral functionals defined in Sobolev spaces.
Read the full abstract
Category Theory
Topologically valued transition structures
We investigate several categories related to transition structures, using a mixture of algebraic and topological methods. We show how two such categories are connected by a contravariant adjunction. This is the most detailed of a family of such results depending on topological restrictions on objects and morphisms.
Read the full abstract
Algebraic Geometry
Deformations of fibered Calabi–Yau varieties
Kollár showed that small deformations of elliptically fibered smooth $K$-torsion varieties with $H^2(X,\mathcal{O}_X)=0$ remain elliptically fibered. We extend this result to any fibered smooth $K$-torsion variety $X$ with $H^2(X,\mathcal{O}_X)=0$, using Hodge theoretic techniques and the $T^1$-lifting criterion of Kawamata–Ran. More generally, our strategy implies that even without the cohomological assumption, small deformations of a semiample line bundle on a smooth $K$-torsion variety remain semiample up to homological equivalence.
Read the full abstract
Logic
Continuous first-order logic of abstract harmonic spaces
This paper studies Brelot harmonic spaces within an unbounded many-sorted continuous first-order language and its expansions. 1. In the finite evaluation reduct of the harmonic language, the Brelot theory together with the finite interpolation scheme eliminates bounded harmonic quantifiers while leaving point quantifiers untouched. 2. The Martin compactification is homeomorphic to a compact subset of the local type space, with the Martin boundary corresponding to non-principal types. 3. If the compact convex space of normalized positive harmonic functions is a Choquet simplex, then each Martin representing measure on the minimal boundary corresponds to a unique Keisler measure supported on minimal types and admits a complete lift. 4. Harnack compactness also implies stability of normalized evaluation formulas, yielding canonical bases and a harmonic barycenter factoring through Keisler measures. These constructions are further applied to fine potential theory, where boundary poles of potentials are Keisler null. First-jet expansions encode the Radó–Kneser–Choquet and Lewy planar rigidity phenomena, while higher-dimensional failures are analyzed through thorn-forking chains in o-minimal expansions.
Read the full abstract
Optimization and Control
Stochastic Trust-Region Methods for Over-parameterized Models
Under interpolation-type assumptions such as the strong growth condition, stochastic optimization methods can attain convergence rates comparable to full-batch methods, but their performance, particularly for SGD, remains highly sensitive to step-size selection. To address this issue, we propose a unified stochastic trust-region framework that eliminates manual step-size tuning and extends naturally to equality-constrained problems. For unconstrained optimization, we develop a first-order stochastic trust-region algorithm and show that, under the strong growth condition, it achieves an iteration and stochastic first-order oracle complexity of $O(\varepsilon^{-2} \log(1/\varepsilon))$ for finding an $\varepsilon$-stationary point. For equality-constrained problems, we introduce a quadratic-penalty-based stochastic trust-region method with penalty parameter $\mu$, and establish an iteration and oracle complexity of $O(\varepsilon^{-4} \log(1/\varepsilon))$ to reach an $\varepsilon$-stationary point of the penalized problem, corresponding to an $O(\varepsilon)$-approximate KKT point of the original constrained problem. Numerical experiments on deep neural network training and orthogonally constrained subspace fitting demonstrate that the proposed methods achieve performance comparable to well-tuned stochastic baselines, while exhibiting stable optimization behavior and effectively handling hard constraints without manual learning-rate scheduling.
Read the full abstract
Combinatorics
Coloring powers of random graphs
Given a graph $G$ and an integer $r\ge 1$, the $r$th power $G^r$ of $G$ is the graph obtained from $G$ by adding edges for all pairs of distinct vertices at distance at most $r$ from each other. We focus on two basic structural properties of the $r$th power of the binomial random graph $G_{n,p}$, namely, the maximum degree $\Delta(G_{n,p}^r)$ and the chromatic number $\chi(G_{n,p}^r)$, and give with high probability (w.h.p.) bounds. In the sparse case that $p=d/n$ for some fixed constant $d>0$, we prove the following. We prove that w.h.p.~$\Delta(G_{n,p}^r) \sim \frac{\log n}{\log_{(r+1)}n}$ (where $\log_{(1)}n=\log n$ and $\log_{(r+1)}n=\log\log_{(r)}n$) and that w.h.p.~$\Delta(G_{n,p}^{\lfloor{r/2}\rfloor})+1 \le \chi(G_{n,p}^r) \le \Delta(G_{n,p}^{r-1})+1$. For $r=2$, we show the upper bound holds with equality. For denser cases, for $d$ satisfying $d=\omega(\log n)$ and $d\le n^{1/r-\Omega(1)}$ as $n\to\infty$, we have $\chi(G_{n,p}^r) = \Theta(d^r/\log d)$ w.h.p.
Read the full abstract
Analysis of PDEs
The Makai inequality in higher dimensions: qualitative and quantitative aspects
In this paper, given a convex, bounded, open set $\Omega \subset \mathbb{R}^n$ we prove a sharp inequality involving the Laplacian torsional rigidity and both the perimeter and the measure of the domain. Our result generalizes to arbitrary dimensions the inequality established by Makai in the plane which, as conjectured in arXiv:2007.02549. Furthermore, we establish quantitative estimates that provide key insights into the geometric structure and the thickness of the underlying optimizing sequences.
Read the full abstract
Geometric Topology
Triple-cup product forms of 3-manifolds and Heegaard diagrams
The triple-cup product form $\mu$ is a classical invariant of $3$-manifolds, determining the cohomology ring up to torsion. Given a closed, connected, oriented $3$-manifold $M$, we describe an explicit formula for computing $\mu$ from a Heegaard diagram of $M$. Then, we show that the triple-cup product form $\mu$ can be recovered as a reduction of Turaev's homotopy intersection form $\eta$ of the Heegaard surface.
Read the full abstract
Group Theory
Computing least common multiples in monoids with a finite Garside family
Right-reversing is an algorithm used to compute least common multiples in monoids that admit a right-complemented presentation. The algorithm can either terminate and find a result, fail, or run indefinitely. The correctness of the algorithm can be proved with additional assumptions coming from Garside theory. In the same framework, we prove that a non-terminating run of the algorithm is necessarily cyclic. Stopping when a cycle is detected provides a way of computing a minimal Garside family.
Read the full abstract
Numerical Analysis · Cross-listed from cs.LG
Unsupervised domain transfer: Overcoming signal degradation in sleep monitoring by increasing scoring realism
Objective: Investigate whether hypnogram 'realism' can be used to guide an unsupervised method for handling arbitrary types of signal degradation in mobile sleep monitoring. Approach: Combining a pretrained, state-of-the-art 'u-sleep' model with a 'discriminator' network, we align features from a target domain with a feature space learned during pretraining. To test the approach, we distort the source domain with realistic signal degradations, to see how well the method can adapt to different types of degradation. We compare the performance of the resulting model with best-case models designed in a supervised manner for each type of transfer. Main Results: Depending on the type of distortion, we find that the unsupervised approach can increase Cohen's kappa with as little as 0.03 and up to 0.29, and that for all transfers, the method does not decrease performance. However, the approach never quite reaches the estimated theoretical optimal performance, and when tested on a real-life domain mismatch between two sleep studies, the benefit was insignificant. Significance: 'Discriminator-guided fine tuning' is an interesting approach to handling signal degradation for 'in the wild' sleep monitoring, with some promise. In particular, what it says about sleep data in general is interesting. However, more development will be necessary before using it 'in production'.
Read the full abstract
Numerical Analysis
Approximation properties of double complexes
We consider the simplicial de Rham complex and the Čech-de Rham complex, two bigraded Hilbert complexes whose Hodge-Laplace problems govern spatially coupled problems in mixed dimension and homogeneous dimension, respectively. The former complex can be realized as a subcomplex of the latter. In this paper, we quantify how close these complexes are to each other by constructing bounded cochain complexes between them, and thus we quantify how close a mixed-dimensional formulation of a problem is to an equidimensionally coupled formulation of the same problem. From this construction, we derive a priori- and a posteriori error estimates between the associated Hodge-Laplace problems on the two complexes. These estimates represent the error which is introduced by treating a spatially coupled problem as mixed-dimensional, rather than an equidimensional problem with thin overlaps.
Read the full abstract
Probability
Divisible sandpiles via random walks in random scenery
We analyze an optimal stopping problem for random walk in random scenery on general graphs, and determine when it has a finite optimum. We use this to extend a theorem of Levine, Murugan, Peres, and Ugurcan [2016]. They proved that on a vertex-transitive graph, the divisible sandpile with i.i.d. initial masses of mean $\mu$ stabilizes almost surely if $\mu < 1$, explodes if $\mu > 1$, and explodes if $\mu = 1$ with positive finite variance. Their proofs rely on conservation of mean mass under toppling. This conservation extends to unimodular random graphs, but fails on general graphs. We prove explosion for all infinite bounded-degree graphs whenever $\mu \geq 1$, and stabilization for $\mu<1$ provided the initial masses have finite $p$-th moment for some $p>3$. Our conditions are nearly sharp: we exhibit unbounded-degree graphs on which sandpiles with $\mu > 1$ stabilize, and for every $p < 3$ we construct bounded-degree graphs on which sandpiles with~$\mu < 1$ and finite $p$-th moment explode.
Read the full abstract
Information Theory
A class of locally differentially $4$-uniform power functions with Niho exponents
Niho exponents have found important applications in sequence design, coding theory, and cryptography. Determining the differential spectrum of a power function with Niho exponent is a topic of considerable interest. In this paper, we investigate the power function $F(x) = x^{3q - 2}$ over $\mathbb{F}_{q^2}$, where $q = 2^m$ and $m\geq 4$ is an even integer. Notably, the exponent $3q - 2$ is a Niho exponent. By analyzing the properties of certain polynomials over $\mathbb{F}_{q^2}$, we determine the differential spectrum of $F$. Our results show that $F$ is locally differentially $4$-uniform, which complements existing results on the differential spectra of power functions with Niho exponents.
Read the full abstract
Optimization and Control
Understanding the Variance Dichotomy in Continuous Simulation Optimization: A Minimax Lower Bound Perspective
This paper studies the variance dichotomy in continuous simulation optimization (CSO). Existing literature shows a sharp contrast between deterministic CSO and stochastic CSO, with convergence rates in stochastic settings appearing insensitive to the magnitude of the noise variance. However, this asymptotic view does not fully explain the behavior of CSO under finite simulation budgets, especially in low-noise settings. To address this gap, this work develops a minimax lower-bound analysis and shows that the complexity is decided by the maximum of a variance-dependent term and a variance-independent term. When the simulation budget is not very large and the noise variance is low, the variance-independent term dominates, implying that low-noise stochastic CSO has essentially the same complexity as deterministic CSO. As the budget increases, the variance-dependent term becomes dominant, and the convergence behavior of stochastic CSO transitions to a slower regime determined jointly by the noise variance and the simulation budget.
Read the full abstract
Group Theory · Cross-listed from cs.CC
Parallel Algorithms for Group Isomorphism via Code Equivalence
In this paper, we exhibit $\textsf{AC}^{3}$ isomorphism tests for coprime extensions $H \ltimes N$ where $H$ is elementary Abelian and $N$ is Abelian; and groups where $\text{Rad}(G) = Z(G)$ is elementary Abelian and $G = \text{Soc}^{*}(G)$. The fact that isomorphism testing for these families is in $\textsf{P}$ was established respectively by Qiao, Sarma, and Tang (STACS 2011), and Grochow and Qiao (CCC 2014, SIAM J. Comput. 2017). The polynomial-time isomorphism tests for both of these families crucially leveraged small (size $O(\log |G|)$) instances of Linear Code Equivalence (Babai, SODA 2011). Here, we combine Luks' group-theoretic method for Graph Isomorphism (FOCS 1980, J. Comput. Syst. Sci. 1982) with the fact that $G$ is given by its multiplication table, to implement the corresponding instances of Linear Code Equivalence in $\textsf{AC}^{3}$. As a byproduct of our work, we show that isomorphism testing of arbitrary central-radical groups is decidable using $\textsf{AC}$ circuits of depth $O(\log^3 n)$ and size $n^{O(\log \log n)}$. This improves upon the previous bound of $n^{O(\log \log n)}$-time due to Grochow and Qiao (ibid.).