Gauge/gravity duality and the interplay of various fractional branes

We consider different types of fractional branes on a Z2 orbifold of the conifold and analyze in detail the corresponding gauge/gravity duality. The gauge theory possesses a rich and varied dynamics, both in the UV and in the IR. We find the dual supergravity solution, which contains both untwisted and twisted 3-form fluxes, related to what are known as deformation and N=2 fractional branes, respectively. We analyze the resulting renormalization group flow from the supergravity perspective, by developing an algorithm to easily extract it. We find hints of a generalization of the familiar cascade of Seiberg dualities due to a nontrivial interplay between the different types of fractional branes. We finally consider the IR behavior in several limits, where the dominant effective dynamics is either confining in a Coulomb phase or runaway, and discuss the resolution of singularities in the dual geometric background. © 2008 The American Physical Society.

A note on spin-s duality

Duality is investigated for higher spin (s ≥ 2), free, massless, bosonic gauge fields. We show how the dual formulations can be derived from a common "parent", first-order action. This goes beyond most of the previous treatments where higher-spin duality was investigated at the level of the equations of motion only. In D = 4 spacetime dimensions, the dual theories turn out to be described by the same Pauli-Fierz (s = 2) or Fronsdal (s ≥ 3) action (as it is the case for spin 1). In the particular s = 2 D = 5 case, the Pauli-Fierz action and the Curtright action are shown to be related through duality. A crucial ingredient of the analysis is given by the first-order, gauge-like, reformulation of higher spin theories due to Vasiliev. © SISSA/ISAS 2003.

Sorting under partial information (without the ellipsoid algorithm)

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: an O(n2) algorithm performing O(log n·log e(P)) comparisons; an O(n2.5) algorithm performing at most (1+ε) log e(P) + Oε(n) comparisons; an O(n2.5) algorithm performing O(log e(P)) comparisons. All our algorithms are simple to implement. © 2010 ACM.