An official website of the United States government
An \ell _p oblivious subspace embedding is a distribution over r \times n matrices \Pi such that for any fixed n \times d matrix A , \[ \Pr _{\Pi }[\textrm {for all }x, \ \Vert Ax\Vert _p \le \Vert \Pi Ax\Vert _p \le \kappa \Vert Ax\Vert _p] \ge 9/10,\] where r is the dimension of the embedding, \kappa is the distortion of the embedding, and for an n -dimensional vector y , \Vert y\Vert _p = (\sum _{i=1}^n |y_i|^p)^{1/p} is the \ell _p -norm. Another important property is the sparsity of \Pi , that is, the maximum number of non-zero entries per column, as this determines the running time of computing \Pi A . While for p = 2 there are nearly optimal tradeoffs in terms of the dimension, distortion, and sparsity, for the important case of 1 \le p \lt 2 , much less was known. In this article, we obtain nearly optimal tradeoffs for \ell _1 oblivious subspace embeddings, as well as new tradeoffs for 1 \lt p \lt 2 . Our main results are as follows: (1) We show for every 1 \le p \lt 2 , any oblivious subspace embedding with dimension r has distortion \[ \kappa = \Omega \left(\frac{1}{\left(\frac{1}{d}\right)^{1 / p} \log ^{2 / p}r + \left(\frac{r}{n}\right)^{1 / p - 1 / 2}}\right).\] When r = {\operatorname{poly}}(d) \ll n in applications, this gives a \kappa = \Omega (d^{1/p}\log ^{-2/p} d) lower bound, and shows the oblivious subspace embedding of Sohler and Woodruff (STOC, 2011) for p = 1 is optimal up to {\operatorname{poly}}(\log (d)) factors. (2) We give sparse oblivious subspace embeddings for every 1 \le p \lt 2 . Importantly, for p = 1 , we achieve r = O(d \log d) , \kappa = O(d \log d) and s = O(\log d) non-zero entries per column. The best previous construction with s \le {\operatorname{poly}}(\log d) is due to Woodruff and Zhang (COLT, 2013), giving \kappa = \Omega (d^2 {\operatorname{poly}}(\log d)) or \kappa = \Omega (d^{3/2} \sqrt {\log n} \cdot {\operatorname{poly}}(\log d)) and r \ge d \cdot {\operatorname{poly}}(\log d) ; in contrast our r = O(d \log d) and \kappa = O(d \log d) are optimal up to {\operatorname{poly}}(\log (d)) factors even for dense matrices. We also give (1) \ell _p oblivious subspace embeddings with an expected 1+\varepsilon number of non-zero entries per column for arbitrarily small \varepsilon \gt 0 , and (2) the first oblivious subspace embeddings for 1 \le p \lt 2 with O(1) -distortion and dimension independent of n . Oblivious subspace embeddings are crucial for distributed and streaming environments, as well as entrywise \ell _p low-rank approximation. Our results give improved algorithms for these applications.
more »
« less
This content will become publicly available on April 1, 2026
On the Automorphism Groups of Hyperbolic Manifolds
Abstract Let $${\mathrm{Diff}}_{0}(N)$$ represent the subgroup of diffeomorphisms that are homotopic to the identity. We show that if $$N$$ is a closed hyperbolic 4-manifold, then $$\pi _{0}{\mathrm{Diff}}_{0}(N)$$ is not finitely generated with similar results holding topologically. This proves in dimension-4 results previously known for $$n$$-dimensional hyperbolic manifolds of dimension $$n\ge 11$$ by Farrell and Jones in 1989 and $$n\ge 10$$ by Farrell and Ontaneda in 2010. Our proof relies on the technical result that $$\pi _{0}{\mathrm{Homeo}}(S^{1}\times D^{3})$$ is not finitely generated, which extends to the topological category smooth results of the authors. We also show that $$\pi _{n-4} {\mathrm{Homeo}}(S^{1} \times D^{n-1})$$ is not finitely generated for $$n \geq 4$$ and in particular $$\pi _{0}{\mathrm{Homeo}}(S^{1}\times D^{3})$$ is not finitely generated. These results are new for $n=4, 5$ and $$7$$. We also introduce higher dimensional barbell maps and establish some of their basic properties.
more »
« less
- Award ID(s):
- 2304841
- PAR ID:
- 10582392
- Publisher / Repository:
- Oxford Academic
- Date Published:
- Journal Name:
- International Mathematics Research Notices
- Volume:
- 2025
- Issue:
- 7
- ISSN:
- 1073-7928
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
This work concerns a map φ : R → S \varphi \colon R\to S of commutative noetherian rings, locally of finite flat dimension. It is proved that the André-Quillen homology functors are rigid, namely, if D n ( S / R ; − ) = 0 \mathrm {D}_n(S/R;-)=0 for some n ≥ 1 n\ge 1 , then D i ( S / R ; − ) = 0 \mathrm {D}_i(S/R;-)=0 for all i ≥ 2 i\ge 2 and φ {\varphi } is locally complete intersection. This extends Avramov’s theorem that draws the same conclusion assuming D n ( S / R ; − ) \mathrm {D}_n(S/R;-) vanishes for all n ≫ 0 n\gg 0 , confirming a conjecture of Quillen. The rigidity of André-Quillen functors is deduced from a more general result about the higher cotangent modules which answers a question raised by Avramov and Herzog, and subsumes a conjecture of Vasconcelos that was proved recently by the first author. The new insight leading to these results concerns the equivariance of a map from André-Quillen cohomology to Hochschild cohomology defined using the universal Atiyah class of φ \varphi .more » « less
-
A bstract We measure the branching fractions and CP asymmetries for the singly Cabibbo-suppressed decays D 0 → π + π − η , D 0 → K + K − η , and D 0 → ϕη , using 980 fb − 1 of data from the Belle experiment at the KEKB e + e − collider. We obtain $$ {\displaystyle \begin{array}{c}\mathcal{B}\left({D}^0\to {\pi}^{+}{\pi}^{-}\eta \right)=\left[1.22\pm 0.02\left(\mathrm{stat}\right)\pm 0.02\left(\mathrm{syst}\right)\pm 0.03\left({\mathcal{B}}_{\mathrm{ref}}\right)\right]\times {10}^{-3},\\ {}\mathcal{B}\left({D}^0\to {K}^{+}{K}^{-}\eta \right)=\left[{1.80}_{-0.06}^{+0.07}\left(\mathrm{stat}\right)\pm 0.04\left(\mathrm{syst}\right)\pm 0.05\left({\mathcal{B}}_{\mathrm{ref}}\right)\right]\times {10}^{-4},\\ {}\mathcal{B}\left({D}^0\to \phi \eta \right)=\left[1.84\pm 0.09\left(\mathrm{stat}\right)\pm 0.06\left(\mathrm{syst}\right)\pm 0.05\left({\mathcal{B}}_{\mathrm{ref}}\right)\right]\times {10}^{-4},\end{array}} $$ B D 0 → π + π − η = 1.22 ± 0.02 stat ± 0.02 syst ± 0.03 B ref × 10 − 3 , B D 0 → K + K − η = 1.80 − 0.06 + 0.07 stat ± 0.04 syst ± 0.05 B ref × 10 − 4 , B D 0 → ϕη = 1.84 ± 0.09 stat ± 0.06 syst ± 0.05 B ref × 10 − 4 , where the third uncertainty ( $$ \mathcal{B} $$ B ref ) is from the uncertainty in the branching fraction of the reference mode D 0 → K − π + η . The color-suppressed decay D 0 → ϕη is observed for the first time, with very high significance. The results for the CP asymmetries are $$ {\displaystyle \begin{array}{c}{A}_{CP}\left({D}^0\ {\pi}^{+}{\pi}^{-}\eta \right)=\left[0.9\pm 1.2\left(\mathrm{stat}\right)\pm 0.5\left(\mathrm{syst}\right)\right]\%,\\ {}{A}_{CP}\left({D}^0\to {K}^{+}{K}^{-}\eta \right)=\left[-1.4\pm 3.3\left(\mathrm{stat}\right)\pm 1.1\left(\mathrm{syst}\right)\right]\%,\\ {} ACP\ \left({D}^0\to \phi \eta \right)=\left[-1.9\pm 4.4\left(\mathrm{stat}\right)\pm 0.6\left(\mathrm{syst}\right)\right]\%.\end{array}} $$ A CP D 0 π + π − η = 0.9 ± 1.2 stat ± 0.5 syst % , A CP D 0 → K + K − η = − 1.4 ± 3.3 stat ± 1.1 syst % , ACP D 0 → ϕη = − 1.9 ± 4.4 stat ± 0.6 syst % . The results for D 0 → π + π − η are a significant improvement over previous results. The branching fraction and A CP results for D 0 → K + K − η , and the ACP result for D 0 → ϕη , are the first such measurements. No evidence for CP violation is found in any of these decays.more » « less
-
The proof of Witten's finiteness conjecture established that the Kauffman bracket skein modules of closed $$3$$-manifolds are finitely generated over $$\Q(A)$$. In this paper, we develop a novel method for computing these skein modules. We show that if the skein module $$S(M,\Q[A^\pmo])$$ of $$M$$ is tame (e.g. finitely generated over $$\Q[A^{\pm 1}]$$), and the $$SL(2, \C)$$-character scheme is reduced, then the dimension $$\dim_{\Q(A)}\, S(M, \Q(A))$$ is the number of closed points in this character scheme. This, in particular, verifies a conjecture in the literature relating $$\dim_{\Q(A)}\, S(M, \Q(A))$$ to the Abouzaid-Manolescu $$SL(2,\C)$$-Floer theoretic invariants, for infinite families of 3-manifolds. We prove a criterion for reducedness of character varieties of closed $$3$$-manifolds and use it to compute the skein modules of Dehn fillings of $(2,2n+1)$-torus knots and of the figure-eight knot. The later family gives the first instance of computations of skein modules for closed hyperbolic 3-manifolds. We also prove that the skein modules of rational homology spheres have dimension at least $$1$$ over $$\Q(A)$$.more » « less
-
null (Ed.)Abstract The elliptic algebras in the title are connected graded $$\mathbb {C}$$ -algebras, denoted $$Q_{n,k}(E,\tau )$$ , depending on a pair of relatively prime integers $$n>k\ge 1$$ , an elliptic curve E and a point $$\tau \in E$$ . This paper examines a canonical homomorphism from $$Q_{n,k}(E,\tau )$$ to the twisted homogeneous coordinate ring $$B(X_{n/k},\sigma ',\mathcal {L}^{\prime }_{n/k})$$ on the characteristic variety $$X_{n/k}$$ for $$Q_{n,k}(E,\tau )$$ . When $$X_{n/k}$$ is isomorphic to $E^g$ or the symmetric power $S^gE$ , we show that the homomorphism $$Q_{n,k}(E,\tau ) \to B(X_{n/k},\sigma ',\mathcal {L}^{\prime }_{n/k})$$ is surjective, the relations for $$B(X_{n/k},\sigma ',\mathcal {L}^{\prime }_{n/k})$$ are generated in degrees $$\le 3$$ and the noncommutative scheme $$\mathrm {Proj}_{nc}(Q_{n,k}(E,\tau ))$$ has a closed subvariety that is isomorphic to $E^g$ or $S^gE$ , respectively. When $$X_{n/k}=E^g$$ and $$\tau =0$$ , the results about $$B(X_{n/k},\sigma ',\mathcal {L}^{\prime }_{n/k})$$ show that the morphism $$\Phi _{|\mathcal {L}_{n/k}|}:E^g \to \mathbb {P}^{n-1}$$ embeds $E^g$ as a projectively normal subvariety that is a scheme-theoretic intersection of quadric and cubic hypersurfaces.more » « less
