
We propose a new approach for multiverse analysis based on computational
complexity, which leads to a new family of "computational" measure factors. By
defining a cosmology as a spacetime containing a vacuum with specified
properties (for example small cosmological constant) together with rules for
how time evolution will produce the vacuum, we can associate global time in a
multiverse with clock time on a supercomputer which simulates it. We argue for
a principle of "limited computational complexity" governing early universe
dynamics as simulated by this supercomputer, which translates to a global
measure for regulating the infinities of eternal inflation. The rules for time
evolution can be thought of as a search algorithm, whose details should be
constrained by a stronger principle of "minimal computational complexity."
Unlike previously studied global measures, ours avoids standard equilibrium
considerations and the wellknown problems of Boltzmann Brains and the
youngness paradox. We also give various definitions of the computational
complexity of a cosmology, and argue that there are only a few natural
complexity classes. (v2: version submitted for publication: clarified section
5.3; added references) (v3: added discussion of marginally hospitable vacua.
Version to appear in Annals of Physics)

We analyze the low temperature structure of a supersymmetric quiver quantum
mechanics with randomized superpotential coefficients, treating them as
quenched disorder. These theories describe features of the low energy dynamics
of wrapped branes, which in large number backreact into extremal black holes.
We show that the low temperature theory, in the limit of a large number of
bifundamentals, exhibits a time reparametrization symmetry as well as a
specific heat linear in the temperature. Both these features resemble the
behavior of black hole horizons in the zero temperature limit. We demonstrate
similarities between the low temperature physics of the random quiver model and
a theory of large $N$ free fermions with random masses.

We explore quantum mechanical theories whose fundamental degrees of freedom
are rectangular matrices with Grassmann valued matrix elements. We study
particular models where the low energy sector can be described in terms of a
bosonic Hermitian matrix quantum mechanics. We describe the classical curved
phase space that emerges in the low energy sector. The phase space lives on a
compact Kahler manifold parameterized by a complex matrix, of the type
discovered some time ago by Berezin. The emergence of a semiclassical bosonic
matrix quantum mechanics at low energies requires that the original Grassmann
matrices be in the long rectangular limit. We discuss possible holographic
interpretations of such matrix models which, by construction, are endowed with
a finite dimensional Hilbert space.

We present a new class of ${\cal N}=4$ supersymmetric quiver matrix models
and argue that it describes the stringy lowenergy dynamics of internally
wrapped Dbranes in fourdimensional antide Sitter (AdS) flux
compactifications. The Lagrangians of these models differ from previously
studied quiver matrix models by the presence of mass terms, associated with the
AdS gravitational potential, as well as additional terms dictated by
supersymmetry. These give rise to dynamical phenomena typically associated with
the presence of fluxes, such as fuzzy membranes, internal cyclotron motion and
the appearance of confining strings. We also show how these models can be
obtained by dimensional reduction of fourdimensional supersymmetric quiver
gauge theories on a threesphere.

We discuss further aspects of the higher spin dS/CFT correspondence. Using a
recent result of Dunne and Kirsten, it is shown how to numerically compute the
partition function of the free Sp(N) model for a large class of SO(3)
preserving deformations of the flat/round metric on R^3/S^3 and the source of
the spinzero singletrace operator dual to the bulk scalar. We interpret this
partition function as a HartleHawking wavefunctional. It has a local maximum
about the pure de Sitter vacuum. Restricting to SO(3) preserving deformations,
other local maxima (which exceed the one near the de Sitter vacuum) can peak at
inhomogeneous and anisotropic values of the late time metric and scalar
profile. Numerical experiments suggest the remarkable observation that, upon
fixing a certain average of the bulk scalar profile at I^+, the wavefunction
becomes normalizable in all the other (infinite) directions of the deformation.
We elucidate the meaning of double trace deformations in the context of dS/CFT
as a change of basis and as a convolution. Finally, we discuss possible
extensions of higher spin de Sitter holography by coupling the free theory to a
ChernSimons term.

We establish the existence of stable and metastable stationary black hole
bound states at finite temperature and chemical potentials in global and planar
fourdimensional asymptotically antide Sitter space. We determine a number of
features of their holographic duals and argue they represent structural
glasses. We map out their thermodynamic landscape in the probe approximation,
and show their relaxation dynamics exhibits logarithmic aging, with aging rates
determined by the distribution of barriers.

