More Like this

1. The Dimension of Divisibility Orders and Multiset Posets

   https://doi.org/10.1007/s11083-023-09653-7  

   Haiman, Milan ( November 2023 , Order)

   The Dushnik–Miller dimension of a posetPis the leastdfor whichPcan be embedded into a product ofdchains. Lewis and Souza isibility order on the interval of integers$$[N/\kappa , N]$$$[N/\kappa ,N]$is bounded above by$$\kappa (\log \kappa )^{1+o(1)}$$$\kappa {(log\kappa )}^{1+o\left(1\right)}$and below by$$\Omega ((\log \kappa /\log \log \kappa )^2)$$$\Omega \left({(log\kappa /loglog\kappa )}^2\right)$. We improve the upper bound to$$O((\log \kappa )^3/(\log \log \kappa )^2).$$$O({(log\kappa )}^3/{(loglog\kappa )}^2).$We deduce this bound from a more general result on posets of multisets ordered by inclusion. We also consider other divisibility orders and give a bound for polynomials ordered by divisibility.

    

   more » « less
2. Hermitian–Yang–Mills Connections on Collapsing Elliptically Fibered K3 Surfaces

   https://doi.org/10.1007/s12220-021-00808-9  

   Datar, Ved ; Jacob, Adam ( January 2022 , The Journal of Geometric Analysis)

   Let$$X\rightarrow {{\mathbb {P}}}^1$$$X\to P^1$be an elliptically fiberedK3 surface, admitting a sequence$$\omega _{i}$$${\omega }_i$of Ricci-flat metrics collapsing the fibers. LetVbe a holomorphicSU(n) bundle overX, stable with respect to$$\omega _i$$${\omega }_i$. Given the corresponding sequence$$\Xi _i$$${\Xi }_i$of Hermitian–Yang–Mills connections onV, we prove that, ifEis a generic fiber, the restricted sequence$$\Xi _i|_{E}$$${\Xi }_i{|}_E$converges to a flat connection$$A_0$$$A_0$. Furthermore, if the restriction$$V|_E$$${V|}_E$is of the form$$\oplus _{j=1}^n{\mathcal {O}}_E(q_j-0)$$${\oplus }_{j=1}^n{O}_E(q_j-0)$forndistinct points$$q_j\in E$$$q_j\in E$, then these points uniquely determine$$A_0$$$A_0$.

    

   more » « less
3. Limitations of the Impagliazzo–Nisan–Wigderson Pseudorandom Generator Against Permutation Branching Programs

   https://doi.org/10.1007/s00453-024-01251-2  

   Hoza, William_M ; Pyne, Edward ; Vadhan, Salil ( July 2024 , Algorithmica)

   The classic Impagliazzo–Nisan–Wigderson (INW) pseudorandom generator (PRG) (STOC ‘94) for space-bounded computation uses a seed of length$$O(\log n \cdot \log (nw/\varepsilon )+\log d)$$$O(logn·log(nw/\epsilon )+logd)$to fool ordered branching programs of lengthn, widthw, and alphabet sizedto within error$$\varepsilon $$$\epsilon$. A series of works have shown that the analysis of the INW generator can be improved for the class ofpermutationbranching programs or the more generalregularbranching programs, improving the$$O(\log ^2 n)$$$O\left({log}^{2}n\right)$dependence on the lengthnto$$O(\log n)$$$O(logn)$or$${\tilde{O}}(\log n)$$$\tilde{O}(logn)$. However, when also considering the dependence on the other parameters, these analyses still fall short of the optimal PRG seed length$$O(\log (nwd/\varepsilon ))$$$O(log(nwd/\epsilon \left)\right)$. In this paper, we prove that any “spectral analysis” of the INW generator requires seed length$$\begin{aligned} \Omega \left( \log n\cdot \log \log \left( \min \{n,d\}\right) +\log n\cdot \log \left( w/\varepsilon \right) +\log d\right) \end{aligned}$$$\begin{array}{c}\Omega \left(log,n,·,log,log,\left(min,\{,n,,,d,\}\right),+,log,n,·,log,\left(w,/,\epsilon \right),+,log,d\right)\end{array}$to fool ordered permutation branching programs of lengthn, widthw, and alphabet sizedto within error$$\varepsilon $$$\epsilon$. By “spectral analysis” we mean an analysis of the INW generator that relies only on the spectral expansion of the graphs used to construct the generator; this encompasses all prior analyses of the INW generator. Our lower bound matches the upper bound of Braverman–Rao–Raz–Yehudayoff (FOCS 2010, SICOMP 2014) for regular branching programs of alphabet size$$d=2$$$d=2$except for a gap between their$$O\left( \log n \cdot \log \log n\right) $$$O\left(log,n,·,log,log,n\right)$term and our$$\Omega \left( \log n \cdot \log \log \min \{n,d\}\right) $$$\Omega \left(log,n,·,log,log,min,\{,n,,,d,\}\right)$term. It also matches the upper bounds of Koucký–Nimbhorkar–Pudlák (STOC 2011), De (CCC 2011), and Steinke (ECCC 2012) for constant-width ($$w=O(1)$$$w=O\left(1\right)$) permutation branching programs of alphabet size$$d=2$$$d=2$to within a constant factor. To fool permutation branching programs in the measure ofspectral norm, we prove that any spectral analysis of the INW generator requires a seed of length$$\Omega \left( \log n\cdot \log \log n+\log n\cdot \log (1/\varepsilon )\right) $$$\Omega \left(log,n,·,log,log,n,+,log,n,·,log,(,1,/,\epsilon ,)\right)$when the width is at least polynomial inn($$w=n^{\Omega (1)}$$$w=n^{\Omega \left(1\right)}$), matching the recent upper bound of Hoza–Pyne–Vadhan (ITCS 2021) to within a constant factor.

    

   more » « less
