More Like this

1. Online Paging with Heterogeneous Cache Slots

   https://doi.org/10.1007/s00453-024-01270-z  

   Chrobak, Marek; Haney, Samuel; Liaee, Mehraneh; Panigrahi, Debmalya; Rajaraman, Rajmohan; Sundaram, Ravi; Young, Neal_E (October 2024, Algorithmica)

   Abstract It is natural to generalize the online$$k$$ $k$-Server problem by allowing each request to specify not only a pointp, but also a subsetSof servers that may serve it. To date, only a few special cases of this problem have been studied. The objective of the work presented in this paper has been to more systematically explore this generalization in the case of uniform and star metrics. For uniform metrics, the problem is equivalent to a generalization of Paging in which each request specifies not only a pagep, but also a subsetSof cache slots, and is satisfied by having a copy ofpin some slot inS. We call this problemSlot-Heterogenous Paging. In realistic settings only certain subsets of cache slots or servers would appear in requests. Therefore we parameterize the problem by specifying a family$${\mathcal {S}}\subseteq 2^{[k]}$$ $S\subseteq 2^{\left[k\right]}$of requestable slot sets, and we establish bounds on the competitive ratio as a function of the cache sizekand family$${\mathcal {S}}$$ $S$:If all request sets are allowed ($${\mathcal {S}}=2^{[k]}\setminus \{\emptyset \}$$ $S=2^{\left[k\right]}\backslash \left\{\varnothing \right\}$), the optimal deterministic and randomized competitive ratios are exponentially worse than for standard Paging ($${\mathcal {S}}=\{[k]\}$$ $S=\left\{\right[k\left]\right\}$).As a function of$$|{\mathcal {S}}|$$ $\left|S\right|$andk, the optimal deterministic ratio is polynomial: at most$$O(k^2|{\mathcal {S}}|)$$ $O\left(k^2\right|S\left|\right)$and at least$$\Omega (\sqrt{|{\mathcal {S}}|})$$ $\Omega \left(\sqrt{\left|S\right|}\right)$.For any laminar family$${\mathcal {S}}$$ $S$of heighth, the optimal ratios areO(hk) (deterministic) and$$O(h^2\log k)$$ $O(h^{2}logk)$(randomized).The special case of laminar$${\mathcal {S}}$$ $S$that we callAll-or-One Pagingextends standard Paging by allowing each request to specify a specific slot to put the requested page in. The optimal deterministic ratio forweightedAll-or-One Paging is$$\Theta (k)$$ $\Theta \left(k\right)$. Offline All-or-One Paging is$$\mathbb{N}\mathbb{P}$$ $NP$-hard.Some results for the laminar case are shown via a reduction to the generalization of Paging in which each request specifies a set$$P$$ $P$ofpages, and is satisfied by fetching any page from$$P$$ $P$into the cache. The optimal ratios for the latter problem (with laminar family of heighth) are at mosthk(deterministic) and$$hH_k$$ $h{H}_k$(randomized). 

   more » « less
2. Ordinary modules for vertex algebras of 𝔬𝔰𝔭 _1|2𝑛

   https://doi.org/10.1515/crelle-2024-0060  

   Creutzig, Thomas; Genra, Naoki; Linshaw, Andrew (August 2024, Journal für die reine und angewandte Mathematik (Crelles Journal))

   Abstract We show that the affine vertex superalgebra $V^k\left(\mathfrak{o}\mathfrak{s}{\mathfrak{p}}_{1|2n}\right)$V^{k}(\mathfrak{osp}_{1|2n})at generic level 𝑘 embeds in the equivariant 𝒲-algebra of $\mathfrak{s}{\mathfrak{p}}_{2n}$\mathfrak{sp}_{2n}times $4n$4nfree fermions.This has two corollaries:(1) it provides a new proof that, for generic 𝑘, the coset $\mathrm{Com}(V^k\left(\mathfrak{s}{\mathfrak{p}}_{2n}\right),V^k\left(\mathfrak{o}\mathfrak{s}{\mathfrak{p}}_{1|2n}\right))$\operatorname{Com}(V^{k}(\mathfrak{sp}_{2n}),V^{k}(\mathfrak{osp}_{1|2n}))is isomorphic to ${\mathcal{W}}^{\mathrm{\ell }}\left(\mathfrak{s}{\mathfrak{p}}_{2n}\right)$\mathcal{W}^{\ell}(\mathfrak{sp}_{2n})for $\mathrm{\ell }=-\left(n+1\right)+\left(k+n+1\right)/\left(2k+2n+1\right)$\ell=-(n+1)+(k+n+1)/(2k+2n+1), and(2) we obtain the decomposition of ordinary $V^k\left(\mathfrak{o}\mathfrak{s}{\mathfrak{p}}_{1|2n}\right)$V^{k}(\mathfrak{osp}_{1|2n})-modules into $V^k\left(\mathfrak{s}{\mathfrak{p}}_{2n}\right)\otimes {\mathcal{W}}^{\mathrm{\ell }}\left(\mathfrak{s}{\mathfrak{p}}_{2n}\right)$V^{k}(\mathfrak{sp}_{2n})\otimes\mathcal{W}^{\ell}(\mathfrak{sp}_{2n})-modules.Next, if 𝑘 is an admissible level and ℓ is a non-degenerate admissible level for $\mathfrak{s}{\mathfrak{p}}_{2n}$\mathfrak{sp}_{2n}, we show that the simple algebra $L_k\left(\mathfrak{o}\mathfrak{s}{\mathfrak{p}}_{1|2n}\right)$L_{k}(\mathfrak{osp}_{1|2n})is an extension of the simple subalgebra $L_k\left(\mathfrak{s}{\mathfrak{p}}_{2n}\right)\otimes {\mathcal{W}}_{\mathrm{\ell }}\left(\mathfrak{s}{\mathfrak{p}}_{2n}\right)$L_{k}(\mathfrak{sp}_{2n})\otimes{\mathcal{W}}_{\ell}(\mathfrak{sp}_{2n}).Using the theory of vertex superalgebra extensions, we prove that the category of ordinary $L_k\left(\mathfrak{o}\mathfrak{s}{\mathfrak{p}}_{1|2n}\right)$L_{k}(\mathfrak{osp}_{1|2n})-modules is a semisimple, rigid vertex tensor supercategory with only finitely many inequivalent simple objects.It is equivalent to a certain subcategory of ${\mathcal{W}}_{\mathrm{\ell }}\left(\mathfrak{s}{\mathfrak{p}}_{2n}\right)$\mathcal{W}_{\ell}(\mathfrak{sp}_{2n})-modules.A similar result also holds for the category of Ramond twisted modules.Due to a recent theorem of Robert McRae, we get as a corollary that categories of ordinary $L_k\left(\mathfrak{s}{\mathfrak{p}}_{2n}\right)$L_{k}(\mathfrak{sp}_{2n})-modules are rigid. 

   more » « less
