More Like this

1. 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
2. Multidimensional WENO-AO Reconstructions Using a Simplified Smoothness Indicator and Applications to Conservation Laws

   https://doi.org/10.1007/s10915-023-02319-x  

   Huang, Chieh-Sen ; Arbogast, Todd ; Tian, Chenyu ( August 2023 , Journal of Scientific Computing)

   Finite volume, weighted essentially non-oscillatory (WENO) schemes require the computation of a smoothness indicator. This can be expensive, especially in multiple space dimensions. We consider the use of the simple smoothness indicator$$\sigma ^{\textrm{S}}= \frac{1}{N_{\textrm{S}}-1}\sum _{j} ({\bar{u}}_{j} - {\bar{u}}_{m})^2$$${\sigma }^{\text{S}}=\frac{1}{N_{\text{S}}-1}{\sum }_j{({\overline{u}}_j-{\overline{u}}_m)}^2$, where$$N_{\textrm{S}}$$$N_{\text{S}}$is the number of mesh elements in the stencil,$${\bar{u}}_j$$${\overline{u}}_j$is the local function average over mesh elementj, and indexmgives the target element. Reconstructions utilizing standard WENO weighting fail with this smoothness indicator. We develop a modification of WENO-Z weighting that gives a reliable and accurate reconstruction of adaptive order, which we denote as SWENOZ-AO. We prove that it attains the order of accuracy of the large stencil polynomial approximation when the solution is smooth, and drops to the order of the small stencil polynomial approximations when there is a jump discontinuity in the solution. Numerical examples in one and two space dimensions on general meshes verify the approximation properties of the reconstruction. They also show it to be about 10 times faster in two space dimensions than reconstructions using the classic smoothness indicator. The new reconstruction is applied to define finite volume schemes to approximate the solution of hyperbolic conservation laws. Numerical tests show results of the same quality as standard WENO schemes using the classic smoothness indicator, but with an overall speedup in the computation time of about 3.5–5 times in 2D tests. Moreover, the computational efficiency (CPU time versus error) is noticeably improved.

    

   more » « less
3. Azimuthal correlations of heavy-flavor hadron decay electrons with charged particles in pp and p–Pb collisions at $$\pmb {\sqrt{s_{\mathrm{{NN}}}}}$$ = 5.02 TeV

   https://doi.org/10.1140/epjc/s10052-023-11835-x  

   Acharya, S. ; Adamová, D. ; Adler, A. ; Aglieri Rinella, G. ; Agnello, M. ; Agrawal, N. ; Ahammed, Z. ; Ahmad, S. ; Ahn, S. U. ; Ahuja, I. ; et al ( August 2023 , The European Physical Journal C)

   The azimuthal ($$\Delta \varphi $$$\Delta \phi$) correlation distributions between heavy-flavor decay electrons and associated charged particles are measured in pp and p–Pb collisions at$$\sqrt{s_{\mathrm{{NN}}}} = 5.02$$$\sqrt{s_{\mathrm{NN}}}=5.02$TeV. Results are reported for electrons with transverse momentum$$4$4<p_{\text{T}}<16$$$\textrm{GeV}/c$$$\text{GeV}/c$ and pseudorapidity$$|\eta |<0.6$$$\left|\eta \right|<0.6$. The associated charged particles are selected with transverse momentum$$1$1<p_{\text{T}}<7$$$\textrm{GeV}/c$$$\text{GeV}/c$, and relative pseudorapidity separation with the leading electron$$|\Delta \eta | < 1$$$\left|\Delta \eta \right|<1$. The correlation measurements are performed to study and characterize the fragmentation and hadronization of heavy quarks. The correlation structures are fitted with a constant and two von Mises functions to obtain the baseline and the near- and away-side peaks, respectively. The results from p–Pb collisions are compared with those from pp collisions to study the effects of cold nuclear matter. In the measured trigger electron and associated particle kinematic regions, the two collision systems give consistent results. The$$\Delta \varphi $$$\Delta \phi$distribution and the peak observables in pp and p–Pb collisions are compared with calculations from various Monte Carlo event generators.

    

   more » « less
