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 stable exotic Cuntz algebras are higher-rank graph algebras

   https://doi.org/10.1090/bproc/180  

   Boersema, Jeffrey ; Browne, Sarah ; Gillaspy, Elizabeth ( March 2024 , Proceedings of the American Mathematical Society, Series B)

   For each odd integer$n \geq 3$, we construct a rank-3 graph$\Lambda _n$with involution$\gamma _n$whose real$C^*$-algebra$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda _n, \gamma _n)$is stably isomorphic to the exotic Cuntz algebra$\mathcal E_n$. This construction is optimal, as we prove that a rank-2 graph with involution$(\Lambda ,\gamma )$can never satisfy$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )\sim _{ME} \mathcal E_n$, and Boersema reached the same conclusion for rank-1 graphs (directed graphs) in [Münster J. Math.10(2017), pp. 485–521, Corollary 4.3]. Our construction relies on a rank-1 graph with involution$(\Lambda , \gamma )$whose real$C^*$-algebra$C^*_{\scriptscriptstyle \mathbb {R}}(\Lambda , \gamma )$is stably isomorphic to the suspension$S \mathbb {R}$. In the Appendix, we show that the$i$-fold suspension$S^i \mathbb {R}$is stably isomorphic to a graph algebra iff$-2 \leq i \leq 1$.

    

   more » « less
4. Surface Houghton groups

   https://doi.org/10.1007/s00208-023-02751-2  

   Aramayona, Javier ; Bux, Kai-Uwe ; Kim, Heejoung ; Leininger, Christopher J. ( November 2023 , Mathematische Annalen)

   For every$$n\ge 2$$$n\ge 2$, thesurface Houghton group$${\mathcal {B}}_n$$$B_n$is defined as the asymptotically rigid mapping class group of a surface with exactlynends, all of them non-planar. The groups$${\mathcal {B}}_n$$$B_n$are analogous to, and in fact contain, the braided Houghton groups. These groups also arise naturally in topology: every monodromy homeomorphism of a fibered component of a depth-1 foliation of closed 3-manifold is conjugate into some$${\mathcal {B}}_n$$$B_n$. As countable mapping class groups of infinite type surfaces, the groups$$\mathcal {B}_n$$$B_n$lie somewhere between classical mapping class groups and big mapping class groups. We initiate the study of surface Houghton groups proving, among other things, that$$\mathcal {B}_n$$$B_n$is of type$$\text {F}_{n-1}$$${\text{F}}_{n-1}$, but not of type$$\text {FP}_{n}$$${\text{FP}}_n$, analogous to the braided Houghton groups.

    

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