3. Stochastic dual dynamic programming for multistage stochastic mixed-integer nonlinear optimization

   https://doi.org/10.1007/s10107-022-01875-8  

   Zhang, Shixuan; Sun, Xu Andy (August 2022, Mathematical Programming)

   Abstract In this paper, we study multistage stochastic mixed-integer nonlinear programs (MS-MINLP). This general class of problems encompasses, as important special cases, multistage stochastic convex optimization withnon-Lipschitzianvalue functions and multistage stochastic mixed-integer linear optimization. We develop stochastic dual dynamic programming (SDDP) type algorithms with nested decomposition, deterministic sampling, and stochastic sampling. The key ingredient is a new type of cuts based on generalized conjugacy. Several interesting classes of MS-MINLP are identified, where the new algorithms are guaranteed to obtain the global optimum without the assumption of complete recourse. This significantly generalizes the classic SDDP algorithms. We also characterize the iteration complexity of the proposed algorithms. In particular, for a$$(T+1)$$ $(T+1)$-stage stochastic MINLP satisfyingL-exact Lipschitz regularization withd-dimensional state spaces, to obtain an$$\varepsilon $$ $\epsilon$-optimal root node solution, we prove that the number of iterations of the proposed deterministic sampling algorithm is upper bounded by$${\mathcal {O}}((\frac{2LT}{\varepsilon })^d)$$ $O\left({\left(\frac{2LT}{\epsilon }\right)}^d\right)$, and is lower bounded by$${\mathcal {O}}((\frac{LT}{4\varepsilon })^d)$$ $O\left({\left(\frac{\mathrm{LT}}{4\epsilon }\right)}^d\right)$for the general case or by$${\mathcal {O}}((\frac{LT}{8\varepsilon })^{d/2-1})$$ $O\left({\left(\frac{\mathrm{LT}}{8\epsilon }\right)}^{d/2-1}\right)$for the convex case. This shows that the obtained complexity bounds are rather sharp. It also reveals that the iteration complexity dependspolynomiallyon the number of stages. We further show that the iteration complexity dependslinearlyonT, if all the state spaces are finite sets, or if we seek a$$(T\varepsilon )$$ $\left(T\epsilon \right)$-optimal solution when the state spaces are infinite sets, i.e. allowing the optimality gap to scale withT. To the best of our knowledge, this is the first work that reports global optimization algorithms as well as iteration complexity results for solving such a large class of multistage stochastic programs. The iteration complexity study resolves a conjecture by the late Prof. Shabbir Ahmed in the general setting of multistage stochastic mixed-integer optimization. 

   more » « less
4. Levin-Wen is a Gauge Theory: Entanglement from Topology

   https://doi.org/10.1007/s00220-024-05144-x  

   Kawagoe, Kyle; Jones, Corey; Sanford, Sean; Green, David; Penneys, David (October 2024, Communications in Mathematical Physics)

   Abstract We show that the Levin-Wen model of a unitary fusion category$${\mathcal {C}}$$ $C$is a gauge theory with gauge symmetry given by the tube algebra$${\text {Tube}}({\mathcal {C}})$$ $\text{Tube}\left(C\right)$. In particular, we define a model corresponding to a$${\text {Tube}}({\mathcal {C}})$$ $\text{Tube}\left(C\right)$symmetry protected topological phase, and we provide a gauging procedure which results in the corresponding Levin-Wen model. In the case$${\mathcal {C}}=\textsf{Hilb}(G,\omega )$$ $C=\mathrm{Hilb}(G,\omega )$, we show how our procedure reduces to the twisted gauging of a trivalG-SPT to produce the Twisted Quantum Double. We further provide an example which is outside the bounds of the current literature, the trivial Fibbonacci SPT, whose gauge theory results in the doubled Fibonacci string-net. Our formalism has a natural topological interpretation with string diagrams living on a punctured sphere. We provide diagrams to supplement our mathematical proofs and to give the reader an intuitive understanding of the subject matter. 

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