More Like this

1. Semileptonic form factors for $$B\rightarrow D^*\ell \nu $$ at nonzero recoil from $$2+1$$-flavor lattice QCD: Fermilab Lattice and MILC Collaborations

   https://doi.org/10.1140/epjc/s10052-022-10984-9  

   Bazavov, A. ; DeTar, C. E. ; Du, D. ; El-Khadra, A. X. ; Gámiz, E. ; Gelzer, Z. ; Gottlieb, S. ; Heller, U. M. ; Kronfeld, A. S. ; Laiho, J. ; et al ( December 2022 , The European Physical Journal C)

   We present the first unquenched lattice-QCD calculation of the form factors for the decay$$B\rightarrow D^*\ell \nu $$$B\to D^{\ast }\ell \nu$at nonzero recoil. Our analysis includes 15 MILC ensembles with$$N_f=2+1$$$N_f=2+1$flavors of asqtad sea quarks, with a strange quark mass close to its physical mass. The lattice spacings range from$$a\approx 0.15$$$a\approx 0.15$fm down to 0.045 fm, while the ratio between the light- and the strange-quark masses ranges from 0.05 to 0.4. The valencebandcquarks are treated using the Wilson-clover action with the Fermilab interpretation, whereas the light sector employs asqtad staggered fermions. We extrapolate our results to the physical point in the continuum limit using rooted staggered heavy-light meson chiral perturbation theory. Then we apply a model-independent parametrization to extend the form factors to the full kinematic range. With this parametrization we perform a joint lattice-QCD/experiment fit using several experimental datasets to determine the CKM matrix element$$|V_{cb}|$$$|V_{\mathrm{cb}}|$. We obtain$$\left| V_{cb}\right| = (38.40 \pm 0.68_{\text {th}} \pm 0.34_{\text {exp}} \pm 0.18_{\text {EM}})\times 10^{-3}$$$\left(V_{\mathrm{cb}}\right)=(38.40\pm 0.{68}_{\text{th}}\pm 0.{34}_{\text{exp}}\pm 0.{18}_{\text{EM}})\times {10}^{-3}$. The first error is theoretical, the second comes from experiment and the last one includes electromagnetic and electroweak uncertainties, with an overall$$\chi ^2\text {/dof} = 126/84$$${\chi }^2\text{/dof}=126/84$, which illustrates the tensions between the experimental data sets, and between theory and experiment. This result is in agreement with previous exclusive determinations, but the tension with the inclusive determination remains. Finally, we integrate the differential decay rate obtained solely from lattice data to predict$$R(D^*) = 0.265 \pm 0.013$$$R\left(D^{\ast }\right)=0.265\pm 0.013$, which confirms the current tension between theory and experiment.

    

   more » « less
2. Eulerian Walks in Temporal Graphs

   https://doi.org/10.1007/s00453-022-01021-y  

   Marino, Andrea ; Silva, Ana ( August 2022 , Algorithmica)

   An Eulerian walk (or Eulerian trail) is a walk (resp. trail) that visits every edge of a graphGat least (resp. exactly) once. This notion was first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. But what if Euler had to take a bus? In a temporal graph$$\varvec{(G,\lambda )}$$$(G,\lambda )$, with$$\varvec{\lambda : E(G)}\varvec{\rightarrow } \varvec{2}^{\varvec{[\tau ]}}$$$\lambda :E\left(G\right)\to 2^{\left[\tau \right]}$, an edge$$\varvec{e}\varvec{\in } \varvec{E(G)}$$$e\in E\left(G\right)$is available only at the times specified by$$\varvec{\lambda (e)}\varvec{\subseteq } \varvec{[\tau ]}$$$\lambda \left(e\right)\subseteq \left[\tau \right]$, in the same way the connections of the public transportation network of a city or of sightseeing tours are available only at scheduled times. In this paper, we deal with temporal walks, local trails, and trails, respectively referring to edge traversal with no constraints, constrained to not repeating the same edge in a single timestamp, and constrained to never repeating the same edge throughout the entire traversal. We show that, if the edges are always available, then deciding whether$$\varvec{(G,\lambda )}$$$(G,\lambda )$has a temporal walk or trail is polynomial, while deciding whether it has a local trail is$$\varvec{\texttt {NP}}$$$\mathrm{NP}$-complete even if$$\varvec{\tau = 2}$$$\tau =2$. In contrast, in the general case, solving any of these problems is$$\varvec{\texttt {NP}}$$$\mathrm{NP}$-complete, even under very strict hypotheses. We finally give$$\varvec{\texttt {XP}}$$$\mathrm{XP}$algorithms parametrized by$$\varvec{\tau }$$$\tau$for walks, and by$$\varvec{\tau +tw(G)}$$$\tau +tw\left(G\right)$for trails and local trails, where$$\varvec{tw(G)}$$$tw\left(G\right)$refers to the treewidth of$$\varvec{G}$$$G$.

    

   more » « less