We initiate a systematic study of the dynamics of multiparticle systems with
supersymmetric Van der Waals and electronmonopole type interactions. The
static interaction allows a complex continuum of ground state configurations,
while the Lorentz interaction tends to counteract this configurational fluidity
by magnetic trapping, thus producing an exotic low temperature phase of matter
aptly named supergoop. Such systems arise naturally in $\mathcal{N}=2$ gauge
theories as monopoledyon mixtures, and in string theory as collections of
particles or black holes obtained by wrapping Dbranes on internal space
cycles. After discussing the general system and its relation to quiver quantum
mechanics, we focus on the case of three particles. We give an exhaustive
enumeration of the classical and quantum ground states of a probe in an
arbitrary background with two fixed centers. We uncover a hidden conserved
charge and show that the dynamics of the probe is classically integrable. In
contrast, the dynamics of one heavy and two light particles moving on a line
shows a nontrivial transition to chaos, which we exhibit by studying the
Poincar\'e sections. Finally we explore the complex dynamics of a probe
particle in a background with a large number of centers, observing hints of
ergodicity breaking. We conclude by discussing possible implications in a
holographic context.

We study the partition function of the free Sp(N) conformal field theory
recently conjectured to be dual to asymptotically de Sitter higherspin gravity
in fourdimensions. We compute the partition function of this CFT on a round
sphere as a function of a finite mass deformation, on a squashed sphere as a
function of the squashing parameter, and on an S2xS1 geometry as a function of
the relative size of S2 and S1. We find that the partition function is
divergent at large negative mass in the first case, and for small $S^1$ in the
third case. It is globally peaked at zero squashing in the second case. Through
the duality this partition function contains information about the wave
function of the universe. We show that the divergence at small S1 occurs also
in Einstein gravity if certain complex solutions are included, but the
divergence in the mass parameter is new. We suggest an interpretation for this
divergence as indicating an instability of de Sitter space in higher spin
gravity, consistent with general arguments that de Sitter space cannot be
stable in quantum gravity.

We show that the late time HartleHawking wave function for a free massless
scalar in a fixed de Sitter background encodes a sharp ultrametric structure
for the standard Euclidean distance on the space of field configurations. This
implies a hierarchical, treelike organization of the state space, reflecting
its genesis as a branched diffusion process. An equivalent mathematical
structure organizes the state space of the SherringtonKirkpatrick model of a
spin glass.

We initiate a systematic study of the state space of nonextremal, stationary
black hole bound states in fourdimensional N = 2 supergravity. Specifically,
we show that an exponential multitude of classically stable "halo" bound states
can be formed between large finite temperature D4D0 black hole cores and much
smaller, arbitrarily charged black holes at the same temperature. We map out in
full the regions of existence for thermodynamically stable and metastable bound
states in terms of the core's charges and temperature, as well as the region of
stability of the core itself. Several features of these systems, such as a
macroscopic configurational entropy and exponential relaxation timescales, are
similar to those of the extended family of glasses. We draw parallels between
the two with a view toward understanding complex systems in fundamental
physics.

These lecture notes give an introduction to a number of ideas and methods
that have been useful in the study of complex systems ranging from spin glasses
to Dbranes on CalabiYau manifolds. Topics include the replica formalism,
Parisi's solution of the SherringtonKirkpatrick model, overlap order
parameters, supersymmetric quantum mechanics, Dbrane landscapes and their
black hole duals.

In four dimensional N=2 supergravity theories, BPS bound states near marginal
stability are described by configurations of widely separated constituents with
nearly parallel central charges. When the vacuum moduli can be dialed
adiabatically until the central charges become anti parallel, a paradox
arises. We show that this paradox is always resolved by the existence of "bound
state transformation walls" across which the nature of the bound state changes,
although the index does not jump. We find that there are two distinct phenomena
that can take place on these walls, which we call recombination and
conjugation. The latter is associated to the presence of singularities at
finite distance in moduli space. Consistency of conjugation and wallcrossing
rules near these singularities leads to new constraints on the BPS spectrum.
Singular loci supporting massless vector bosons are particularly subtle in this
respect. We argue that the spectrum at such loci necessarily contains massless
magnetic monopoles, and that bound states around them transform by intricate
hybrids of conjugation and recombination.

