More Like this

1. 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)

   Abstract 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
2. Multipliers on bi-parameter Haar system Hardy spaces

   https://doi.org/10.1007/s00208-024-02887-9  

   Lechner, R.; Motakis, P.; Müller, P_F_X; Schlumprecht, Th (May 2024, Mathematische Annalen)

   Abstract Let$$(h_I)$$ $\left(h_I\right)$denote the standard Haar system on [0, 1], indexed by$$I\in \mathcal {D}$$ $I\in D$, the set of dyadic intervals and$$h_I\otimes h_J$$ $h_I\otimes h_J$denote the tensor product$$(s,t)\mapsto h_I(s) h_J(t)$$ $(s,t)\mapsto h_I\left(s\right)h_J\left(t\right)$,$$I,J\in \mathcal {D}$$ $I,J\in D$. We consider a class of two-parameter function spaces which are completions of the linear span$$\mathcal {V}(\delta ^2)$$ $V\left({\delta }^2\right)$of$$h_I\otimes h_J$$ $h_I\otimes h_J$,$$I,J\in \mathcal {D}$$ $I,J\in D$. This class contains all the spaces of the formX(Y), whereXandYare either the Lebesgue spaces$$L^p[0,1]$$ $L^p[0,1]$or the Hardy spaces$$H^p[0,1]$$ $H^p[0,1]$,$$1\le p < \infty $$ $1\le p<\infty$. We say that$$D:X(Y)\rightarrow X(Y)$$ $D:X\left(Y\right)\to X\left(Y\right)$is a Haar multiplier if$$D(h_I\otimes h_J) = d_{I,J} h_I\otimes h_J$$ $D(h_I\otimes h_J)=d_{I,J}{h}_I\otimes h_J$, where$$d_{I,J}\in \mathbb {R}$$ $d_{I,J}\in R$, and ask which more elementary operators factor throughD. A decisive role is played by theCapon projection$$\mathcal {C}:\mathcal {V}(\delta ^2)\rightarrow \mathcal {V}(\delta ^2)$$ $C:V\left({\delta }^2\right)\to V\left({\delta }^2\right)$given by$$\mathcal {C} h_I\otimes h_J = h_I\otimes h_J$$ $C{h}_I\otimes h_J=h_I\otimes h_J$if$$|I|\le |J|$$ $\left|I\right|\le \left|J\right|$, and$$\mathcal {C} h_I\otimes h_J = 0$$ $C{h}_I\otimes h_J=0$if$$|I| > |J|$$ $\left|I\right|>\left|J\right|$, as our main result highlights: Given any bounded Haar multiplier$$D:X(Y)\rightarrow X(Y)$$ $D:X\left(Y\right)\to X\left(Y\right)$, there exist$$\lambda ,\mu \in \mathbb {R}$$ $\lambda ,\mu \in R$such that$$\begin{aligned} \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C})\text { approximately 1-projectionally factors through }D, \end{aligned}$$ $\begin{array}{c}\lambda C+\mu (\text{Id}-C)\text{approximately 1-projectionally factors through}D,\end{array}$i.e., for all$$\eta > 0$$ $\eta >0$, there exist bounded operatorsA, Bso thatABis the identity operator$${{\,\textrm{Id}\,}}$$ $\text{Id}$,$$\Vert A\Vert \cdot \Vert B\Vert = 1$$ $\Vert A\Vert ·\Vert B\Vert =1$and$$\Vert \lambda \mathcal {C} + \mu ({{\,\textrm{Id}\,}}-\mathcal {C}) - ADB\Vert < \eta $$ $\Vert \lambda C+\mu (\text{Id}-C)-ADB\Vert <\eta$. Additionally, if$$\mathcal {C}$$ $C$is unbounded onX(Y), then$$\lambda = \mu $$ $\lambda =\mu$and then$${{\,\textrm{Id}\,}}$$ $\text{Id}$either factors throughDor$${{\,\textrm{Id}\,}}-D$$ $\text{Id}-D$. 

   more » « less
3. Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of #SAT Algorithms

   https://doi.org/10.1007/s00224-022-10106-8  

   Vyas, Nikhil; Williams, R_Ryan (November 2022, Theory of Computing Systems)

   Abstract We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in$$\mathsf {Quasi}\text {-}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$$ $\mathrm{Quasi}-\mathrm{NP}=\mathrm{NTIME}\left[n^{{\left(\log n\right)}^{O\left(1\right)}}\right]$and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$$\mathcal { C}$$ $C$, by showing that$$\mathcal { C}$$ $C$admits non-trivial satisfiability and/or#SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a non-trivial#SAT algorithm for a circuit class$${\mathcal C}$$ $C$. Say that a symmetric Boolean functionf(x₁,…,x_n) issparseif it outputs 1 onO(1) values of$${\sum }_{i} x_{i}$$ ${\sum }_i{x}_i$. We show that for every sparsef, and for all “typical”$$\mathcal { C}$$ $C$, faster#SAT algorithms for$$\mathcal { C}$$ $C$circuits imply lower bounds against the circuit class$$f \circ \mathcal { C}$$ $f\circ C$, which may bestrongerthan$$\mathcal { C}$$ $C$itself. In particular:#SAT algorithms forn^k-size$$\mathcal { C}$$ $C$-circuits running in 2ⁿ/n^ktime (for allk) implyNEXPdoes not have$$(f \circ \mathcal { C})$$ $(f\circ C)$-circuits of polynomial size.#SAT algorithms for$$2^{n^{{\varepsilon }}}$$ $2^{n^{\epsilon }}$-size$$\mathcal { C}$$ $C$-circuits running in$$2^{n-n^{{\varepsilon }}}$$ $2^{n-n^{\epsilon }}$time (for someε> 0) implyQuasi-NPdoes not have$$(f \circ \mathcal { C})$$ $(f\circ C)$-circuits of polynomial size. Applying#SAT algorithms from the literature, one immediate corollary of our results is thatQuasi-NPdoes not haveEMAJ∘ACC⁰∘THRcircuits of polynomial size, whereEMAJis the “exact majority” function, improving previous lower bounds againstACC⁰[Williams JACM’14] andACC⁰∘THR[Williams STOC’14], [Murray-Williams STOC’18]. This is the first nontrivial lower bound against such a circuit class. 

   more » « less