3. Measurements of the associated production of a W boson and a charm quark in proton–proton collisions at $$\sqrt{s}=8\,\text {TeV} $$

   https://doi.org/10.1140/epjc/s10052-022-10897-7  

   Tumasyan, A. ; Adam, W. ; Bergauer, T. ; Dragicevic, M. ; Erö, J. ; Valle, A. Escalante ; Frühwirth, R. ; Jeitler, M. ; Krammer, N. ; Lechner, L. ; et al ( December 2022 , The European Physical Journal C)

   Measurements of the associated production of a W boson and a charm ($${\text {c}}$$$\text{c}$) quark in proton–proton collisions at a centre-of-mass energy of 8$$\,\text {TeV}$$$\text{TeV}$are reported. The analysis uses a data sample corresponding to a total integrated luminosity of 19.7$$\,\text {fb}^{-1}$$${\text{fb}}^{-1}$collected by the CMS detector at the LHC. The W bosons are identified through their leptonic decays to an electron or a muon, and a neutrino. Charm quark jets are selected using distinctive signatures of charm hadron decays. The product of the cross section and branching fraction$$\sigma (\text {p}\text {p}\rightarrow \text {W}+ {\text {c}}+ \text {X}) {\mathcal {B}}(\text {W}\rightarrow \ell \upnu )$$$\sigma (\text{pp}\to \text{W}+\text{c}+\text{X})B(\text{W}\to \ell \nu )$, where$$\ell = \text {e}$$$\ell =\text{e}$or$$\upmu $$$\mu$, and the cross section ratio$$\sigma (\text {p}\text {p}\rightarrow {{\text {W}}^{+} + \bar{{\text {c}}} + \text {X}}) / \sigma (\text {p}\text {p}\rightarrow {{\text {W}}^{-} + {\text {c}}+ \text {X}})$$$\sigma (\text{pp}\to {\text{W}}^{+}+\overline{\text{c}}+\text{X})/\sigma (\text{pp}\to {\text{W}}^{-}+\text{c}+\text{X})$are measured in a fiducial volume and differentially as functions of the pseudorapidity and of the transverse momentum of the lepton from the W boson decay. The results are compared with theoretical predictions. The impact of these measurements on the determination of the strange quark distribution is assessed.

    

   more » « less
4. Improved Merlin–Arthur Protocols for Central Problems in Fine-Grained Complexity

   https://doi.org/10.1007/s00453-023-01102-6  

   Akmal, Shyan ; Chen, Lijie ; Jin, Ce ; Raj, Malvika ; Williams, Ryan ( February 2023 , Algorithmica)

   In a Merlin–Arthur proof system, the proof verifier (Arthur) accepts valid proofs (from Merlin) with probability 1, and rejects invalid proofs with probability arbitrarily close to 1. The running time of such a system is defined to be the length of Merlin’s proof plus the running time of Arthur. We provide new Merlin–Arthur proof systems for some key problems in fine-grained complexity. In several cases our proof systems have optimal running time. Our main results include:

   Certifying that a list ofnintegers has no 3-SUM solution can be done in Merlin–Arthur time$$\tilde{O}(n)$$$\tilde{O}\left(n\right)$. Previously, Carmosino et al. [ITCS 2016] showed that the problem has a nondeterministic algorithm running in$$\tilde{O}(n^{1.5})$$$\tilde{O}\left(n^{1.5}\right)$time (that is, there is a proof system with proofs of length$$\tilde{O}(n^{1.5})$$$\tilde{O}\left(n^{1.5}\right)$and a deterministic verifier running in$$\tilde{O}(n^{1.5})$$$\tilde{O}\left(n^{1.5}\right)$time).

   Counting the number ofk-cliques with total edge weight equal to zero in ann-node graph can be done in Merlin–Arthur time$${\tilde{O}}(n^{\lceil k/2\rceil })$$$\tilde{O}\left(n^{\lceil k/2\rceil }\right)$(where$$k\ge 3$$$k\ge 3$). For oddk, this bound can be further improved for sparse graphs: for example, counting the number of zero-weight triangles in anm-edge graph can be done in Merlin–Arthur time$${\tilde{O}}(m)$$$\tilde{O}\left(m\right)$. Previous Merlin–Arthur protocols by Williams [CCC’16] and Björklund and Kaski [PODC’16] could only countk-cliques in unweighted graphs, and had worse running times for smallk.

   Computing the All-Pairs Shortest Distances matrix for ann-node graph can be done in Merlin–Arthur time$$\tilde{O}(n^2)$$$\tilde{O}\left(n^2\right)$. Note this is optimal, as the matrix can have$$\Omega (n^2)$$$\Omega \left(n^2\right)$nonzero entries in general. Previously, Carmosino et al. [ITCS 2016] showed that this problem has an$$\tilde{O}(n^{2.94})$$$\tilde{O}\left(n^{2.94}\right)$nondeterministic time algorithm.

   Certifying that ann-variablek-CNF is unsatisfiable can be done in Merlin–Arthur time$$2^{n/2 - n/O(k)}$$$2^{n/2-n/O\left(k\right)}$. We also observe an algebrization barrier for the previous$$2^{n/2}\cdot \textrm{poly}(n)$$$2^{n/2}·\text{poly}\left(n\right)$-time Merlin–Arthur protocol of R. Williams [CCC’16] for$$\#$$$\#$SAT: in particular, his protocol algebrizes, and we observe there is no algebrizing protocol fork-UNSAT running in$$2^{n/2}/n^{\omega (1)}$$$2^{n/2}/n^{\omega \left(1\right)}$time. Therefore we have to exploit non-algebrizing properties to obtain our new protocol.

   Certifying a Quantified Boolean Formula is true can be done in Merlin–Arthur time$$2^{4n/5}\cdot \textrm{poly}(n)$$$2^{4n/5}·\text{poly}\left(n\right)$. Previously, the only nontrivial result known along these lines was an Arthur–Merlin–Arthur protocol (where Merlin’s proof depends on some of Arthur’s coins) running in$$2^{2n/3}\cdot \textrm{poly}(n)$$$2^{2n/3}·\text{poly}\left(n\right)$time.

   Due to the centrality of these problems in fine-grained complexity, our results have consequences for many other problems of interest. For example, our work implies that certifying there is no Subset Sum solution tonintegers can be done in Merlin–Arthur time$$2^{n/3}\cdot \textrm{poly}(n)$$$2^{n/3}·\text{poly}\left(n\right)$, improving on the previous best protocol by Nederlof [IPL 2017] which took$$2^{0.49991n}\cdot \textrm{poly}(n)$$$2^{0.49991n}·\text{poly}\left(n\right)$time.

    

   more » « less