We give an elementary physical derivation of the KontsevichSoibelman wall
crossing formula, valid for any theory with a 4d N=2 supergravity description.
Our argument leads to a slight generalization of the formula, which relates
monodromy to the BPS spectrum.

We derive an expression for functional determinants in thermal spacetimes as
a product over the corresponding quasinormal modes. As simple applications we
give efficient computations of scalar determinants in thermal AdS, BTZ black
hole and de Sitter spacetimes. We emphasize the conceptual utility of our
formula for discussing `1/N' corrections to strongly coupled field theories via
the holographic correspondence.

We show that strongly coupled field theories with holographic gravity duals
at finite charge density and low temperatures can undergo de Haas  van Alphen
quantum oscillations as a function of an external magnetic field. Exhibiting
this effect requires computation of the one loop contribution of charged bulk
fermions to the free energy. The one loop calculation is performed using a
formula expressing determinants in black hole backgrounds as sums over
quasinormal modes. At zero temperature, the periodic nonanalyticities in the
magnetic susceptibility as a function of the inverse magnetic field depend on
the low energy scaling behavior of fermionic operators in the field theory, and
are found to be softer than in weakly coupled theories. We also obtain
numerical and WKB results for the quasinormal modes of charged bosons in dyonic
black hole backgrounds, finding evidence for nontrivial periodic behavior as a
function of the magnetic field.

The AdS/CFT correspondence may connect the landscape of string vacua and the
`atomic landscape' of condensed matter physics. We study the stability of a
landscape of IR fixed points of N=2 large N gauge theories in 2+1 dimensions,
dual to SasakiEinstein compactifications of M theory, towards a
superconducting state. By exhibiting instabilities of charged black holes in
these compactifications, we show that many of these theories have charged
operators that condense when the theory is placed at a finite chemical
potential. We compute a statistical distribution of critical superconducting
temperatures for a subset of these theories. With a chemical potential of one
milliVolt, we find critical temperatures ranging between 0.24 and 165 degrees
Kelvin.

By Tdualizing spacefilling Dbranes in IIB orientifold compactifications
along the three noninternal spatial directions, we obtain black hole bound
states living in a universe with a gauged spatial reflection symmetry. We call
these objects orientiholes. The gravitational entropy of various IIA
orientihole configurations provides an "experimental" estimate of the number of
vacua in various sectors of the IIB landscape. Furthermore, basic physical
properties of orientiholes map to (sometimes subtle) microscopic features, thus
providing a useful alternative viewpoint on a number of issues arising in
Dbrane model building. More generally, we give orientihole generalizations of
recently derived wall crossing formulae, and conjecture a relation to the
topological string analogous to the OSV conjecture, but with a linear rather
than a quadratic identification of partition functions.

With model building applications in mind, we collect and develop basic
techniques to analyze the landscape of D7branes in type IIB compact CalabiYau
orientifolds, in three different pictures: Ftheory, the D7 worldvolume theory
and D9antiD9 tachyon condensation. A significant complication is that
consistent D7branes in the presence of O7^ planes are generically singular,
with singularities locally modeled by the Whitney Umbrella. This invalidates
the standard formulae for charges, moduli space and flux lattice dimensions. We
infer the correct formulae by comparison to Ftheory and derive them
independently and more generally from the tachyon picture, and relate these
numbers to the closed string massless spectrum of the orientifold
compactification in an interesting way. We furthermore give concrete recipes to
explicitly and systematically construct nontrivial Dbrane worldvolume flux
vacua in arbitrary CalabiYau orientifolds, illustrate how to read off Dbrane
flux content, enhanced gauge groups and charged matter spectra from tachyon
matrices, and demonstrate how brane recombination in general leads to flux
creation, as required by charge conservation and by equivalence of geometric
and gauge theory moduli spaces.

These lectures give a detailed introduction to constructing and analyzing
string vacua suitable for phenomenological model building, with particular
emphasis on Ftheory flux vacua. Topics include (1) general challenges and
overview of some proposed scenarios, (2) an extensive introduction to Ftheory
and its relation to Mtheory and perturbative IIB string theory, (3) Ftheory
flux vacua and moduli stabilization scenarios, (4) a practical geometrical
toolkit for constructing string vacua from scratch, (5) statistics of flux
vacua, and (6) explicit models.

