No abstract uploaded!

In computational complexity, a complexity class is given by a set of problems or functions, and a basic challenge is to show separations of complexity classes Aot= B especially when Aot= B is known to be a subset of Aot= B . In this paper we introduce a homological theory of functions that can be used to establish complexity separations, while also providing other interesting consequences. We propose to associate a topological space Aot= B to each class of functions Aot= B , such that, to separate complexity classes Aot= B , it suffices to observe a change in" the number of holes", ie homology, in Aot= B as a subclass Aot= B of Aot= B is added to Aot= B . In other words, if the homologies of Aot= B and Aot= B are different, then Aot= B . We develop the underlying theory of functions based on combinatorial and homological commutative algebra and Stanley-Reisner theory, and recover Minsky and Papert's 1969 result that parity cannot be computed by nonmaximal degree polynomial threshold functions. In the process, we derive a" maximal principle" for polynomial threshold functions that is used to extend this result further to arbitrary symmetric functions. A surprising coincidence is demonstrated, where the maximal dimension of" holes" in Aot= B upper bounds the VC dimension of Aot= B , with equality for common computational cases such as the class of polynomial threshold functions or the class of linear functionals in Aot= B , or common algebraic cases such as when the Stanley-Reisner ring of Aot= B is Cohen-Macaulay. As another interesting application of our theory, we prove a result that a priori has nothing to do with complexity separation: it characterizes when a vector subspace intersects the positive

No abstract uploaded!

The ``principle of the fermionic projector'' provides a new mathematical framework for the formulation of physical theories and is a promising approach for physics beyond the standard model. The book begins with a brief review of relativity, relativistic quantum mechanics and classical gauge theories, with the emphasis on the basic physical concepts and the mathematical foundations. The external field problem and Klein's paradox are discussed and then resolved by introducing the so-called fermionic projector, a global object in space-time which generalizes the notion of the Dirac sea. The mathematical core of the book is to give a precise definition of the fermionic projector and to employ methods of hyperbolic differential equations for its detailed analysis. The fermionic projector makes it possible to formulate a new type of variational principles in space-time. The mathematical tools for the analysis of the corresponding Euler-Lagrange equations are developed. A particular variational principle is proposed which gives rise to an effective interaction showing many similarities to the interactions of the standard model. The main chapters of the book are easily accessible for beginning graduate students in mathematics or physics. Several appendices provide supplementary material which will be useful to the experienced researcher.

Symmetry protected topological (SPT) states have boundary 't Hooft anomalies that obstruct an effective boundary theory realized in its own dimension with UV completion and with an on-site $G$-symmetry. In this work, yet we show that a certain anomalous non-on-site $G$ symmetry along the boundary becomes on-site when viewed as an extended $H$ symmetry, via a suitable group extension $1\to K\to H\to G\to1$. Namely, a non-perturbative global (gauge/gravitational) anomaly in $G$ becomes anomaly-free in $H$. This guides us to construct exactly soluble lattice path integral and Hamiltonian of symmetric gapped boundaries, \emph{always existent} for \emph{any} SPT state in any spacetime dimension $d \geq 2$ of \emph{any} finite symmetry group, including on-site unitary and anti-unitary time-reversal symmetries. The resulting symmetric gapped boundary can be described either by an $H$-symmetry extended boundary of bulk $d \geq 2$, or more naturally by a topological {emergent} $K$-gauge theory with a global symmetry $G$ on a 3+1D bulk or above. The excitations on such a symmetric topologically ordered boundary can carry fractional quantum numbers of the symmetry $G$, described by representations of $H$. (Apply our approach to a 1+1D boundary of 2+1D bulk, we find that a deconfined gauge boundary indeed has \emph{spontaneous symmetry breaking} with long-range order. The deconfined symmetry-breaking phase crosses over smoothly to a confined phase without a phase transition.) In contrast to known gapped boundaries/interfaces obtained via \emph{symmetry breaking} (either global symmetry breaking or Anderson-Higgs mechanism for gauge theory), our approach is based on \emph{symmetry extension}. More generally, applying our approach to SPT states, topologically ordered gauge theories and symmetry enriched topologically ordered (SET) states, leads to generic boundaries/interfaces constructed with a mixture of \emph{symmetry breaking}, \emph{symmetry extension}, and \emph{dynamical gauging}.