- Publication Date:
- NSF-PAR ID:
- 10190072
- Journal Name:
- Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms
- Sponsoring Org:
- National Science Foundation
More Like this
-
The cumulative empirical spectral measure (CESM) $\Phi[\mathbf{A}] : \mathbb{R} \to [0,1]$ of a $n\times n$ symmetric matrix $\mathbf{A}$ is defined as the fraction of eigenvalues of $\mathbf{A}$ less than a given threshold, i.e., $\Phi[\mathbf{A}](x) := \sum_{i=1}^{n} \frac{1}{n} {\large\unicode{x1D7D9}}[ \lambda_i[\mathbf{A}]\leq x]$. Spectral sums $\operatorname{tr}(f[\mathbf{A}])$ can be computed as the Riemann–Stieltjes integral of $f$ against $\Phi[\mathbf{A}]$, so the task of estimating CESM arises frequently in a number of applications, including machine learning. We present an error analysis for stochastic Lanczos quadrature (SLQ). We show that SLQ obtains an approximation to the CESM within a Wasserstein distance of $t \: | \lambda_{\text{max}}[\mathbf{A}] - \lambda_{\text{min}}[\mathbf{A}] |$ with probability at least $1-\eta$, by applying the Lanczos algorithm for $\lceil 12 t^{-1} + \frac{1}{2} \rceil$ iterations to $\lceil 4 ( n+2 )^{-1}t^{-2} \ln(2n\eta^{-1}) \rceil$ vectors sampled independently and uniformly from the unit sphere. We additionally provide (matrix-dependent) a posteriori error bounds for the Wasserstein and Kolmogorov–Smirnov distances between the output of this algorithm and the true CESM. The quality of our bounds is demonstrated using numerical experiments.
-
Abstract Given a sequence $\{Z_d\}_{d\in \mathbb{N}}$ of smooth and compact hypersurfaces in ${\mathbb{R}}^{n-1}$, we prove that (up to extracting subsequences) there exists a regular definable hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^n$ such that each manifold $Z_d$ is diffeomorphic to a component of the zero set on $\Gamma$ of some polynomial of degree $d$. (This is in sharp contrast with the case when $\Gamma$ is semialgebraic, where for example the homological complexity of the zero set of a polynomial $p$ on $\Gamma$ is bounded by a polynomial in $\deg (p)$.) More precisely, given the above sequence of hypersurfaces, we construct a regular, compact, semianalytic hypersurface $\Gamma \subset {\mathbb{R}}\textrm{P}^{n}$ containing a subset $D$ homeomorphic to a disk, and a family of polynomials $\{p_m\}_{m\in \mathbb{N}}$ of degree $\deg (p_m)=d_m$ such that $(D, Z(p_m)\cap D)\sim ({\mathbb{R}}^{n-1}, Z_{d_m}),$ i.e. the zero set of $p_m$ in $D$ is isotopic to $Z_{d_m}$ in ${\mathbb{R}}^{n-1}$. This says that, up to extracting subsequences, the intersection of $\Gamma$ with a hypersurface of degree $d$ can be as complicated as we want. We call these ‘pathological examples’. In particular, we show that for every $0 \leq k \leq n-2$ and every sequence of natural numbers $a=\{a_d\}_{d\in \mathbb{N}}$ there is a regular, compact semianalyticmore »
-
The densest subgraph problem in a graph (\dsg), in the simplest form, is the following. Given an undirected graph $G=(V,E)$ find a subset $S \subseteq V$ of vertices that maximizes the ratio $|E(S)|/|S|$ where $E(S)$ is the set of edges with both endpoints in $S$. \dsg and several of its variants are well-studied in theory and practice and have many applications in data mining and network analysis. In this paper we study fast algorithms and structural aspects of \dsg via the lens of \emph{supermodularity}. For this we consider the densest supermodular subset problem (\dssp): given a non-negative supermodular function $f: 2^V \rightarrow \mathbb{R}_+$, maximize $f(S)/|S|$. For \dsg we describe a simple flow-based algorithm that outputs a $(1-\eps)$-approximation in deterministic $\tilde{O}(m/\eps)$ time where $m$ is the number of edges. Our algorithm is the first to have a near-linear dependence on $m$ and $1/\eps$ and improves previous methods based on an LP relaxation. It generalizes to hypergraphs, and also yields a faster algorithm for directed \dsg. Greedy peeling algorithms have been very popular for \dsg and several variants due to their efficiency, empirical performance, and worst-case approximation guarantees. We describe a simple peeling algorithm for \dssp and analyze its approximation guarantee inmore »
-
Abstract In this paper, we consider discrete Schrödinger operators of the form, $$\begin{equation*} (Hu)(n) = u({n+1})+u({n-1})+V(n)u(n). \end{equation*}$$We view $H$ as a perturbation of the free operator $H_0$, where $(H_0u)(n)= u({n+1})+u({n-1})$. For $H_0$ (no perturbation), $\sigma _{\textrm{ess}}(H_0)=\sigma _{\textrm{ac}}(H)=[-2,2]$ and $H_0$ does not have eigenvalues embedded into $(-2,2)$. It is an interesting and important problem to identify the perturbation such that the operator $H_0+V$ has one eigenvalue (finitely many eigenvalues or countable eigenvalues) embedded into $(-2,2)$. We introduce the almost sign type potentials and develop the Prüfer transformation to address this problem, which leads to the following five results. 1: We obtain the sharp spectral transition for the existence of irrational type eigenvalues or rational type eigenvalues with even denominators.2: Suppose $\limsup _{n\to \infty } n|V(n)|=a<\infty .$ We obtain a lower/upper bound of $a$ such that $H_0+V$ has one rational type eigenvalue with odd denominator.3: We obtain the asymptotical behavior of embedded eigenvalues around the boundaries of $(-2,2)$.4: Given any finite set of points $\{ E_j\}_{j=1}^N$ in $(-2,2)$ with $0\notin \{ E_j\}_{j=1}^N+\{ E_j\}_{j=1}^N$, we construct the explicit potential $V(n)=\frac{O(1)}{1+|n|}$ such that $H=H_0+V$ has eigenvalues $\{ E_j\}_{j=1}^N$.5: Given any countable set of points $\{ E_j\}$ in $(-2,2)$ with $0\notin \{ E_j\}+\{ E_j\}$, andmore »
-
Abstract Let $f(z) = \sum_{n=1}^\infty a_f(n)q^n$ be a holomorphic cuspidal newform with even integral weight $k\geq 2$, level N, trivial nebentypus and no complex multiplication. For all primes p, we may define $\theta_p\in [0,\pi]$ such that $a_f(p) = 2p^{(k-1)/2}\cos \theta_p$. The Sato–Tate conjecture states that the angles θp are equidistributed with respect to the probability measure $\mu_{\textrm{ST}}(I) = \frac{2}{\pi}\int_I \sin^2 \theta \; d\theta$, where $I\subseteq [0,\pi]$. Using recent results on the automorphy of symmetric power L-functions due to Newton and Thorne, we explicitly bound the error term in the Sato–Tate conjecture when f corresponds to an elliptic curve over $\mathbb{Q}$ of arbitrary conductor or when f has square-free level. In these cases, if $\pi_{f,I}(x) := \#\{p \leq x : p \nmid N, \theta_p\in I\}$ and $\pi(x) := \# \{p \leq x \}$, we prove the following bound: $$ \left| \frac{\pi_{f,I}(x)}{\pi(x)} - \mu_{\textrm{ST}}(I)\right| \leq 58.1\frac{\log((k-1)N \log{x})}{\sqrt{\log{x}}} \qquad \text{for} \quad x \geq 3. $$ As an application, we give an explicit bound for the number of primes up to x that violate the Atkin–Serre conjecture for f.