An official website of the United States government
We provide a complete picture of the extent to which amplification of success probability is possible for randomized algorithms having access to one NP oracle query, in the settings of two-sided, one-sided, and zero-sided error. We generalize this picture to amplifying one-query algorithms with q-query algorithms, and we show our inclusions are tight for relativizing techniques.
more »
« less
The Elliptic Tail Kernel
Abstract We introduce and study a new family of $$q$$-translation-invariant determinantal point processes on the two-sided $$q$$-lattice. We prove that these processes are limits of the $$q$$–$zw$ measures, which arise in the $$q$$-deformation of harmonic analysis on $$U(\infty )$$, and express their correlation kernels in terms of Jacobi theta functions. As an application, we show that the $$q$$–$zw$ measures are diffuse. Our results also hint at a link between the two-sided $$q$$-lattice and rows/columns of Young diagrams.
more »
« less
- Award ID(s):
- 1949820
- PAR ID:
- 10244227
- Date Published:
- Journal Name:
- International Mathematics Research Notices
- ISSN:
- 1073-7928
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract Let Ω ⊂ ℝ n + 1 {\Omega\subset\mathbb{R}^{n+1}} , n ≥ 2 {n\geq 2} , be a 1-sided non-tangentially accessible domain (aka uniform domain), that is, Ω satisfies the interior Corkscrew and Harnack chain conditions, which are respectively scale-invariant/quantitative versions of openness and path-connectedness. Let us assume also that Ω satisfies the so-called capacity density condition, a quantitative version of the fact that all boundary points are Wiener regular. Consider L 0 u = - div ( A 0 ∇ u ) {L_{0}u=-\mathrm{div}(A_{0}\nabla u)} , L u = - div ( A ∇ u ) {Lu=-\mathrm{div}(A\nabla u)} , two real (non-necessarily symmetric) uniformly elliptic operators in Ω, and write ω L 0 {\omega_{L_{0}}} , ω L {\omega_{L}} for the respective associated elliptic measures. The goal of this program is to find sufficient conditions guaranteeing that ω L {\omega_{L}} satisfies an A ∞ {A_{\infty}} -condition or a RH q {\mathrm{RH}_{q}} -condition with respect to ω L 0 {\omega_{L_{0}}} . In this paper we establish that if the discrepancy of the two matrices satisfies a natural Carleson measure condition with respect to ω L 0 {\omega_{L_{0}}} , then ω L ∈ A ∞ ( ω L 0 ) {\omega_{L}\in A_{\infty}(\omega_{L_{0}})} . Additionally, we can prove that ω L ∈ RH q ( ω L 0 ) {\omega_{L}\in\mathrm{RH}_{q}(\omega_{L_{0}})} for some specific q ∈ ( 1 , ∞ ) {q\in(1,\infty)} , by assuming that such Carleson condition holds with a sufficiently small constant. This “small constant” case extends previous work of Fefferman–Kenig–Pipher and Milakis–Pipher together with the last author of the present paper who considered symmetric operators in Lipschitz and bounded chord-arc domains, respectively. Here we go beyond those settings, our domains satisfy a capacity density condition which is much weaker than the existence of exterior Corkscrew balls. Moreover, their boundaries need not be Ahlfors regular and the restriction of the n -dimensional Hausdorff measure to the boundary could be even locally infinite. The “large constant” case, that is, the one on which we just assume that the discrepancy of the two matrices satisfies a Carleson measure condition, is new even in the case of nice domains (such as the unit ball, the upper-half space, or non-tangentially accessible domains) and in the case of symmetric operators. We emphasize that our results hold in the absence of a nice surface measure: all the analysis is done with the underlying measure ω L 0 {\omega_{L_{0}}} , which behaves well in the scenarios we are considering. When particularized to the setting of Lipschitz, chord-arc, or 1-sided chord-arc domains, our methods allow us to immediately recover a number of existing perturbation results as well as extend some of them.more » « less
-
We investigate positivity and probabilistic properties arising from the Young-Fibonacci lattice $$\mathbb{YF}$$, a 1-differential poset on binary words composed of 1's and 2's (known as Fibonacci words). Building on Okada's theory of clone Schur functions (Trans. Amer. Math. Soc. 346 (1994), 549-568), we introduce clone coherent measures on $$\mathbb{YF}$$ which give rise to random Fibonacci words of increasing length. Unlike coherent systems associated to classical Schur functions on the Young lattice of integer partitions, clone coherent measures are generally not extremal on $$\mathbb{YF}$$. Our first main result is a complete characterization of Fibonacci positive specializations - parameter sequences which yield positive clone Schur functions on $$\mathbb{YF}$$. We connect Fibonacci positivity with total positivity of tridiagonal matrices, Stieltjes moment sequences, and orthogonal polynomials in one variable from the ($$q$$-)Askey scheme. Our second family of results concerns the asymptotic behavior of random Fibonacci words derived from various Fibonacci positive specializations. We analyze several limiting regimes for specific examples, revealing stick-breaking-like processes (connected to GEM distributions), dependent stick-breaking processes of a new type, or discrete limits tied to the Martin boundary of the Young-Fibonacci lattice. Our stick-breaking-like scaling limits significantly extend the result of Gnedin-Kerov (Math. Proc. Camb. Philos. Soc. 129 (2000), no. 3, 433-446) on asymptotics of the Plancherel measure on $$\mathbb{YF}$$. We also establish Cauchy-like identities for clone Schur functions (with the right-hand side given by a quadridiagonal determinant), and construct and analyze models of random permutations and involutions based on Fibonacci positive specializations and a version of the Robinson-Schensted correspondence for $$\mathbb{YF}$$.more » « less
-
Abstract Let Ω ⊂ ℝ n + 1 {\Omega\subset\mathbb{R}^{n+1}} , n ≥ 2 {n\geq 2} , be a 1-sided non-tangentially accessible domain (also known as uniform domain), that is, Ω satisfies the interior Corkscrew and Harnack chain conditions, which are respectively scale-invariant/quantitative versions of openness and path-connectedness. Let us assume also that Ω satisfies the so-called capacity density condition, a quantitative version of the fact that all boundary points are Wiener regular. Consider two real-valued (non-necessarily symmetric) uniformly elliptic operators L 0 u = - div ( A 0 ∇ u ) and L u = - div ( A ∇ u ) L_{0}u=-\operatorname{div}(A_{0}\nabla u)\quad\text{and}\quad Lu=-%\operatorname{div}(A\nabla u) in Ω, and write ω L 0 {\omega_{L_{0}}} and ω L {\omega_{L}} for the respective associated elliptic measures. The goal of this article and its companion[M. Akman, S. Hofmann, J. M. Martell and T. Toro,Perturbation of elliptic operators in 1-sided NTA domains satisfying the capacity density condition,preprint 2021, https://arxiv.org/abs/1901.08261v3 ]is to find sufficient conditions guaranteeing that ω L {\omega_{L}} satisfies an A ∞ {A_{\infty}} -condition or a RH q {\operatorname{RH}_{q}} -condition with respect to ω L 0 {\omega_{L_{0}}} . In this paper, we are interested in obtaininga square function and non-tangential estimates for solutions of operators as before. We establish that bounded weak null-solutions satisfy Carleson measure estimates, with respect to the associated elliptic measure. We also show that for every weak null-solution, the associated square function can be controlled by the non-tangential maximal function in any Lebesgue space with respect to the associated elliptic measure. These results extend previous work ofDahlberg, Jerison and Kenig and are fundamental for the proof of the perturbation results in the paper cited above.more » « less
-
Abstract Let L be a separable quadratic extension of either $${\mathbb {Q}}$$ Q or $${\mathbb {F}}_q(t)$$ F q ( t ) . We exhibit efficient algorithms for finding isomorphisms between quaternion algebras over L . Our techniques are based on computing maximal one-sided ideals of the corestriction of a central simple L -algebra.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1093/imrn/rnaa038
