More Like this

1. 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
2. Evidence-driven spatiotemporal COVID-19 hospitalization prediction with Ising dynamics

   https://doi.org/10.1038/s41467-023-38756-3  

   Gao, Junyi; Heintz, Joerg; Mack, Christina; Glass, Lucas; Cross, Adam; Sun, Jimeng (May 2023, Nature Communications)

   Abstract In this work, we aim to accurately predict the number of hospitalizations during the COVID-19 pandemic by developing a spatiotemporal prediction model. We propose HOIST, an Ising dynamics-based deep learning model for spatiotemporal COVID-19 hospitalization prediction. By drawing the analogy between locations and lattice sites in statistical mechanics, we use the Ising dynamics to guide the model to extract and utilize spatial relationships across locations and model the complex influence of granular information from real-world clinical evidence. By leveraging rich linked databases, including insurance claims, census information, and hospital resource usage data across the U.S., we evaluate the HOIST model on the large-scale spatiotemporal COVID-19 hospitalization prediction task for 2299 counties in the U.S. In the 4-week hospitalization prediction task, HOIST achieves 368.7 mean absolute error, 0.6$${R}^{2}$$ $R^2$and 0.89 concordance correlation coefficient score on average. Our detailed number needed to treat (NNT) and cost analysis suggest that future COVID-19 vaccination efforts may be most impactful in rural areas. This model may serve as a resource for future county and state-level vaccination efforts. 

   more » « less
3. Misconceptions in Finite-Trace and Infinite-Trace Linear Temporal Logic

   https://doi.org/10.1007/978-3-031-71162-6_30  

   Greenman, Ben; Prasad, Siddhartha; Di_Stasio, Antonio; Zhu, Shufang; De_Giacomo, Giuseppe; Krishnamurthi, Shriram; Montali, Marco; Nelson, Tim; Zizyte, Milda (September 2024, Springer Nature Switzerland)

   Abstract With the growing use of temporal logics in areas ranging from robot planning to runtime verification, it is critical that users have a clear understanding of what a specification means. Toward this end, we have been developing a catalog of semantic errors and a suite of test instruments targeting various user-groups. The catalog is of interest to educators, to logic designers, to formula authors, and to tool builders, e.g., to identify mistakes. The test instruments are suitable for classroom teaching or self-study. This paper reports on five sets of survey data collected over a three-year span. We study misconceptions about finite-trace$$\textsc {ltl}_{f}$$ ${LTL}_f$in threeltl-aware audiences, and misconceptions about standardltlin novices. We find several mistakes, even among experts. In addition, the data supports several categories of errors in both$$\textsc {ltl}_{f}$$ ${LTL}_f$andltlthat have not been identified in prior work. These findings, based on data from actual users, offer insights into whatspecific waystemporal logics are tricky and provide a groundwork for future interventions. 

   more » « less
