More Like this

1. The two-phase problem for harmonic measure in VMO and the chord-arc condition

   https://doi.org/10.1090/btran/197  

   Tolsa, Xavier; Toro, Tatiana (November 2024, Transactions of the American Mathematical Society, Series B)

   Let ${\mathrm{\Omega <\#comment/>}}^{+}\subset <\#comment/>{\mathbb{R}}^{n+1}$be a bounded $\mathrm{\delta <\#comment/>}$-Reifenberg flat domain, with $\mathrm{\delta <\#comment/>}>0$small enough, possibly with locally infinite surface measure. Assume also that ${\mathrm{\Omega <\#comment/>}}^{-<\#comment/>}={\mathbb{R}}^{n+1}\setminus <\#comment/>\stackrel{¯<\#comment/>}{{\mathrm{\Omega <\#comment/>}}^{+}}$is an NTA (non-tangentially accessible) domain as well and denote by ${\mathrm{\omega <\#comment/>}}^{+}$and ${\mathrm{\omega <\#comment/>}}^{-<\#comment/>}$the respective harmonic measures of ${\mathrm{\Omega <\#comment/>}}^{+}$and ${\mathrm{\Omega <\#comment/>}}^{-<\#comment/>}$with poles $p^{\pm <\#comment/>}\in <\#comment/>{\mathrm{\Omega <\#comment/>}}^{\pm <\#comment/>}$. In this paper we show that the condition that $\log <\#comment/>\frac{d{\mathrm{\omega <\#comment/>}}^{-<\#comment/>}}{d{\mathrm{\omega <\#comment/>}}^{+}}\in <\#comment/>\mathrm{VMO}<\#comment/>\left({\mathrm{\omega <\#comment/>}}^{+}\right)$is equivalent to ${\mathrm{\Omega <\#comment/>}}^{+}$being a chord-arc domain with inner unit normal belonging to $\mathrm{VMO}<\#comment/>\left({\mathcal{H}}^n{|}_{\mathrm{\partial <\#comment/>}{\mathrm{\Omega <\#comment/>}}^{+}}\right)$. 

   more » « less
2. Tight Bounds for ℓ ₁ Oblivious Subspace Embeddings

   https://doi.org/10.1145/3477537  

   Wang, Ruosong; Woodruff, David P. (January 2022, ACM Transactions on Algorithms)

   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
3. A deterministic near-linear time approximation scheme for geometric transportation

   https://doi.org/10.1109/FOCS57990.2023.00078  

   Fox, Emily; Lu, Jiashuai (November 2023, IEEE)

   Given a set of points $$P = (P^+ \sqcup P^-) \subset \mathbb{R}^d$$ for some constant $$d$$ and a supply function $$\mu:P\to \mathbb{R}$$ such that $$\mu(p) > 0~\forall p \in P^+$$, $$\mu(p) < 0~\forall p \in P^-$$, and $$\sum_{p\in P}{\mu(p)} = 0$$, the geometric transportation problem asks one to find a transportation map $$\tau: P^+\times P^-\to \mathbb{R}_{\ge 0}$$ such that $$\sum_{q\in P^-}{\tau(p, q)} = \mu(p)~\forall p \in P^+$$, $$\sum_{p\in P^+}{\tau(p, q)} = -\mu(q) \forall q \in P^-$$, and the weighted sum of Euclidean distances for the pairs $$\sum_{(p,q)\in P^+\times P^-}\tau(p, q)\cdot ||q-p||_2$$ is minimized. We present the first deterministic algorithm that computes, in near-linear time, a transportation map whose cost is within a $$(1 + \varepsilon)$$ factor of optimal. More precisely, our algorithm runs in $$O(n\varepsilon^{-(d+2)}\log^5{n}\log{\log{n}})$$ time for any constant $$\varepsilon > 0$$. While a randomized $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time algorithm for this problem was discovered in the last few years, all previously known deterministic $$(1 + \varepsilon)$$-approximation algorithms run in~$$\Omega(n^{3/2})$$ time. A similar situation existed for geometric bipartite matching, the special case of geometric transportation where all supplies are unit, until a deterministic $$n\varepsilon^{-O(d)}\log^{O(d)}{n}$$ time $$(1 + \varepsilon)$$-approximation algorithm was presented at STOC 2022. Surprisingly, our result is not only a generalization of the bipartite matching one to arbitrary instances of geometric transportation, but it also reduces the running time for all previously known $$(1 + \varepsilon)$$-approximation algorithms, randomized or deterministic, even for geometric bipartite matching. In particular, we give the first $$(1 + \varepsilon)$$-approximate deterministic algorithm for geometric bipartite matching and the first $$(1 + \varepsilon)$$-approximate deterministic or randomized algorithm for geometric transportation with no dependence on $$d$$ in the exponent of the running time's polylog. As an additional application of our main ideas, we also give the first randomized near-linear $$O(\varepsilon^{-2} m \log^{O(1)} n)$$ time $$(1 + \varepsilon)$$-approximation algorithm for the uncapacitated minimum cost flow (transshipment) problem in undirected graphs with arbitrary \emph{real} edge costs. 

   more » « less
4. Modular invariance in superstring theory from $$ \mathcal{N} $$ = 4 super-Yang-Mills

   https://doi.org/10.1007/JHEP11(2020)016  

   Chester, Shai M.; Green, Michael B.; Pufu, Silviu S.; Wang, Yifan; Wen, Congkao (November 2020, Journal of High Energy Physics)

   A bstract We study the four-point function of the lowest-lying half-BPS operators in the $$ \mathcal{N} $$ N = 4 SU( N ) super-Yang-Mills theory and its relation to the flat-space four-graviton amplitude in type IIB superstring theory. We work in a large- N expansion in which the complexified Yang-Mills coupling τ is fixed. In this expansion, non-perturbative instanton contributions are present, and the SL(2 , ℤ) duality invariance of correlation functions is manifest. Our results are based on a detailed analysis of the sphere partition function of the mass-deformed SYM theory, which was previously computed using supersymmetric localization. This partition function determines a certain integrated correlator in the undeformed $$ \mathcal{N} $$ N = 4 SYM theory, which in turn constrains the four-point correlator at separated points. In a normalization where the two-point functions are proportional to N 2 − 1 and are independent of τ and $$ \overline{\tau} $$ τ ¯ , we find that the terms of order $$ \sqrt{N} $$ N and $$ 1/\sqrt{N} $$ 1 / N in the large N expansion of the four-point correlator are proportional to the non-holomorphic Eisenstein series $$ E\left(\frac{3}{2},\tau, \overline{\tau}\right) $$ E 3 2 τ τ ¯ and $$ E\left(\frac{5}{2},\tau, \overline{\tau}\right) $$ E 5 2 τ τ ¯ , respectively. In the flat space limit, these terms match the corresponding terms in the type IIB S-matrix arising from R 4 and D 4 R 4 contact inter-actions, which, for the R 4 case, represents a check of AdS/CFT at finite string coupling. Furthermore, we present striking evidence that these results generalize so that, at order $$ {N}^{\frac{1}{2}-m} $$ N 1 2 − m with integer m ≥ 0, the expansion of the integrated correlator we study is a linear sum of non-holomorphic Eisenstein series with half-integer index, which are manifestly SL(2 , ℤ) invariant. 

   more » « less
5. A Stronger Lower Bound on Parametric Minimum Spanning Trees

   https://doi.org/10.1007/s00453-022-01024-9  

   Eppstein, David (June 2023, Algorithmica)

   Abstract We prove that, for an undirected graph with n vertices and m edges, each labeled with a linear function of a parameter $$\lambda $$ λ , the number of different minimum spanning trees obtained as the parameter varies can be $$\Omega (m\log n)$$ Ω ( m log n ) . 

   more » « less