An official website of the United States government
The authors present an algorithm that, given an n-vertex m-edge Eulerian graph with polynomially bounded weights, computes an 𝑂 ~ ( 𝑛 log 2 𝑛 ⋅ 𝜀 − 2 ) O ~ (nlog 2 n⋅ε −2 )-edge 𝜀 ε-approximate Eulerian sparsifier with high probability in 𝑂 ~ ( 𝑚 log 3 𝑛 ) O ~ (mlog 3 n) time (where 𝑂 ~ ( ⋅ ) O ~ (⋅) hides polyloglog(n) factors). By a reduction from Peng-Song (STOC ’22), this yields an 𝑂 ~ ( 𝑚 log 3 𝑛 + 𝑛 log 6 𝑛 ) O ~ (mlog 3 n+nlog 6 n)-time algorithm for solving n-vertex m-edge Eulerian Laplacian systems with polynomially bounded weights with high probability, improving on the previous state-of-the-art runtime of Ω ( 𝑚 log 8 𝑛 + 𝑛 log 23 𝑛 ) Ω(mlog 8 n+nlog 23 n). They also provide a polynomial-time algorithm that computes sparsifiers with 𝑂 ( min ( 𝑛 log 𝑛 ⋅ 𝜀 − 2 + 𝑛 log 5 / 3 𝑛 ⋅ 𝜀 − 4 / 3 , 𝑛 log 3 / 2 𝑛 ⋅ 𝜀 − 2 ) ) O(min(nlogn⋅ε −2 +nlog 5/3 n⋅ε −4/3 ,nlog 3/2 n⋅ε −2 )) edges, improving the previous best bounds. Furthermore, they extend their techniques to yield the first 𝑂 ( 𝑚 ⋅ polylog ( 𝑛 ) ) O(m⋅polylog(n))-time algorithm for computing 𝑂 ( 𝑛 𝜀 − 1 ⋅ polylog ( 𝑛 ) ) O(nε −1 ⋅polylog(n))-edge graphical spectral sketches, along with a natural Eulerian generalization. Unlike prior approaches using short cycle or expander decompositions, their algorithms leverage a new effective resistance decomposition scheme, combined with natural sampling and electrical routing for degree balance. The analysis applies asymmetric variance bounds specialized to Eulerian Laplacians and tools from discrepancy theory.
more »
« less
This content will become publicly available on November 28, 2025
A Schmidt–Nochka theorem for closed subschemes in subgeneral position
In previous work, the authors established a generalized version of Schmidt’s subspace theorem for closed subschemes in general position in terms of Seshadri constants.We extend our theorem to weighted sums involving closed subschemes in subgeneral position, providing a joint generalization of Schmidt’s theorem with seminal inequalities of Nochka.A key aspect of the proof is the use of a lower bound for Seshadri constants of intersections from algebraic geometry, as well as a generalized Chebyshev inequality.As an application, we extend inequalities of Nochka and Ru–Wong from hyperplanes in 𝑚-subgeneral position to hypersurfaces in 𝑚-subgeneral position in projective space, proving a sharp result in dimensions 2 and 3, and coming within a factor of 3/2 of a sharp inequality in all dimensions.We state analogous results in Nevanlinna theory generalizing the second main theorem and Nochka’s theorem (Cartan’s conjecture).
more »
« less
- Award ID(s):
- 2302298
- PAR ID:
- 10628550
- Publisher / Repository:
- De Gruyter
- Date Published:
- Journal Name:
- Journal für die reine und angewandte Mathematik (Crelles Journal)
- Volume:
- 819
- ISSN:
- 0075-4102
- Page Range / eLocation ID:
- 205-229
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This work aims to prove a Hardy-type inequality and a trace theorem for a class of function spaces on smooth domains with a nonlocal character. Functions in these spaces are allowed to be as rough as an [Formula: see text]-function inside the domain of definition but as smooth as a [Formula: see text]-function near the boundary. This feature is captured by a norm that is characterized by a nonlocal interaction kernel defined heterogeneously with a special localization feature on the boundary. Thus, the trace theorem we obtain here can be viewed as an improvement and refinement of the classical trace theorem for fractional Sobolev spaces [Formula: see text]. Similarly, the Hardy-type inequalities we establish for functions that vanish on the boundary show that functions in this generalized space have the same decay rate to the boundary as functions in the smaller space [Formula: see text]. The results we prove extend existing results shown in the Hilbert space setting with p = 2. A Poincaré-type inequality we establish for the function space under consideration together with the new trace theorem allows formulating and proving well-posedness of a nonlinear nonlocal variational problem with conventional local boundary condition.more » « less
-
Abstract We are interested in sharp functional inequalities for the coherent state transform related to the Wehrl conjecture and its generalizations. This conjecture was settled by Lieb in the case of the Heisenberg group, Lieb and Solovej for SU(2), and Kulikov for SU(1, 1) and the affine group. In this article, we give alternative proofs and characterize, for the first time, the optimizers in the general case. We also extend the recent Faber-Krahn-type inequality for Heisenberg coherent states, due to Nicola and Tilli, to the SU(2) and SU(1, 1) cases. Finally, we prove a family of reverse Hölder inequalities for polynomials, conjectured by Bodmann.more » « less
-
Abstract We establish the sharp growth rate, in terms of cardinality, of the $L^p$ norms of the maximal Hilbert transform $$H_\Omega $$ along finite subsets of a finite order lacunary set of directions $$\Omega \subset \mathbb{R}^3$$, answering a question of Parcet and Rogers in dimension $n=3$. Our result is the first sharp estimate for maximal directional singular integrals in dimensions greater than 2. The proof relies on a representation of the maximal directional Hilbert transform in terms of a model maximal operator associated to compositions of 2D angular multipliers, as well as on the usage of weighted norm inequalities, and their extrapolation, in the directional setting.more » « less
-
We use thin position of Heegaard splittings to give a new proof of Haken's Lemma that a Heegaard surface of a reducible manifold is reducible and of Scharlemann's ``Strong Haken Theorem'': a Heegaard surface for a 3-manifold may be isotoped to intersect a given collection of essential spheres and discs in a single loop each. We also give a reformulation of Casson and Gordon's theorem on weakly reducible Heegaard splittings, showing that they exhibit additional structure with respect to certain incompressible surfaces. This article could also serve as an introduction to the theory of generalized Heegaard surfaces and it includes a careful study of their behaviour under amalgamation.more » « less