4. On a Traveling Salesman Problem for Points in the Unit Cube

   https://doi.org/10.1007/s00453-024-01257-w  

   Balogh, József ; Clemen, Felix Christian ; Dumitrescu, Adrian ( September 2024 , Algorithmica)

   LetXbe ann-element point set in thek-dimensional unit cube$$[0,1]^k$$${[0,1]}^k$where$$k \ge 2$$$k\ge 2$. According to an old result of Bollobás and Meir (Oper Res Lett 11:19–21, 1992) , there exists a cycle (tour)$$x_1, x_2, \ldots , x_n$$$x_1,x_2,\dots ,x_n$through thenpoints, such that$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} \le c_k$$${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}\le c_k$, where$$|x-y|$$$|x-y|$is the Euclidean distance betweenxandy, and$$c_k$$$c_k$is an absolute constant that depends only onk, where$$x_{n+1} \equiv x_1$$$x_{n+1}\equiv x_1$. From the other direction, for every$$k \ge 2$$$k\ge 2$and$$n \ge 2$$$n\ge 2$, there existnpoints in$$[0,1]^k$$${[0,1]}^k$, such that their shortest tour satisfies$$\left( \sum _{i=1}^n |x_i - x_{i+1}|^k \right) ^{1/k} = 2^{1/k} \cdot \sqrt{k}$$${\left({\sum }_{i=1}^n,{|x_i-x_{i+1}|}^k\right)}^{1/k}=2^{1/k}·\sqrt{k}$. For the plane, the best constant is$$c_2=2$$$c_2=2$and this is the only exact value known. Bollobás and Meir showed that one can take$$c_k = 9 \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$$c_k=9{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$for every$$k \ge 3$$$k\ge 3$and conjectured that the best constant is$$c_k = 2^{1/k} \cdot \sqrt{k}$$$c_k=2^{1/k}·\sqrt{k}$, for every$$k \ge 2$$$k\ge 2$. Here we significantly improve the upper bound and show that one can take$$c_k = 3 \sqrt{5} \left( \frac{2}{3} \right) ^{1/k} \cdot \sqrt{k}$$$c_k=3\sqrt{5}{\left(\frac{2}{3}\right)}^{1/k}·\sqrt{k}$or$$c_k = 2.91 \sqrt{k} \ (1+o_k(1))$$$c_k=2.91\sqrt{k}(1+o_k\left(1\right))$. Our bounds are constructive. We also show that$$c_3 \ge 2^{7/6}$$$c_3\ge 2^{7/6}$, which disproves the conjecture for$$k=3$$$k=3$. Connections to matching problems, power assignment problems, related problems, including algorithms, are discussed in this context. A slightly revised version of the Bollobás–Meir conjecture is proposed.

    

   more » « less
5. Green function estimates on complements of low-dimensional uniformly rectifiable sets

   https://doi.org/10.1007/s00208-022-02379-8  

   David, Guy ; Feneuil, Joseph ; Mayboroda, Svitlana ( March 2022 , Mathematische Annalen)

   It has been recently established in David and Mayboroda (Approximation of green functions and domains with uniformly rectifiable boundaries of all dimensions.arXiv:2010.09793) that on uniformly rectifiable sets the Green function is almost affine in the weak sense, and moreover, in some scenarios such Green function estimates are equivalent to the uniform rectifiability of a set. The present paper tackles a strong analogue of these results, starting with the “flagship degenerate operators on sets with lower dimensional boundaries. We consider the elliptic operators$$L_{\beta ,\gamma } =- {\text {div}}D^{d+1+\gamma -n} \nabla $$$L_{\beta ,\gamma }=-\text{div}{D}^{d+1+\gamma -n}\nabla$associated to a domain$$\Omega \subset {\mathbb {R}}^n$$$\Omega \subset R^n$with a uniformly rectifiable boundary$$\Gamma $$$\Gamma$of dimension$$d < n-1$$$d<n-1$, the now usual distance to the boundary$$D = D_\beta $$$D=D_{\beta }$given by$$D_\beta (X)^{-\beta } = \int _{\Gamma } |X-y|^{-d-\beta } d\sigma (y)$$$D_{\beta }{\left(X\right)}^{-\beta }={\int }_{\Gamma }{|X-y|}^{-d-\beta }d\sigma \left(y\right)$for$$X \in \Omega $$$X\in \Omega$, where$$\beta >0$$$\beta >0$and$$\gamma \in (-1,1)$$$\gamma \in (-1,1)$. In this paper we show that the Green functionGfor$$L_{\beta ,\gamma }$$$L_{\beta ,\gamma }$, with pole at infinity, is well approximated by multiples of$$D^{1-\gamma }$$$D^{1-\gamma }$, in the sense that the function$$\big | D\nabla \big (\ln \big ( \frac{G}{D^{1-\gamma }} \big )\big )\big |^2$$$|D\nabla (ln(\frac{G}{D^{1-\gamma }})){|}^2$satisfies a Carleson measure estimate on$$\Omega $$$\Omega$. We underline that the strong and the weak results are different in nature and, of course, at the level of the proofs: the latter extensively used compactness arguments, while the present paper relies on some intricate integration by parts and the properties of the “magical distance function from David et al. (Duke Math J, to appear).

    

   more » « less