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 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. Plasmonically enhanced mid-IR light source based on tunable spectrally and directionally selective thermal emission from nanopatterned graphene

   https://doi.org/10.1038/s41598-020-73582-3  

   Shabbir, Muhammad Waqas ; Leuenberger, Michael N. ( October 2020 , Scientific Reports)

   We present a proof of concept for a spectrally selective thermal mid-IR source based on nanopatterned graphene (NPG) with a typical mobility of CVD-grown graphene (up to 3000$$\hbox {cm}^2\,\hbox {V}^{-1}\,\hbox {s}^{-1}$$${\text{cm}}^2{\text{V}}^{-1}{\text{s}}^{-1}$), ensuring scalability to large areas. For that, we solve the electrostatic problem of a conducting hyperboloid with an elliptical wormhole in the presence of anin-planeelectric field. The localized surface plasmons (LSPs) on the NPG sheet, partially hybridized with graphene phonons and surface phonons of the neighboring materials, allow for the control and tuning of the thermal emission spectrum in the wavelength regime from$$\lambda =3$$$\lambda =3$to 12$$\upmu$$$\mu$m by adjusting the size of and distance between the circular holes in a hexagonal or square lattice structure. Most importantly, the LSPs along with an optical cavity increase the emittance of graphene from about 2.3% for pristine graphene to 80% for NPG, thereby outperforming state-of-the-art pristine graphene light sources operating in the near-infrared by at least a factor of 100. According to our COMSOL calculations, a maximum emission power per area of$$11\times 10^3$$$11\times {10}^3$W/$$\hbox {m}^2$$${\text{m}}^2$at$$T=2000$$$T=2000$K for a bias voltage of$$V=23$$$V=23$V is achieved by controlling the temperature of the hot electrons through the Joule heating. By generalizing Planck’s theory to any grey body and deriving the completely general nonlocal fluctuation-dissipation theorem with nonlocal response of surface plasmons in the random phase approximation, we show that the coherence length of the graphene plasmons and the thermally emitted photons can be as large as 13$$\upmu$$$\mu$m and 150$$\upmu$$$\mu$m, respectively, providing the opportunity to create phased arrays made of nanoantennas represented by the holes in NPG. The spatial phase variation of the coherence allows for beamsteering of the thermal emission in the range between$$12^\circ$$${12}^{\circ }$and$$80^\circ$$${80}^{\circ }$by tuning the Fermi energy between$$E_F=1.0$$$E_F=1.0$eV and$$E_F=0.25$$$E_F=0.25$eV through the gate voltage. Our analysis of the nonlocal hydrodynamic response leads to the conjecture that the diffusion length and viscosity in graphene are frequency-dependent. Using finite-difference time domain calculations, coupled mode theory, and RPA, we develop the model of a mid-IR light source based on NPG, which will pave the way to graphene-based optical mid-IR communication, mid-IR color displays, mid-IR spectroscopy, and virus detection.

    

   more » « less
