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)

   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 polynomialmore »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.

   « 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)

   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.
3. Algorithms for covering multiple submodular constraints and applications

   https://doi.org/10.1007/s10878-022-00874-x  

   Chekuri, Chandra ; Inamdar, Tanmay ; Quanrud, Kent ; Varadarajan, Kasturi ; Zhang, Zhao ( June 2022 , Journal of Combinatorial Optimization)

   We consider the problem of covering multiple submodular constraints. Given a finite ground setN, a weight function$$w: N \rightarrow \mathbb {R}_+$$$w:N\to R_{+}$,rmonotone submodular functions$$f_1,f_2,\ldots ,f_r$$$f_1,f_2,\dots ,f_r$overNand requirements$$k_1,k_2,\ldots ,k_r$$$k_1,k_2,\dots ,k_r$the goal is to find a minimum weight subset$$S \subseteq N$$$S\subseteq N$such that$$f_i(S) \ge k_i$$$f_i\left(S\right)\ge k_i$for$$1 \le i \le r$$$1\le i\le r$. We refer to this problem asMulti-Submod-Coverand it was recently considered by Har-Peled and Jones (Few cuts meet many point sets. CoRR.arxiv:abs1808.03260Har-Peled and Jones 2018) who were motivated by an application in geometry. Even with$$r=1$$$r=1$Multi-Submod-Covergeneralizes the well-known Submodular Set Cover problem (Submod-SC), and it can also be easily reduced toSubmod-SC. A simple greedy algorithm gives an$$O(\log (kr))$$$O(log(kr\left)\right)$approximation where$$k = \sum _i k_i$$$k={\sum }_i{k}_i$and this ratio cannot be improved in the general case. In this paper, motivated by several concrete applications, we consider two ways to improve upon the approximation given by the greedy algorithm. First, we give a bicriteria approximation algorithm forMulti-Submod-Coverthat covers each constraint to within a factor of$$(1-1/e-\varepsilon )$$$(1-1/e-\epsilon )$while incurring an approximation of$$O(\frac{1}{\epsilon }\log r)$$$O(\frac{1}{ϵ}logr)$in the cost. Second, we consider the special case when each$$f_i$$$f_i$is a obtained from a truncated coverage function and obtain an algorithm that generalizes previous work on partial set cover (Partial-SC), covering integer programs (CIPs) and multiple vertex cover constraintsmore »Bera et al. (Theoret Comput Sci 555:2–8 Bera et al. 2014). Both these algorithms are based on mathematical programming relaxations that avoid the limitations of the greedy algorithm. We demonstrate the implications of our algorithms and related ideas to several applications ranging from geometric covering problems to clustering with outliers. Our work highlights the utility of the high-level model and the lens of submodularity in addressing this class of covering problems.

   « less
4. The Direct-method Oxygen Abundance of Typical Dwarf Galaxies at Cosmic High Noon∗

   https://doi.org/10.3847/1538-4357/acb153  

   Gburek, Timothy ; Siana, Brian ; Alavi, Anahita ; Emami, Najmeh ; Richard, Johan ; Freeman, William R. ; Stark, Daniel P. ; Snapp-Kolas, Christopher ( May 2023 , The Astrophysical Journal)

   We present a Keck/MOSFIRE rest-optical composite spectrum of 16 typical gravitationally lensed star-forming dwarf galaxies at 1.7 ≲z≲ 2.6 (z_mean= 2.30), all chosen independent of emission-line strength. These galaxies have a median stellar mass of$\log {(M_{*}/M_{\odot })}_{\mathrm{med}}={8.29}_{-0.43}^{+0.51}$and a median star formation rate of${\mathrm{S}\mathrm{F}\mathrm{R}}_{\mathrm{H}\alpha }^{\mathrm{m}\mathrm{e}\mathrm{d}}={2.25}_{-1.26}^{+2.15}{M}_{\odot }{\mathrm{y}\mathrm{r}}^{-1}$. We measure the faint electron-temperature-sensitive [Oiii]λ4363 emission line at 2.5σ(4.1σ) significance when considering a bootstrapped (statistical-only) uncertainty spectrum. This yields a direct-method oxygen abundance of$12+\log {(\mathrm{O}/\mathrm{H})}_{\mathrm{direct}}={7.88}_{-0.22}^{+0.25}$(${0.15}_{-0.06}^{+0.12}{Z}_{\odot }$). We investigate the applicability at highzof locally calibrated oxygen-based strong-line metallicity relations, finding that the local reference calibrations of Bian et al. best reproduce (≲0.12 dex) our composite metallicity at fixed strong-line ratio. At fixedM_*, our composite is well represented by thez∼ 2.3 direct-method stellar mass—gas-phase metallicity relation (MZR) of Sanders et al. When comparing to predicted MZRs from the IllustrisTNG and FIRE simulations, having recalculated our stellar masses with more realistic nonparametric star formation histories$(\log {(M_{*}/M_{\odot })}_{\mathrm{med}}={8.92}_{-0.22}^{+0.31})$, we find excellent agreement with the FIRE MZR. Our composite is consistent with no metallicity evolution, atmore »fixedM_*and SFR, of the locally defined fundamental metallicity relation. We measure the doublet ratio [Oii]λ3729/[Oii]λ3726 = 1.56 ± 0.32 (1.51 ± 0.12) and a corresponding electron density of$n_e=1_{-0}^{+215}{\mathrm{cm}}^{-3}$($n_e=1_{-0}^{+74}{\mathrm{cm}}^{-3}$) when considering the bootstrapped (statistical-only) error spectrum. This result suggests that lower-mass galaxies have lower densities than higher-mass galaxies atz∼ 2.

   « less
5. A database of calculated solution parameters for the AlphaFold predicted protein structures

   https://doi.org/10.1038/s41598-022-10607-z  

   Brookes, Emre ; Rocco, Mattia ( May 2022 , Scientific Reports)

   Recent spectacular advances by AI programs in 3D structure predictions from protein sequences have revolutionized the field in terms of accuracy and speed. The resulting “folding frenzy” has already produced predicted protein structure databases for the entire human and other organisms’ proteomes. However, rapidly ascertaining a predicted structure’s reliability based on measured properties in solution should be considered. Shape-sensitive hydrodynamic parameters such as the diffusion and sedimentation coefficients ($${D_{t(20,w)}^{0}}$$$D_{t(20,w)}^0$,$${s_{{\left( {{20},w} \right)}}^{{0}} }$$$s_{\left(20,w\right)}^0$) and the intrinsic viscosity ([η]) can provide a rapid assessment of the overall structure likeliness, and SAXS would yield the structure-related pair-wise distance distribution functionp(r) vs.r. Using the extensively validated UltraScan SOlution MOdeler (US-SOMO) suite, a database was implemented calculating from AlphaFold structures the corresponding$${D_{t(20,w)}^{0}}$$$D_{t(20,w)}^0$,$${s_{{\left( {{20},w} \right)}}^{{0}} }$$$s_{\left(20,w\right)}^0$, [η],p(r) vs.r, and other parameters. Circular dichroism spectra were computed using the SESCA program. Some of AlphaFold’s drawbacks were mitigated, such as generating whenever possible a protein’s mature form. Others, like the AlphaFold direct applicability to single-chain structures only, the absence of prosthetic groups, or flexibility issues, are discussed. Overall, this implementation of the US-SOMO-AF database should already aid in rapidly evaluating the consistency in solution of a relevant portion of AlphaFold predicted protein structures.