4. Restricted spaces of holomorphic sections vanishing along subvarieties

   https://doi.org/10.1007/s00209-025-03706-w  

   Coman, Dan; Marinescu, George; Nguyên, Viêt-Anh (May 2025, Mathematische Zeitschrift)

   Abstract LetXbe a compact normal complex space of dimensionnandLbe a holomorphic line bundle onX. Suppose that$$\Sigma =(\Sigma _1,\ldots ,\Sigma _\ell )$$ $\Sigma =({\Sigma }_1,\dots ,{\Sigma }_{\ell })$is an$$\ell $$ $\ell$-tuple of distinct irreducible proper analytic subsets ofX,$$\tau =(\tau _1,\ldots ,\tau _\ell )$$ $\tau =({\tau }_1,\dots ,{\tau }_{\ell })$is an$$\ell $$ $\ell$-tuple of positive real numbers, and let$$H^0_0(X,L^p)$$ $H_0^0(X,L^p)$be the space of holomorphic sections of$$L^p:=L^{\otimes p}$$ $L^p:=L^{\otimes p}$that vanish to order at least$$\tau _jp$$ ${\tau }_{j}p$along$$\Sigma _j$$ ${\Sigma }_j$,$$1\le j\le \ell $$ $1\le j\le \ell$. If$$Y\subset X$$ $Y\subset X$is an irreducible analytic subset of dimensionm, we consider the space$$H^0_0 (X|Y, L^p)$$ $H_0^0\left(X\right|Y,L^p)$of holomorphic sections of$$L^p|_Y$$ $L^p{|}_Y$that extend to global holomorphic sections in$$H^0_0(X,L^p)$$ $H_0^0(X,L^p)$. Assuming that the triplet$$(L,\Sigma ,\tau )$$ $(L,\Sigma ,\tau )$is big in the sense that$$\dim H^0_0(X,L^p)\sim p^n$$ $dim{H}_0^0(X,L^p)\sim p^n$, we give a general condition onYto ensure that$$\dim H^0_0(X|Y,L^p)\sim p^m$$ $dim{H}_0^0\left(X\right|Y,L^p)\sim p^m$. WhenLis endowed with a continuous Hermitian metric, we show that the Fubini-Study currents of the spaces$$H^0_0(X|Y,L^p)$$ $H_0^0\left(X\right|Y,L^p)$converge to a certain equilibrium current onY. We apply this to the study of the equidistribution of zeros inYof random holomorphic sections in$$H^0_0(X|Y,L^p)$$ $H_0^0\left(X\right|Y,L^p)$as$$p\rightarrow \infty $$ $p\to \infty$. 

   more » « less
5. Characterizing Schwarz maps by tracial inequalities

   https://doi.org/10.1007/s11005-023-01636-4  

   Carlen, Eric; Müller-Hermes, Alexander (February 2023, Letters in Mathematical Physics)

   Abstract Let$$\phi $$ $\varphi$be a positive map from the$$n\times n$$ $n\times n$matrices$$\mathcal {M}_n$$ $M_n$to the$$m\times m$$ $m\times m$matrices$$\mathcal {M}_m$$ $M_m$. It is known that$$\phi $$ $\varphi$is 2-positive if and only if for all$$K\in \mathcal {M}_n$$ $K\in M_n$and all strictly positive$$X\in \mathcal {M}_n$$ $X\in M_n$,$$\phi (K^*X^{-1}K) \geqslant \phi (K)^*\phi (X)^{-1}\phi (K)$$ $\varphi \left(K^{\ast }{X}^{-1}K\right)⩾\varphi {\left(K\right)}^{\ast }\varphi {\left(X\right)}^{-1}\varphi \left(K\right)$. This inequality is not generally true if$$\phi $$ $\varphi$is merely a Schwarz map. We show that the corresponding tracial inequality$${{\,\textrm{Tr}\,}}[\phi (K^*X^{-1}K)] \geqslant {{\,\textrm{Tr}\,}}[\phi (K)^*\phi (X)^{-1}\phi (K)]$$ $\text{Tr}\left[\varphi \left(K^{\ast }{X}^{-1}K\right)\right]⩾\text{Tr}\left[\varphi {\left(K\right)}^{\ast }\varphi {\left(X\right)}^{-1}\varphi \left(K\right)\right]$holds for a wider class of positive maps that is specified here. We also comment on the connections of this inequality with various monotonicity statements that have found wide use in mathematical physics, and apply it, and a close relative, to obtain some new, definitive results. 

   more » « less