Search Talks

Complexity class MA is a class of yes/no problems for which the answer `yes\' has a short certificate that can be efficiently checked by a classical randomized algorithm. We prove that MA has a natural complete problem: stoquastic k-SAT. This is a quantum-mechanical analogue of the satisfiability problem such that k-bit clauses are replaced by k-qubit projectors with non-negative matrix elements. Complexity class AM is a generalization of MA in which the certificate may include a short conversation between Prover and Verifier. We prove that AM also has a natural complete problem: stoquastic Local Hamiltonian with a quenched disorder. The problem is to evaluate expectation value of the ground state energy of disordered local Hamiltonian with non-positive matrix elements.

The nature of an unusual class of cosmic X-ray source, dubbed "Anomalous X-ray Pulsars," was a mystery since 1982 when the first example was discovered. In this talk, I will show the recent observational evidence that unambiguously links them with another equally exotic class of object, the explosive "Soft Gamma Repeaters." The evidence todate strongly supports the picture that both are "magnetars:" isolated young neutron stars having surface magnetic fields ~1000 times greater than those in conventional neutron stars.

The initial conditions for structure formation, and hence the dark matter distribution on sub-galactic scales, depend on the microphysics of the dark matter in the early Universe. I will focus on WIMPs and explain how collisional damping and free-streaming erase perturbations on comoving scales k> ~1/pc. Consequently the first structures to form in the Universe are mini-halos with mass of order the Earth. I will then describe the status of calculations of the subsequent dynamical evolution of these mini-halos. Finally, if time permits, I'll briefly overview the microphysics of axions.