3. The Ionization and Dynamics of the Makani Galactic Wind

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

   Rupke, David S. ; Coil, Alison L. ; Perrotta, Serena ; Davis, Julie D. ; Diamond-Stanic, Aleksandar M. ; Geach, James E. ; Hickox, Ryan C. ; Moustakas, John ; Petter, Grayson C. ; Rudnick, Gregory H. ; et al ( April 2023 , The Astrophysical Journal)

   The Makani galaxy hosts the poster child of a galactic wind on scales of the circumgalactic medium. It consists of a two-episode wind in which the slow, outer wind originated 400 Myr ago (Episode I;R_I= 20 − 50 kpc) and the fast, inner wind is 7 Myr old (Episode II;R_II= 0 − 20 kpc). While this wind contains ionized, neutral, and molecular gas, the physical state and mass of the most extended phase—the warm, ionized gas—are unknown. Here we present Keck optical spectra of the Makani outflow. These allow us to detect hydrogen lines out tor= 30–40 kpc and thus constrain the mass, momentum, and energy in the wind. Many collisionally excited lines are detected throughout the wind, and their line ratios are consistent with 200–400 km s⁻¹shocks that power the ionized gas, withv_shock=σ_wind. Combining shock models, density-sensitive line ratios, and mass and velocity measurements, we estimate that the ionized mass and outflow rate in the Episode II wind could be as high as those of the molecular gas:$M_{\mathrm{II}}^{\mathrm{H}\mathrm{II}}\sim M_{\mathrm{II}}^{{\mathrm{H}}_2}=(1-2)\times {10}^9{M}_{\odot }$and$\mathit{dM}/{\mathit{dt}}_{\mathrm{II}}^{\mathrm{H}\mathrm{II}}\sim \mathit{dM}/{\mathit{dt}}_{\mathrm{II}}^{{\mathrm{H}}_2}=170-250M_{\odot }$yr⁻¹. The outer wind has slowed, so that$\mathit{dM}/{\mathit{dt}}_{\mathrm{I}}^{\mathrm{H}\mathrm{II}}\sim 10M_{\odot }$yr⁻¹, but it contains more ionized gas,$M_{\mathrm{I}}^{\mathrm{H}\mathrm{II}}=5\times {10}^9$M_⊙. The momentum and energy in the recent Episode II wind imply a momentum-driven flow (p“boost” ∼7) driven by the hot ejecta and radiation pressure from the Eddington-limited, compact starburst. Much of the energy and momentum in the older Episode I wind may reside in a hotter phase, or lie further into the circumgalactic medium.

    

   more » « less
4. Evidence for AGN-regulated Cooling in Clusters at z ∼ 1.4: A Multiwavelength View of SPT-CL J0607-4448

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

   Masterson, Megan ; McDonald, Michael ; Ansarinejad, Behzad ; Bayliss, Matthew ; Benson, Bradford A. ; Bleem, Lindsey E. ; Calzadilla, Michael S. ; Edge, Alastair C. ; Floyd, Benjamin ; Kim, Keunho J. ; et al ( February 2023 , The Astrophysical Journal)

   We present a multiwavelength analysis of the galaxy cluster SPT-CL J0607-4448 (SPT0607), which is one of the most distant clusters discovered by the South Pole Telescope atz= 1.4010 ± 0.0028. The high-redshift cluster shows clear signs of being relaxed with well-regulated feedback from the active galactic nucleus (AGN) in the brightest cluster galaxy (BCG). Using Chandra X-ray data, we construct thermodynamic profiles and determine the properties of the intracluster medium. The cool-core nature of the cluster is supported by a centrally peaked density profile and low central entropy ($K_0={18}_{-9}^{+11}$keV cm²), which we estimate assuming an isothermal temperature profile due to the limited spectral information given the distance to the cluster. Using the density profile and gas cooling time inferred from the X-ray data, we find a mass-cooling rate${\dot{M}}_{\mathrm{cool}}={100}_{-60}^{+90}{M}_{\odot }$yr⁻¹. From optical spectroscopy and photometry around the [Oii] emission line, we estimate that the BCG star formation rate is${\mathrm{SFR}}_{[\mathrm{O}\mathrm{II}]}={1.7}_{-0.6}^{+1.0}{M}_{\odot }$yr⁻¹, roughly two orders of magnitude lower than the predicted mass-cooling rate. In addition, using ATCA radio data at 2.1 GHz, we measure a radio jet power$P_{\mathrm{cav}}={3.2}_{-1.3}^{+2.1}\times {10}^{44}$erg s⁻¹, which is consistent with the X-ray cooling luminosity ($L_{\mathrm{cool}}={1.9}_{-0.5}^{+0.2}\times {10}^{44}$erg s⁻¹withinr_cool= 43 kpc). These findings suggest that SPT0607 is a relaxed, cool-core cluster with AGN-regulated cooling at an epoch shortly after cluster formation, implying that the balance between cooling and feedback can be reached quickly. We discuss the implications for these findings on the evolution of AGN feedback in galaxy clusters.

    

   more » « less
5. 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, at 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.

    

   more » « less