4. Measurement of the mass dependence of the transverse momentum of lepton pairs in Drell–Yan production in proton–proton collisions at $$\sqrt{s} = 13\,\text {Te\hspace{-.08em}V} $$

   https://doi.org/10.1140/epjc/s10052-023-11631-7  

   Tumasyan, A. ; Adam, W. ; Andrejkovic, J. W. ; Bergauer, T. ; Chatterjee, S. ; Dragicevic, M. ; Valle, A. Escalante ; Frühwirth, R. ; Jeitler, M. ; Krammer, N. ; et al ( July 2023 , The European Physical Journal C)

   The double differential cross sections of the Drell–Yan lepton pair ($$\ell ^+\ell ^-$$${\ell }^{+}{\ell }^{-}$, dielectron or dimuon) production are measured as functions of the invariant mass$$m_{\ell \ell }$$$m_{\ell \ell }$, transverse momentum$$p_{\textrm{T}} (\ell \ell )$$$p_{\text{T}}\left(\ell \ell \right)$, and$$\varphi ^{*}_{\eta }$$${\phi }_{\eta }^{\ast }$. The$$\varphi ^{*}_{\eta }$$${\phi }_{\eta }^{\ast }$observable, derived from angular measurements of the leptons and highly correlated with$$p_{\textrm{T}} (\ell \ell )$$$p_{\text{T}}\left(\ell \ell \right)$, is used to probe the low-$$p_{\textrm{T}} (\ell \ell )$$$p_{\text{T}}\left(\ell \ell \right)$region in a complementary way. Dilepton masses up to 1$$\,\text {Te\hspace{-.08em}V}$$$\text{Te}\text{V}$are investigated. Additionally, a measurement is performed requiring at least one jet in the final state. To benefit from partial cancellation of the systematic uncertainty, the ratios of the differential cross sections for various$$m_{\ell \ell }$$$m_{\ell \ell }$ranges to those in the Z mass peak interval are presented. The collected data correspond to an integrated luminosity of 36.3$$\,\text {fb}^{-1}$$${\text{fb}}^{-1}$of proton–proton collisions recorded with the CMS detector at the LHC at a centre-of-mass energy of 13$$\,\text {Te\hspace{-.08em}V}$$$\text{Te}\text{V}$. Measurements are compared with predictions based on perturbative quantum chromodynamics, including soft-gluon resummation.

    

   more » « less
5. Torsion phenomena for zero-cycles on a product of curves over a number field

   https://doi.org/10.1007/s40993-024-00519-4  

   Gazaki, Evangelia ; Love, Jonathan ( March 2024 , Research in Number Theory)

   For a smooth projective varietyXover an algebraic number fieldka conjecture of Bloch and Beilinson predicts that the kernel of the Albanese map ofXis a torsion group. In this article we consider a product$$X=C_1\times \cdots \times C_d$$$X=C_1\times \cdots \times C_d$of smooth projective curves and show that if the conjecture is true for any subproduct of two curves, then it is true forX. For a product$$X=C_1\times C_2$$$X=C_1\times C_2$of two curves over$$\mathbb {Q} $$$Q$with positive genus we construct many nontrivial examples that satisfy the weaker property that the image of the natural map$$J_1(\mathbb {Q})\otimes J_2(\mathbb {Q})\xrightarrow {\varepsilon }{{\,\textrm{CH}\,}}_0(C_1\times C_2)$$$J_1\left(Q\right)\otimes J_2\left(Q\right)\stackrel{\epsilon }{\to }{\text{CH}}_0(C_1\times C_2)$is finite, where$$J_i$$$J_i$is the Jacobian variety of$$C_i$$$C_i$. Our constructions include many new examples of non-isogenous pairs of elliptic curves$$E_1, E_2$$$E_1,E_2$with positive rank, including the first known examples of rank greater than 1. Combining these constructions with our previous result, we obtain infinitely many nontrivial products$$X=C_1\times \cdots \times C_d$$$X=C_1\times \cdots \times C_d$for which the analogous map$$\varepsilon $$$\epsilon$has finite image.

    

   more » « less