No abstract uploaded!

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

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 A!= B especially when A is known to be a subset of 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 S_A to each class of functions A, such that, to separate complexity classes A from a superclass B', it suffices to observe a change in" the number of holes", ie homology, in S_A as a subclass B of B'is added to A. In other words, if the homologies of S_A and S_ {A union B} are different, then A!= B'. We develop the underlying theory of functions based on homological commutative algebra and Stanley-Reisner theory, and prove a" maximal principle" for polynomial threshold functions that is used to recover Aspnes, Beigel, Furst, and Rudich's characterization of the polynomial threshold degree of symmetric functions. A surprising coincidence is demonstrated, where, roughly speaking, the maximal dimension of" holes" in S_A upper bounds the VC dimension of A, with equality for common computational cases such as the class of polynomial threshold functions or the class of linear functionals over the finite field of 2 elements, or common algebraic cases such as when the Stanley-Reisner ring of S_A 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 cone, in terms of homological

In this paper we study generalized Gorenstein Arf rings: a class of one-dimensional Cohen–Macaulay local Arf rings that is strictly contained in the class of Gorenstein rings. We obtain new characterizations and examples of Arf rings, and give applications of our argument to numerical semigroup rings and certain idealizations. In particular, we generalize a beautiful result of Barucci and Fröberg concerning Arf numerical semigroup rings.

In this paper we study the Weak Lefschetz property of two classes of standard graded Artinian Gorenstein algebras associated in a natural way to the Apéry set of numerical semigroups. To this aim we also prove a general result about the transfer of the Weak Lefschetz property from an Artinian Gorenstein algebra to its quotients modulo a colon ideal.

Siegel varieties are locally symmetric varieties. They are important and interesting in algebraic geometry and number theory. We construct a canonical Hodge bundle on a Siegel variety so that the holomorphic tangent bundle can be embedded into the Hodge bundle; we obtain that the canonical Bergman metric on a Siegel variety is same as the induced Hodge metric and we describe asymptotic behavior of this unique K\"ahler-Einstein metric explicitly; depending on these properties and the uniformitarian of K\"ahler-Einstein manifold, we study extensions of the tangent bundle over any smooth toroidal compactification. We apply these results of Hodge bundles, to study dimension of Siegel cusp modular forms and general type for Siegel varieties

We prove that in the unramified case, local models of Shimura varieties with Iwahori level structure are normal and Cohen Macaulay.

No abstract uploaded!

No abstract uploaded!