More Like this

1. Large charge ’t Hooft limit of $$ \mathcal{N} $$ = 4 super-Yang-Mills

   https://doi.org/10.1007/JHEP02(2024)047  

   Caetano, João; Komatsu, Shota; Wang, Yifan (February 2024, Journal of High Energy Physics)

   A<sc>bstract</sc> The planar integrability of$$ \mathcal{N} $$ $N$= 4 super-Yang-Mills (SYM) is the cornerstone for numerous exact observables. We show that the large charge sector of the SU(2)$$ \mathcal{N} $$ $N$= 4 SYM provides another interesting solvable corner which exhibits striking similarities despite being far from the planar limit. We study non-BPS operators obtained by small deformations of half-BPS operators withR-chargeJin the limitJ→ ∞ with$$ {\lambda}_J\equiv {g}_{\textrm{YM}}^2J/2 $$ ${\lambda }_J\equiv g_{\mathrm{YM}}^{2}J/2$fixed. The dynamics in thislarge charge ’t Hooft limitis constrained by a centrally-extended$$ \mathfrak{psu} $$ $\mathrm{psu}$(2|2)²symmetry that played a crucial role for the planar integrability. To the leading order in 1/J, the spectrum is fully fixed by this symmetry, manifesting the magnon dispersion relation familiar from the planar limit, while it is constrained up to a few constants at the next order. We also determine the structure constant of two large charge operators and the Konishi operator, revealing a rich structure interpolating between the perturbative series at weak coupling and the worldline instantons at strong coupling. In addition we compute heavy-heavy-light-light (HHLL) four-point functions of half-BPS operators in terms of resummed conformal integrals and recast them into an integral form reminiscent of the hexagon formalism in the planar limit. For general SU(N) gauge groups, we study integrated HHLL correlators by supersymmetric localization and identify a dual matrix model of sizeJ/2 that reproduces our large charge result atN= 2. Finally we discuss a relation to the physics on the Coulomb branch and explain how the dilaton Ward identity emerges from a limit of the conformal block expansion. We comment on generalizations including the large spin ’t Hooft limit, the combined largeN-largeJlimits, and applications to general$$ \mathcal{N} $$ $N$= 2 superconformal field theories. 

   more » « less
2. $$ \mathcal{N} $$ = 2 JT supergravity and matrix models

   https://doi.org/10.1007/JHEP12(2023)003  

   Turiaci, Gustavo J.; Witten, Edward (December 2023, Journal of High Energy Physics)

   A<sc>bstract</sc> Generalizing previous results for$$ \mathcal{N} $$ $N$= 0 and$$ \mathcal{N} $$ $N$= 1, we analyze$$ \mathcal{N} $$ $N$= 2 JT supergravity on asymptotically AdS₂spaces with arbitrary topology and show that this theory of gravity is dual, in a holographic sense, to a certain random matrix ensemble in which supermultiplets of differentR-charge are statistically independent and each is described by its own$$ \mathcal{N} $$ $N$= 2 random matrix ensemble. We also analyze the case with a time-reversal symmetry, either commuting or anticommuting with theR-charge. In order to compare supergravity to random matrix theory, we develop an$$ \mathcal{N} $$ $N$= 2 analog of the recursion relations for Weil-Petersson volumes originally discovered by Mirzakhani in the bosonic case. 

   more » « less
3. Topologically charged BPS microstates in AdS3/CFT2

   https://doi.org/10.1007/JHEP03(2025)069  

   Ardehali, Arash Arabi; Krishna, Hare (March 2025, Journal of High Energy Physics)

   A<sc>bstract</sc> In the standard$$ \mathcal{N} $$ $N$= (4, 4) AdS₃/CFT₂with sym^N(T⁴), as well as the$$ \mathcal{N} $$ $N$= (2, 2) Datta-Eberhardt-Gaberdiel variant with sym^N(T⁴/ℤ₂), supersymmetric index techniques have not been applied so far to the CFT states with target-space momentum or winding. We clarify that the difficulty lies in a central extension of the SUSY algebra in the momentum and winding sectors, analogous to the central extension on the Coulomb branch of 4d$$ \mathcal{N} $$ $N$= 2 gauge theories. We define modified helicity-trace indices tailored to the momentum and winding sectors, and use them for microstate counting of the corresponding bulk black holes. In the$$ \mathcal{N} $$ $N$= (4, 4) case we reproduce the microstate matching of Larsen and Martinec. In the$$ \mathcal{N} $$ $N$= (2, 2) case we resolve a previous mismatch with the Bekenstein-Hawking formula encountered in the topologically trivial sector by going to certain winding sectors. 

   more » « less
4. 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
5. Query-Efficient Algorithm to Find all Nash Equilibria in a Two-Player Zero-Sum Matrix Game

   https://doi.org/10.1145/3732787  

   Maiti, Arnab; Boczar, Ross; Jamieson, Kevin; Ratliff, Lillian (April 2025, ACM Transactions on Economics and Computation)

   We study the query complexity of finding the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \)in two-player zero-sum matrix games. Fearnley and Savani [18] showed that for any randomized algorithm, there exists ann×ninput matrix where it needs to queryΩ(n²) entries in expectation to compute asingleNash equilibrium. On the other hand, Bienstock et al. [5] showed that there is a special class of matrices for which one can queryO(n) entries and compute its set of all Nash equilibria. However, these results do not fully characterize the query complexity of finding the set of all Nash equilibria in two-player zero-sum matrix games. In this work, we characterize the query complexity of finding the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \)in terms of the number of rowsnof the input matrix\(A \in \mathbb {R}^{n \times n} \), row support size\(k_1 := |\bigcup \limits _{x \in \mathcal {X}_\ast } \text{supp}(x)| \), and column support size\(k_2 := |\bigcup \limits _{y \in \mathcal {Y}_\ast } \text{supp}(y)| \). We design a simple yet non-trivial randomized algorithm that returns the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \)by querying at mostO(nk⁵· polylog(n)) entries of the input matrix\(A \in \mathbb {R}^{n \times n} \)in expectation, wherek≔ max{k₁,k₂}. This upper bound is tight up to a factor of poly(k), as we show that for any randomized algorithm, there exists ann×ninput matrix with min {k₁,k₂} = 1, for which it needs to queryΩ(nk) entries in expectation in order to find the set of all Nash equilibria\(\mathcal {X}_\ast \times \mathcal {Y}_\ast \). 

   more » « less