An official website of the United States government
A<sc>bstract</sc> We interpret appropriate families of Euclidean wormhole solutions of AdS3gravity in individual 2d CFTs as replica wormholes described by branching around the time-symmetric apparent horizons of black holes sourced by the backreaction of heavy point particles. These wormholes help describe a rich formalism to coarse grain pure states in 2d CFTs dual to the black hole geometries because the wormhole amplitudes match with the Renyi entropies of CFT states obtained by decohering the pure states in a specific way. This formalism can be generalised to coarse grain pure states in several copies of the CFT dual to multi-boundary black holes using wormhole solutions with higher genus boundaries using which we illustrate that coarse graining away the interior of multi-boundary black holes sets the mutual information between any two copies of the dual CFT to zero. Furthermore, this formalism of coarse graining pure states can be extended to decohere transition matrices between pure states which helps interpret more general families of wormhole solutions including those with non replica-symmetric boundary conditions in individual CFTs. The pseudo entropy of the decohered transition matrices has interesting holographic interpretation in terms of the area of minimal surfaces on appropriate black hole or wormhole geometries. The wormhole solutions which show up in the coarse graining formalism also compute the Renyi entropies of Hawking radiation after the Page time in a setup which generalizes the West Coast model to 3d gravity. Using this setup, we discuss the evaporation of one-sided black holes sourced by massive point particles and multi-boundary black holes in 3d gravity.
more »
« less
Discrete bulk reconstruction
A bstract According to the AdS/CFT correspondence , the geometries of certain spacetimes are fully determined by quantum states that live on their boundaries — indeed, by the von Neumann entropies of portions of those boundary states. This work investigates to what extent the geometries can be reconstructed from the entropies in polynomial time . Bouland, Fefferman, and Vazirani (2019) argued that the AdS/CFT map can be exponentially complex if one wants to reconstruct regions such as the interiors of black holes. Our main result provides a sort of converse: we show that, in the special case of a single 1D boundary divided into N “atomic regions”, if the input data consists of a list of entropies of contiguous boundary regions, and if the entropies satisfy a single inequality called Strong Subadditivity, then we can construct a graph model for the bulk in linear time. Moreover, the bulk graph is planar, it has O ( N 2 ) vertices (the information-theoretic minimum), and it’s “universal”, with only the edge weights depending on the specific entropies in question. From a combinatorial perspective, our problem boils down to an “inverse” of the famous min-cut problem: rather than being given a graph and asked to find a min-cut, here we’re given the values of min-cuts separating various sets of vertices, and need to find a weighted undirected graph consistent with those values. Our solution to this problem relies on the notion of a “bulkless” graph, which might be of independent interest for AdS/CFT. We also make initial progress on the case of multiple 1D boundaries — where the boundaries could be connected via wormholes — including an upper bound of O ( N 4 ) vertices whenever an embeddable bulk graph exists (thus putting the problem into the complexity class NP).
more »
« less
- Award ID(s):
- 2016245
- PAR ID:
- 10424824
- Date Published:
- Journal Name:
- Journal of High Energy Physics
- Volume:
- 2023
- Issue:
- 4
- ISSN:
- 1029-8479
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We give an algorithm to find a minimum cut in an edge-weighted directed graph with n vertices and m edges in O ̃(n · max{m^{2/3}, n}) time. This improves on the 30 year old bound of O ̃(nm) obtained by Hao and Orlin for this problem. Using similar techniques, we also obtain O ̃ (n^2 /ε^2 )-time (1+ε)-approximation algorithms for both the minimum edge and minimum vertex cuts in directed graphs, for any fixed ε. Before our work, no (1+ε)-approximation algorithm better than the exact runtime of O ̃(nm) is known for either problem. Our algorithms follow a two-step template. In the first step, we employ a partial sparsification of the input graph to preserve a critical subset of cut values approximately. In the second step, we design algorithms to find the (edge/vertex) mincut among the preserved cuts from the first step. For edge mincut, we give a new reduction to O ̃ (min{n/m^{1/3} , √n}) calls of any maxflow subroutine, via packing arborescences in the sparsifier. For vertex mincut, we develop new local flow algorithms to identify small unbalanced cuts in the sparsified graph.more » « less
-
null (Ed.)A bstract Using the fact that flat space with a boundary is related by a Weyl transformation to anti-de Sitter (AdS) space, one may study observables in boundary conformal field theory (BCFT) by placing a CFT in AdS. In addition to correlation functions of local operators, a quantity of interest is the free energy of the CFT computed on the AdS space with hyperbolic ball metric, i.e. with a spherical boundary. It is natural to expect that the AdS free energy can be used to define a quantity that decreases under boundary renormalization group flows. We test this idea by discussing in detail the case of the large N critical O ( N ) model in general dimension d , as well as its perturbative descriptions in the epsilon-expansion. Using the AdS approach, we recover the various known boundary critical behaviors of the model, and we compute the free energy for each boundary fixed point, finding results which are consistent with the conjectured F -theorem in a continuous range of dimensions. Finally, we also use the AdS setup to compute correlation functions and extract some of the BCFT data. In particular, we show that using the bulk equations of motion, in conjunction with crossing symmetry, gives an efficient way to constrain bulk two-point functions and extract anomalous dimensions of boundary operators.more » « less
-
A bstract We study the boundary critical behavior of conformal field theories of interacting fermions in the Gross-Neveu universality class. By a Weyl transformation, the problem can be studied by placing the CFT in an anti de Sitter space background. After reviewing some aspects of free fermion theories in AdS, we use both large N methods and the epsilon expansion near 2 and 4 dimensions to study the conformal boundary conditions in the Gross-Neveu CFT. At large N and general dimension d , we find three distinct boundary conformal phases. Near four dimensions, where the CFT is described by the Wilson-Fisher fixed point of the Gross-Neveu-Yukawa model, two of these phases correspond respectively to the choice of Neumann or Dirichlet boundary condition on the scalar field, while the third one corresponds to the case where the bulk scalar field acquires a classical expectation value. One may flow between these boundary critical points by suitable relevant boundary deformations. We compute the AdS free energy on each of them, and verify that its value is consistent with the boundary version of the F-theorem. We also compute some of the BCFT observables in these theories, including bulk two-point functions of scalar and fermions, and four-point functions of boundary fermions.more » « less
-
null (Ed.)We consider the classical Minimum Balanced Cut problem: given a graph $$G$$, compute a partition of its vertices into two subsets of roughly equal volume, while minimizing the number of edges connecting the subsets. We present the first {\em deterministic, almost-linear time} approximation algorithm for this problem. Specifically, our algorithm, given an $$n$$-vertex $$m$$-edge graph $$G$$ and any parameter $$1\leq r\leq O(\log n)$$, computes a $$(\log m)^{r^2}$$-approximation for Minimum Balanced Cut on $$G$$, in time $$O\left ( m^{1+O(1/r)+o(1)}\cdot (\log m)^{O(r^2)}\right )$$. In particular, we obtain a $$(\log m)^{1/\epsilon}$$-approximation in time $$m^{1+O(1/\sqrt{\epsilon})}$$ for any constant $$\epsilon$$, and a $$(\log m)^{f(m)}$$-approximation in time $$m^{1+o(1)}$$, for any slowly growing function $$m$$. We obtain deterministic algorithms with similar guarantees for the Sparsest Cut and the Lowest-Conductance Cut problems. Our algorithm for the Minimum Balanced Cut problem in fact provides a stronger guarantee: it either returns a balanced cut whose value is close to a given target value, or it certifies that such a cut does not exist by exhibiting a large subgraph of $$G$$ that has high conductance. We use this algorithm to obtain deterministic algorithms for dynamic connectivity and minimum spanning forest, whose worst-case update time on an $$n$$-vertex graph is $$n^{o(1)}$$, thus resolving a major open problem in the area of dynamic graph algorithms. Our work also implies deterministic algorithms for a host of additional problems, whose time complexities match, up to subpolynomial in $$n$$ factors, those of known randomized algorithms. The implications include almost-linear time deterministic algorithms for solving Laplacian systems and for approximating maximum flows in undirected graphs.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1007/JHEP04(2023)037
