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)

   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. 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
3. Instanton contributions to the ABJM free energy from quantum M2 branes

   https://doi.org/10.1007/JHEP10(2023)029  

   Beccaria, M ; Giombi, S ; Tseytlin, A A ( October 2023 , Journal of High Energy Physics)

   We present a quantum M2 brane computation of the instanton prefactor in the leading non-perturbative contribution to the ABJM 3-sphere free energy at largeNand fixed levelk. Using supersymmetric localization, such instanton contribution was found earlier to take the form$$ {F}^{inst}\left(N,k\right)=-{\left({\sin}^2\frac{2\pi }{k}\right)}^{-1}\exp \left(-2\pi \sqrt{\frac{2N}{k}}\right)+.\dots $$$F^{\text{inst}}\left(N,k\right)=-{\left({sin}^2\frac{2\pi }{k}\right)}^{-1}exp\left(-2\pi \sqrt{\frac{2N}{k}}\right)+.\dots$The exponent comes from the action of an M2 brane instanton wrapped onS³/ℤ_k, which represents the M-theory uplift of the ℂP¹instanton in type IIA string theory on AdS₄× ℂP³. The IIA string computation of the leading largekterm in the instanton prefactor was recently performed in arXiv:2304.12340. Here we find that the exact value of the prefactor$$ {\left({\sin}^2\frac{2\pi }{k}\right)}^{-1} $$${\left({sin}^2\frac{2\pi }{k}\right)}^{-1}$is reproduced by the 1-loop term in the M2 brane partition function expanded near theS³/ℤ_kinstanton configuration. As in the Wilson loop example in arXiv:2303.15207, the quantum M2 brane computation is well defined and produces a finite result in exact agreement with localization.

    

   more » « less
4. A case study of SMEFT $$ \mathcal{O}\left(1/{\Lambda}^4\right) $$ effects in diboson processes: pp → W±(ℓ±ν)γ

   https://doi.org/10.1007/JHEP05(2024)223  

   Martin, Adam ( May 2024 , Journal of High Energy Physics)

   In this paper we explorepp→W^±(ℓ^±ν)γto$$ \mathcal{O}\left(1/{\Lambda}^4\right) $$$O\left(1/{\Lambda }^4\right)$in the SMEFT expansion. Calculations to this order are necessary to properly capture SMEFT contributions that grow with energy, as the interference between energy-enhanced SMEFT effects at$$ \mathcal{O}\left(1/{\Lambda}^2\right) $$$O\left(1/{\Lambda }^2\right)$and the Standard Model is suppressed. We find that there are several dimension eight operators that interfere with the Standard Model and lead to the same energy growth, ~$$ \mathcal{O}\left({E}^4/{\Lambda}^4\right) $$$O\left(E^4/{\Lambda }^4\right)$, as dimension six squared. While energy-enhanced SMEFT contributions are a main focus, our calculation includes the complete set of$$ \mathcal{O}\left(1/{\Lambda}^4\right) $$$O\left(1/{\Lambda }^4\right)$SMEFT effects consistent with U(3)⁵flavor symmetry. Additionally, we include the decay of theW^±→ ℓ^±ν, making the calculation actually$$ \overline{q}{q}^{\prime}\to {\ell}^{\pm}\nu \gamma $$$\overline{q}{q}^{\prime }\to {\ell }^{\pm }\mathrm{\nu \gamma }$. As such, we are able to study the impact of non-resonant SMEFT operators, such as$$ \left({L}^{\dagger }{\overline{\sigma}}^{\mu }{\tau}^IL\right)\left({Q}^{\dagger }{\overline{\sigma}}^{\nu }{\tau}^IQ\right) $$$\left(L^{†}{\overline{\sigma }}^{\mu }{\tau }^{I}L\right)\left(Q^{†}{\overline{\sigma }}^{\nu }{\tau }^{I}Q\right)$B_μν, which contribute to$$ \overline{q}{q}^{\prime}\to {\ell}^{\pm}\nu \gamma $$$\overline{q}{q}^{\prime }\to {\ell }^{\pm }\mathrm{\nu \gamma }$directly and not to$$ \overline{q}{q}^{\prime}\to {W}^{\pm}\gamma $$$\overline{q}{q}^{\prime }\to W^{\pm }\gamma$. We show several distributions to illustrate the shape differences of the different contributions.

    

   more » « less
5. Search for the $$ {B}_s^0 $$ → μ+μ−γ decay

   https://doi.org/10.1007/JHEP07(2024)101  

   Aaij, R ; Abdelmotteleb, A_S W ; Abellan_Beteta, C ; Abudinén, F ; Ackernley, T ; Adefisoye, A A ; Adeva, B ; Adinolfi, M ; Adlarson, P ; Agapopoulou, C ; et al ( July 2024 , Journal of High Energy Physics)

   A search for the fully reconstructed$$ {B}_s^0 $$$B_s^0$→ μ⁺μ⁻γdecay is performed at the LHCb experiment using proton-proton collisions at$$ \sqrt{s} $$$\sqrt{s}$= 13 TeV corresponding to an integrated luminosity of 5.4 fb⁻¹. No significant signal is found and upper limits on the branching fraction in intervals of the dimuon mass are set$$ {\displaystyle \begin{array}{cc}\mathcal{B}\left({B}_s^0\to {\mu}^{+}{\mu}^{-}\gamma \right)<4.2\times {10}^{-8},& m\left({\mu}^{+}{\mu}^{-}\right)\in \left[2{m}_{\mu },1.70\right]\textrm{GeV}/{c}^2,\\ {}\mathcal{B}\left({B}_s^0\to {\mu}^{+}{\mu}^{-}\gamma \right)<7.7\times {10}^{-8},&\ m\left({\mu}^{+}{\mu}^{-}\right)\in \left[\textrm{1.70,2.88}\right]\textrm{GeV}/{c}^2,\\ {}\mathcal{B}\left({B}_s^0\to {\mu}^{+}{\mu}^{-}\gamma \right)<4.2\times {10}^{-8},& m\left({\mu}^{+}{\mu}^{-}\right)\in \left[3.92,{m}_{B_s^0}\right]\textrm{GeV}/{c}^2,\end{array}} $$$\begin{array}{cc}B\left(B_s^0\to {\mu }^{+}{\mu }^{-}\gamma \right)<4.2\times {10}^{-8},& m\left({\mu }^{+}{\mu }^{-}\right)\in \left(2m_{\mu },1.70\right)\mathrm{GeV}/c^2,\\ B\left(B_s^0\to {\mu }^{+}{\mu }^{-}\gamma \right)<7.7\times {10}^{-8},& m\left({\mu }^{+}{\mu }^{-}\right)\in \left(\mathrm{1.70,\; 2.88}\right)\mathrm{GeV}/c^2,\\ B\left(B_s^0\to {\mu }^{+}{\mu }^{-}\gamma \right)<4.2\times {10}^{-8},& m\left({\mu }^{+}{\mu }^{-}\right)\in \left(3.92,m_{B_s^0}\right)\mathrm{GeV}/c^2,\end{array}$

   at 95% confidence level. Additionally, upper limits are set on the branching fraction in the [2m_μ,1.70] GeV/c²dimuon mass region excluding the contribution from the intermediateϕ(1020) meson, and in the region combining all dimuon-mass intervals.

    

   more » « less