5. From approximate to exact integer programming

   https://doi.org/10.1007/s10107-024-02084-1  

   Dadush, Daniel ; Eisenbrand, Friedrich ; Rothvoss, Thomas ( April 2024 , Mathematical Programming)

   Approximate integer programming is the following: For a given convex body$$K \subseteq {\mathbb {R}}^n$$$K\subseteq R^n$, either determine whether$$K \cap {\mathbb {Z}}^n$$$K\cap Z^n$is empty, or find an integer point in the convex body$$2\cdot (K - c) +c$$$2·(K-c)+c$which isK, scaled by 2 from its center of gravityc. Approximate integer programming can be solved in time$$2^{O(n)}$$$2^{O\left(n\right)}$while the fastest known methods for exact integer programming run in time$$2^{O(n)} \cdot n^n$$$2^{O\left(n\right)}·n^n$. So far, there are no efficient methods for integer programming known that are based on approximate integer programming. Our main contribution are two such methods, each yielding novel complexity results. First, we show that an integer point$$x^* \in (K \cap {\mathbb {Z}}^n)$$$x^{\ast }\in (K\cap Z^n)$can be found in time$$2^{O(n)}$$$2^{O\left(n\right)}$, provided that theremaindersof each component$$x_i^* \mod \ell $$$x_i^{\ast }mod\ell$for some arbitrarily fixed$$\ell \ge 5(n+1)$$$\ell \ge 5(n+1)$of$$x^*$$$x^{\ast }$are given. The algorithm is based on acutting-plane technique, iteratively halving the volume of the feasible set. The cutting planes are determined via approximate integer programming. Enumeration of the possible remainders gives a$$2^{O(n)}n^n$$$2^{O\left(n\right)}{n}^n$algorithm for general integer programming. This matches the current best bound of an algorithm by Dadush (Integer programming, lattice algorithms, and deterministic, vol. Estimation. Georgia Institute of Technology, Atlanta, 2012) that is considerably more involved. Our algorithm also relies on a newasymmetric approximate Carathéodory theoremthat might be of interest on its own. Our second method concerns integer programming problems in equation-standard form$$Ax = b, 0 \le x \le u, \, x \in {\mathbb {Z}}^n$$$Ax=b,0\le x\le u,x\in Z^n$. Such a problem can be reduced to the solution of$$\prod _i O(\log u_i +1)$$${\prod }_{i}O(log{u}_i+1)$approximate integer programming problems. This implies, for example thatknapsackorsubset-sumproblems withpolynomial variable range$$0 \le x_i \le p(n)$$$0\le x_i\le p\left(n\right)$can be solved in time$$(\log n)^{O(n)}$$${(logn)}^{O\left(n\right)}$. For these problems, the best running time so far was$$n^n \cdot 2^{O(n)}$$$n^n·2^{O\left(n\right)}$.

    

   more » « less