We systematically construct the geometries dual to the 1+1 dimensional (0,4)
conformal field theories that arise in the lowenergy description of wrapped
M5branes in S^1 x CY_3 compactifications of Mtheory. This includes a large
number of multicentered black hole bound states asymptotic to AdS_3 x S^2. In
addition, we find many geometries that develop multiple, mutually decoupled
AdS_3 x S^2 throats. We argue there is a useful one to one correspondence
between the connected components of the space of solutions and particular
limits of type IIA attractor flow trees. We point out that there is a
thermodynamic instability of small supersymmetric BTZ black holes to
localization on the S^2, a supersymmetric and exactly solvable analog of the
well known AdSSchwarzschild localization instability, and identify this with
the ``Entropy Enigma'' in four dimensions. We discuss the phase transition this
suggests, and initiate the CFT interpretation of these results.

We investigate degeneracies of BPS states of Dbranes on compact CalabiYau
manifolds. We develop a factorization formula for BPS indices using attractor
flow trees associated to multicentered black hole bound states. This enables us
to study background dependence of the BPS spectrum, to compute explicitly exact
indices of various nontrivial Dbrane systems, and to clarify the subtle
relation of DonaldsonThomas invariants to BPS indices of stable D6D2D0
states, realized in supergravity as "hole halos". We introduce a convergent
generating function for D4 indices in the large CY volume limit, and prove it
can be written as a modular average of its polar part, generalizing the
fareytail expansion of the elliptic genus. We show polar states are "split"
D6antiD6 bound states, and that the partition function factorizes
accordingly, leading to a refined version of the OSV conjecture. This differs
from the original conjecture in several aspects. In particular we obtain a
nontrivial measure factor g_{top}^{2} e^{K} and find factorization requires a
cutoff. We show that the main factor determining the cutoff and therefore the
error is the existence of "swing states"  D6 states which exist at large
radius but do not form stable D6antiD6 bound states. We point out a likely
breakdown of the OSV conjecture at small g_{top} (in the large background CY
volume limit), due to the surprising phenomenon that for sufficiently large
background Kahler moduli, a charge N Q supporting single centered black holes
of entropy ~ N^2 S(Q) also admits twocentered BPS black hole realizations
whose entropy grows like N^3 at large N.

The BekensteinHawking entropy of certain black holes can be computed
microscopically in string theory by mapping the elusive problem of counting
microstates of a strongly gravitating black hole to the tractable problem of
counting microstates of a weakly coupled Dbrane system, which has no event
horizon, and indeed comfortably fits on the head of a pin. We show here that,
contrary to widely held beliefs, the entropy of spherically symmetric black
holes can easily be dwarfed by that of stationary multiblackhole
``molecules'' of the same total charge and energy. Thus, the corresponding
pinsized Dbrane systems do not even approximately count the microstates of a
single black hole, but rather those of a zoo of entropically dominant
multicentered configurations.

A D4D0 black hole can be deconstructed into a bound state of D0 branes with
a D6antiD6 pair containing worldvolume fluxes. The exact spacetime solution
is known and resembles a D0 accretion disk surrounding a D6antiD6 core. We
find a scaling limit in which the disk and core drop inside an AdS_2 throat.
Crossing this AdS_2 throat and the D0 accretion disk into the core, we find a
second scaling region describing the D6antiD6 pair. It is shown that the
Mtheory lift of this region is AdS_3 x S^2. Surprisingly, time translations in
the far asymptotic region reduce to global, rather than Poincare, time
translations in this core AdS_3. We further find that the quantum mechanical
ground state degeneracy reproduces the BekensteinHawking entropyarea law.

We provide a qualitative review of flux compactifications of string theory,
focusing on broad physical implications and statistical methods of analysis.

We study the computational complexity of the physical problem of finding
vacua of string theory which agree with data, such as the cosmological
constant, and show that such problems are typically NP hard. In particular, we
prove that in the BoussoPolchinski model, the problem is NP complete. We
discuss the issues this raises and the possibility that, even if we were to
find compelling evidence that some vacuum of string theory describes our
universe, we might never be able to find that vacuum explicitly.
In a companion paper, we apply this point of view to the question of how
early cosmology might select a vacuum.