More Like this

1. Sketching, Moment Estimation, and the Lévy-Khintchine Representation Theorem

   https://doi.org/10.4230/lipics.itcs.2025.77  

   Pettie, Seth; Wang, Dingyu (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Meka, Raghu (Ed.)

   In the d-dimensional turnstile streaming model, a frequency vector 𝐱 = (𝐱(1),…,𝐱(n)) ∈ (ℝ^d)ⁿ is updated entry-wisely over a stream. We consider the problem of f-moment estimation for which one wants to estimate f(𝐱)=∑_{v ∈ [n]}f(𝐱(v)) with a small-space sketch. A function f is tractable if the f-moment can be estimated to within a constant factor using polylog(n) space. The f-moment estimation problem has been intensively studied in the d = 1 case. Flajolet and Martin estimate the F₀-moment (f(x) = 1 (x > 0), incremental stream); Alon, Matias, and Szegedy estimate the L₂-moment (f(x) = x²); Indyk estimates the L_α-moment (f(x) = |x|^α), α ∈ (0,2]. For d ≥ 2, Ganguly, Bansal, and Dube estimate the L_{p,q} hybrid moment (f:ℝ^d → ℝ,f(x) = (∑_{j = 1}^d |x_j|^p)^q), p ∈ (0,2],q ∈ (0,1). For tractability, Bar-Yossef, Jayram, Kumar, and Sivakumar show that f(x) = |x|^α is not tractable for α > 2. Braverman, Chestnut, Woodruff, and Yang characterize the class of tractable one-variable functions except for a class of nearly periodic functions. In this work we present a simple and generic scheme to construct sketches with the novel idea of hashing indices to Lévy processes, from which one can estimate the f-moment f(𝐱) where f is the characteristic exponent of the Lévy process. The fundamental Lévy-Khintchine representation theorem completely characterizes the space of all possible characteristic exponents, which in turn characterizes the set of f-moments that can be estimated by this generic scheme. The new scheme has strong explanatory power. It unifies the construction of many existing sketches (F₀, L₀, L₂, L_α, L_{p,q}, etc.) and it implies the tractability of many nearly periodic functions that were previously unclassified. Furthermore, the scheme can be conveniently generalized to multidimensional cases (d ≥ 2) by considering multidimensional Lévy processes and can be further generalized to estimate heterogeneous moments by projecting different indices with different Lévy processes. We conjecture that the set of tractable functions can be characterized using the Lévy-Khintchine representation theorem via what we called the Fourier-Hahn-Lévy method. 

   more » « less
2. Degenerate linear parabolic equations in divergence form on the upper half space

   https://doi.org/10.1090/tran/8892  

   Dong, Hongjie; Phan, Tuoc; Tran, Hung (June 2023, Transactions of the American Mathematical Society)

   We study a class of second-order degenerate linear parabolic equations in divergence form in ( − ∞ , T ) × R + d (-\infty , T) \times {\mathbb {R}}^d_+ with homogeneous Dirichlet boundary condition on ( − ∞ , T ) × ∂ R + d (-\infty , T) \times \partial {\mathbb {R}}^d_+ , where R + d = { x ∈ R d : x d > 0 } {\mathbb {R}}^d_+ = \{x \in {\mathbb {R}}^d: x_d>0\} and T ∈ ( − ∞ , ∞ ] T\in {(-\infty , \infty ]} is given. The coefficient matrices of the equations are the product of μ ( x d ) \mu (x_d) and bounded uniformly elliptic matrices, where μ ( x d ) \mu (x_d) behaves like x d α x_d^\alpha for some given α ∈ ( 0 , 2 ) \alpha \in (0,2) , which are degenerate on the boundary { x d = 0 } \{x_d=0\} of the domain. Our main motivation comes from the analysis of degenerate viscous Hamilton-Jacobi equations. Under a partially VMO assumption on the coefficients, we obtain the well-posedness and regularity of solutions in weighted Sobolev spaces. Our results can be readily extended to systems. 

   more » « less
3. On the three ball theorem for solutions of the Helmholtz equation

   https://doi.org/10.1007/s40627-021-00070-3  

   Berge, Stine Marie; Malinnikova, Eugenia (June 2021, Complex Analysis and its Synergies)

   null (Ed.)

   Abstract Let $$u_{k}$$ u k be a solution of the Helmholtz equation with the wave number k , $$\varDelta u_{k}+k^{2} u_{k}=0$$ Δ u k + k 2 u k = 0 , on (a small ball in) either $${\mathbb {R}}^{n}$$ R n , $${\mathbb {S}}^{n}$$ S n , or $${\mathbb {H}}^{n}$$ H n . For a fixed point p , we define $$M_{u_{k}}(r)=\max _{d(x,p)\le r}|u_{k}(x)|.$$ M u k ( r ) = max d ( x , p ) ≤ r | u k ( x ) | . The following three ball inequality $$M_{u_{k}}(2r)\le C(k,r,\alpha )M_{u_{k}}(r)^{\alpha }M_{u_{k}}(4r)^{1-\alpha }$$ M u k ( 2 r ) ≤ C ( k , r , α ) M u k ( r ) α M u k ( 4 r ) 1 - α is well known, it holds for some $$\alpha \in (0,1)$$ α ∈ ( 0 , 1 ) and $$C(k,r,\alpha )>0$$ C ( k , r , α ) > 0 independent of $$u_{k}$$ u k . We show that the constant $$C(k,r,\alpha )$$ C ( k , r , α ) grows exponentially in k (when r is fixed and small). We also compare our result with the increased stability for solutions of the Cauchy problem for the Helmholtz equation on Riemannian manifolds. 

   more » « less
4. On regularity of \overline∂-solutions on 𝑎_{𝑞} domains with 𝐶² boundary in complex manifolds

   https://doi.org/10.1090/tran/9315  

   Gong, Xianghong (March 2025, Transactions of the American Mathematical Society)

   We study regularity of solutions $u$to $\stackrel{¯<\#comment/>}{\mathrm{\partial <\#comment/>}}u=f$on a relatively compact $C^2$domain $D$in a complex manifold of dimension $n$, where $f$is a $(0,q)$form. Assume that there are either $(q+1)$negative or $(n-<\#comment/>q)$positive Levi eigenvalues at each point of boundary $\mathrm{\partial <\#comment/>}D$. Under the necessary condition that a locally $L^2$solution exists on the domain, we show the existence of the solutions on the closure of the domain that gain $1/2$derivative when $q=1$and $f$is in the Hölder–Zygmund space ${\mathrm{\Lambda <\#comment/>}}^r\left(D\right)$with $r>1$. For $q>1$, the same regularity for the solutions is achieved when $\mathrm{\partial <\#comment/>}D$is either sufficiently smooth or of $(n-<\#comment/>q)$positive Levi eigenvalues everywhere on $\mathrm{\partial <\#comment/>}D$. 

   more » « less
5. Deep Network With Approximation Error Being Reciprocal of Width to Power of Square Root of Depth

   https://doi.org/10.1162/neco_a_01364  

   Shen, Zuowei; Yang, Haizhao; Zhang, Shijun (January 2021, Neural Computation)

   null (Ed.)

   A new network with super-approximation power is introduced. This network is built with Floor (⌊x⌋) or ReLU (max{0,x}) activation function in each neuron; hence, we call such networks Floor-ReLU networks. For any hyperparameters N∈N+ and L∈N+, we show that Floor-ReLU networks with width max{d,5N+13} and depth 64dL+3 can uniformly approximate a Hölder function f on [0,1]d with an approximation error 3λdα/2N-αL, where α∈(0,1] and λ are the Hölder order and constant, respectively. More generally for an arbitrary continuous function f on [0,1]d with a modulus of continuity ωf(·), the constructive approximation rate is ωf(dN-L)+2ωf(d)N-L. As a consequence, this new class of networks overcomes the curse of dimensionality in approximation power when the variation of ωf(r) as r→0 is moderate (e.g., ωf(r)≲rα for Hölder continuous functions), since the major term to be considered in our approximation rate is essentially d times a function of N and L independent of d within the modulus of continuity. 

   more » « less