4. Measurement of exclusive $$J/\psi$$ and $$\psi(2S)$$ production at $$\sqrt{s}=13$$ TeV

   https://doi.org/10.21468/SciPostPhys.18.2.071  

   Collaboration, LHCb; Aaij, Roel; Abdelmotteleb, Ahmed_Sameh Wagih; Abellan_Beteta, Carlos; Abudinèn, Fernando Jesus; Ackernley, Thomas; Adefisoye, Ayomide Matthew; Adeva, Bernardo; Adinolfi, Marco; Adlarson, Patrik Harri; et al (January 2025, SciPost Physics)

   Measurements are presented of the cross-section for the central exclusive production ofJ/\psi\to\mu^+\mu^- $J/\psi \to {\mu }^{+}{\mu }^{-}$and\psi(2S)\to\mu^+\mu^- $\psi \left(2S\right)\to {\mu }^{+}{\mu }^{-}$processes in proton-proton collisions at\sqrt{s} = 13 \ \mathrm{TeV} $\sqrt{s}=13TeV$with 2016–2018 data. They are performed by requiring both muons to be in the LHCb acceptance (with pseudorapidity2<\eta_{\mu^±} < 4.5 $2<{\eta }_{{\mu }^{\pm }}<4.5$) and mesons in the rapidity range2.0 < y < 4.5 $2.0<y<4.5$. The integrated cross-section results are\sigma_{J/\psi\to\mu^+\mu^-}(2.0 ${\sigma }_{J/\psi \to {\mu }^{+}{\mu }^{-}}(2.0<y_{J/\psi }<4.5,2.0<{\eta }_{{\mu }^{\pm }}<4.5)=400\pm 2\pm 5\pm 12pb,{\sigma }_{\psi \left(2S\right)\to {\mu }^{+}{\mu }^{-}}(2.0<y_{\psi \left(2S\right)}<4.5,2.0<{\eta }_{{\mu }^{\pm }}<4.5)=9.40\pm 0.15\pm 0.13\pm 0.27pb,$where the uncertainties are statistical, systematic and due to the luminosity determination. In addition, a measurement of the ratio of\psi(2S) $\psi \left(2S\right)$andJ/\psi $J/\psi$cross-sections, at an average photon-proton centre-of-mass energy of1\ \mathrm{TeV} $1TeV$, is performed, giving$ = 0.1763 ± 0.0029 ± 0.0008 ± 0.0039,$$ where the first uncertainty is statistical, the second systematic and the third due to the knowledge of the involved branching fractions. For the first time, the dependence of theJ/\psi$ $J/\psi$and\psi(2S) $\psi \left(2S\right)$cross-sections on the total transverse momentum transfer is determined inpp $pp$collisions and is found consistent with the behaviour observed in electron-proton collisions. 

   more » « less
5. Instantaneous everywhere-blowup of parabolic SPDEs

   https://doi.org/10.1007/s00440-024-01263-7  

   Foondun, Mohammud; Khoshnevisan, Davar; Nualart, Eulalia (October 2024, Probability Theory and Related Fields)

   Abstract We consider the following stochastic heat equation$$\begin{aligned} \partial _t u(t,x) = \tfrac{1}{2} \partial ^2_x u(t,x) + b(u(t,x)) + \sigma (u(t,x)) {\dot{W}}(t,x), \end{aligned}$$ $\begin{array}{c}{\partial }_{t}u(t,x)=\frac{1}{2}{\partial }_x^{2}u(t,x)+b\left(u(t,x)\right)+\sigma \left(u(t,x)\right)\dot{W}(t,x),\end{array}$defined for$$(t,x)\in (0,\infty )\times {\mathbb {R}}$$ $(t,x)\in (0,\infty )\times R$, where$${\dot{W}}$$ $\dot{W}$denotes space-time white noise. The function$$\sigma $$ $\sigma$is assumed to be positive, bounded, globally Lipschitz, and bounded uniformly away from the origin, and the functionbis assumed to be positive, locally Lipschitz and nondecreasing. We prove that the Osgood condition$$\begin{aligned} \int _1^\infty \frac{\textrm{d}y}{b(y)}<\infty \end{aligned}$$ $\begin{array}{c}{\int }_1^{\infty }\frac{\text{d}y}{b\left(y\right)}<\infty \end{array}$implies that the solution almost surely blows up everywhere and instantaneously, In other words, the Osgood condition ensures that$$\textrm{P}\{ u(t,x)=\infty \quad \hbox { for all } t>0 \hbox { and } x\in {\mathbb {R}}\}=1.$$ $\text{P}\left\{u\right(t,x)=\infty \text{for all}t>0\text{and}x\in R\}=1.$The main ingredients of the proof involve a hitting-time bound for a class of differential inequalities (Remark 3.3), and the study of the spatial growth of stochastic convolutions using techniques from the Malliavin calculus and the Poincaré inequalities that were developed in Chen et al. (Electron J Probab 26:1–37, 2021, J Funct Anal 282(2):109290, 2022). 

   more » « less