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. Analytical Model of Disk Evaporation and State Transitions in Accreting Black Holes

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

   Cho 조, Hyerin 혜린 ; Narayan, Ramesh ( June 2022 , The Astrophysical Journal)

   State transitions in black hole X-ray binaries are likely caused by gas evaporation from a thin accretion disk into a hot corona. We present a height-integrated version of this process, which is suitable for analytical and numerical studies. With radiusrscaled to Schwarzschild units and coronal mass accretion rate${\dot{m}}_c$to Eddington units, the results of the model are independent of black hole mass. State transitions should thus be similar in X-ray binaries and an active galactic nucleus. The corona solution consists of two power-law segments separated at a break radiusr_b∼ 10³(α/0.3)⁻², whereαis the viscosity parameter. Gas evaporates from the disk to the corona forr>r_b, and condenses back forr<r_b. Atr_b,${\dot{m}}_c$reaches its maximum,${\dot{m}}_{c,\max }\approx 0.02{(\alpha /0.3)}^3$. If atr≫r_bthe thin disk accretes with${\dot{m}}_d<{\dot{m}}_{c,\max }$, then the disk evaporates fully before reachingr_b, giving the hard state. Otherwise, the disk survives at all radii, giving the thermal state. While the basic model considers only bremsstrahlung cooling and viscous heating, we also discuss a more realistic model that includes Compton cooling and direct coronal heating by energy transport from the disk. Solutions are again independent of black hole mass, andr_bremains unchanged. This model predicts strong coronal winds forr>r_b, and aT∼ 5 × 10⁸K Compton-cooled corona forr<r_b. Two-temperature effects are ignored, but may be important at small radii.

    

   more » « less
3. QLBT: a linear Boltzmann transport model for heavy quarks in a quark-gluon plasma of quasi-particles

   https://doi.org/10.1140/epjc/s10052-022-10308-x  

   Liu, Feng-Lei ; Xing, Wen-Jing ; Wu, Xiang-Yu ; Qin, Guang-You ; Cao, Shanshan ; Wang, Xin-Nian ( April 2022 , The European Physical Journal C)

   We develop a new heavy quark transport model, QLBT, to simulate the dynamical propagation of heavy quarks inside the quark-gluon plasma (QGP) created in relativistic heavy-ion collisions. Our QLBT model is based on the linear Boltzmann transport (LBT) model with the ideal QGP replaced by a collection of quasi-particles to account for the non-perturbative interactions among quarks and gluons of the hot QGP. The thermal masses of quasi-particles are fitted to the equation of state from lattice QCD simulations using the Bayesian statistical analysis method. Combining QLBT with our advanced hybrid fragmentation-coalescence hadronization approach, we calculate the nuclear modification factor$$R_\mathrm {AA}$$$R_{\mathrm{AA}}$and the elliptic flow$$v_2$$$v_2$ofDmesons at the Relativistic Heavy-Ion Collider and the Large Hadron Collider. By comparing our QLBT calculation to the experimental data on theDmeson$$R_\mathrm {AA}$$$R_{\mathrm{AA}}$and$$v_2$$$v_2$, we extract the heavy quark transport parameter$$\hat{q}$$$\hat{q}$and diffusion coefficient$$D_\mathrm {s}$$$D_s$in the temperature range of$$1-4~T_\mathrm {c}$$$1-4T_c$, and compare them with the lattice QCD results and other phenomenological studies.

    

   more » « less
4. The Brown measure of the free multiplicative Brownian motion

   https://doi.org/10.1007/s00440-022-01142-z  

   Driver, Bruce K. ; Hall, Brian ; Kemp, Todd ( October 2022 , Probability Theory and Related Fields)

   The free multiplicative Brownian motion$$b_{t}$$$b_t$is the large-Nlimit of the Brownian motion on$$\mathsf {GL}(N;\mathbb {C}),$$$\mathrm{GL}(N;C),$in the sense of$$*$$$\ast$-distributions. The natural candidate for the large-Nlimit of the empirical distribution of eigenvalues is thus the Brown measure of$$b_{t}$$$b_t$. In previous work, the second and third authors showed that this Brown measure is supported in the closure of a region$$\Sigma _{t}$$${\Sigma }_t$that appeared in the work of Biane. In the present paper, we compute the Brown measure completely. It has a continuous density$$W_{t}$$$W_t$on$$\overline{\Sigma }_{t},$$${\overline{\Sigma }}_t,$which is strictly positive and real analytic on$$\Sigma _{t}$$${\Sigma }_t$. This density has a simple form in polar coordinates:$$\begin{aligned} W_{t}(r,\theta )=\frac{1}{r^{2}}w_{t}(\theta ), \end{aligned}$$$\begin{array}{c}{W}_t(r,\theta )=\frac{1}{r^2}{w}_t\left(\theta \right),\end{array}$where$$w_{t}$$$w_t$is an analytic function determined by the geometry of the region$$\Sigma _{t}$$${\Sigma }_t$. We show also that the spectral measure of free unitary Brownian motion$$u_{t}$$$u_t$is a “shadow” of the Brown measure of$$b_{t}$$$b_t$, precisely mirroring the relationship between the circular and semicircular laws. We develop several new methods, based on stochastic differential equations and PDE, to prove these results.

    

   more » « less
5. Analytic genericity of diffusing orbits in a priori unstable Hamiltonian systems

   https://doi.org/10.1088/1361-6544/ac50bb  

   Chen, Qinbo ; de la Llave, Rafael ( March 2022 , Nonlinearity)

   The genericity of Arnold diffusion in the analytic category is an open problem. In this paper, we study this problem in the followinga prioriunstable Hamiltonian system with a time-periodic perturbation${\mathcal{H}}_{\epsilon }(p,q,I,\phi ,t)=h(I)+\sum _{i=1}^n\pm \left(\frac{1}{2}{p}_i^2+V_i(q_i)\right)+\epsilon H_1(p,q,I,\phi ,t),$where$(p,q)\in {\mathbb{R}}^n\times {\mathbb{T}}^n$,$(I,\phi )\in {\mathbb{R}}^d\times {\mathbb{T}}^d$withn,d⩾ 1,V_iare Morse potentials, andɛis a small non-zero parameter. The unperturbed Hamiltonian is not necessarily convex, and the induced inner dynamics does not need to satisfy a twist condition. Using geometric methods we prove that Arnold diffusion occurs for generic analytic perturbationsH₁. Indeed, the set of admissibleH₁isC^ωdense andC³open (a fortiori,C^ωopen). Our perturbative technique for the genericity is valid in theC^ktopology for allk∈ [3, ∞) ∪ {∞,ω}.

    

   more » « less