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 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 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 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.

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.

This work concerns finite free complexes over commutative noetherian rings, in particular over group algebras of elementary abelian groups. The main contribution is the construction of complexes such that the total rank of their underlying free modules, or the total length of their homology, is less than predicted by various conjectures in the theory of transformation groups and in local algebra.

We establish new bounds on character values and character ratios for finite groups G of Lie type, which are considerably stronger than previously known bounds, and which are best possible in many cases. These bounds have the form |χ(g)|⩽cχ(1)αg, and give rise to a variety of applications, for example to covering numbers and mixing times of random walks on such groups. In particular, we deduce that, if G is a classical group in dimension n, then, under some conditions on G and g∈G, the mixing time of the random walk on G with the conjugacy class of g as a generating set is (up to a small multiplicative constant) n/s, where s is the support of g.

We associate to any given finite set of valuations on the polynomial ring in two variables over an algebraically closed field a numerical invariant whose positivity characterizes the case when the intersection of their valuation rings has maximal transcendence degree over the base fields. As an application, we give a criterion for when an analytic branch at infinity in the affine plane that is defined over a number field in a suitable sense is the branch of an algebraic curve.

No abstract uploaded!

No abstract uploaded!

No abstract uploaded!

This paper is a contribution to the general problem of giving an explicit description of the basic locus in the reduction modulo $p$ of Shimura varieties. Motivated by \cite{Vollaard-Wedhorn} and \cite{Rapoport-Terstiege-Wilson}, we classify the cases where the basic locus is (in a natural way) the union of classical Deligne-Lusztig sets associated to Coxeter elements. We show that if this is satisfied, then the Newton strata and Ekedahl-Oort strata have many nice properties.

In this paper, we prove a conjecture of Kottwitz and Rapoport on a union of (generalized) affine Deligne-Lusztig varieties $X(\mu, b)_J$ for a $p$-adic group $G$ and its parahoric subgroup $P_J$. We show that $X(\mu, b)_J \neq \emptyset$ if and only if the group-theoretic version of Mazur's inequality is satisfied. In the process, we obtain a generalization of Grothendieck's conjecture on the closure relation of $\s$-conjugacy classes of a twisted loop group.

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

We study affine Deligne-Lusztig varieties in the affine flag manifold of an algebraic group, and in particular the question, which affine Deligne-Lusztig varieties are non-empty. Under mild assumptions on the group, we provide a complete answer to this question in terms of the underlying affine root system. In particular, this proves the corresponding conjecture for split groups stated in \cite{GHKR2}. The question of non-emptiness of affine Deligne-Lusztig varieties is closely related to the relationship between certain natural stratifications of moduli spaces of abelian varieties in positive characteristic.

This paper studies affine Deligne-Lusztig varieties $X_{w}(b)$ in the affine flag variety of a quasi-split tamely ramified group. We describe the geometric structure of $X_{w}(b)$ for a minimal length element $w$ in the conjugacy class of an extended affine Weyl group, generalizing one of the main results in \cite{HL} to the affine case. We then provide a reduction method that relates the structure of $X_{w}(b)$ for arbitrary elements $w$ in the extended affine Weyl group to those associated with minimal length elements. Based on this reduction, we establish a connection between the dimension of affine Deligne-Lusztig varieties and the degree of the class polynomial of affine Hecke algebras. As a consequence, we prove a conjecture of G\"ortz, Haines, Kottwitz and Reuman in \cite{GHKR}.

No abstract uploaded!

This paper explores the Nash equilibria of a variant of the Colonel Blotto game, which we call the Asymmetric Colonel Blotto game. In the Colonel Blotto game, two players simultaneously distribute forces across n battlefields. Within each battlefield, the player that allocates the higher level of force wins. The payo↵ of the game is the proportion of wins on the individual battlefields. In the asymmetric version, the levels of force distributed to the battlefields must be nondecreasing. In this paper, we find a family of Nash equilibria for the case with three battlefields and equal levels of force and prove the uniqueness of the marginal distributions. We also find the unique equilibrium payo↵ for all possible levels of force in the case with two battlefields, and obtain partial results for the unique equilibrium payo↵ for asymmetric levels of force in the case with three battlefields.

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 study smooth toroidal compactifications of Siegel varieties thoroughly from the viewpoints of mixed Hodge theory and K\"ahler-Einstein metric. We observe that any cusp of a Siegel space can be identified as a set of certain weight one polarized mixed Hodge structures. We then study the infinity boundary divisors of toroidal compactifications, and obtain a global volume form formula of an arbitrary smooth Siegel variety $\sA_{g,\Gamma}(g>1)$ with a smooth toroidal compactification $\overline{\sA}_{g,\Gamma}$ such that $D_\infty:=\overline{\sA}_{g,\Gamma}\setminus \sA_{g,\Gamma}$ is normal crossing. We use this volume form formula to show that the unique group-invariant K\"ahler-Einstein metric on $\sA_{g,\Gamma}$ endows some restraint combinatorial conditions for all smooth toroidal compactifications of $\sA_{g,\Gamma}.$ Again using the volume form formula, we study the asymptotic behaviour of logarithmical canonical line bundle on any smooth toroidal compactification of $\sA_{g,\Gamma}$ carefully and we obtain that the logarithmical canonical bundle degenerate sharply even though it is big and numerically effective.

No abstract uploaded!

No abstract uploaded!

In this paper we describe a machinery for homological calculations of representations of FI_G, and use it to develop a local cohomology theory over any commutative Noetherian ring. As an application, we show that the depth introduced by the second author coincides with a more classical invariant from commutative algebra, and obtain upper bounds of a few important invariants of FI_G-modules in terms of torsion degrees of their local cohomology groups.

No abstract uploaded!

In 1971, McMullen and Walkup posed the following conjecture, which is called the generalized lower bound conjecture: If$P$is a simplicial$d$-polytope then its$h$-vector ($h$_{0},$h$_{1}, …,$h$_{$d$}) satisfies $$ {h_0}\leq {h_1}\leq \ldots \leq {h_{{\left\lfloor {{d \left/ {2} \right.}} \right\rfloor }}} $$ . Moreover, if$h$_{$r$−1}=$h$_{$r$}for some $$ r\leq \frac{1}{2}d $$ then$P$can be triangulated without introducing simplices of dimension ≤$d$−$r$.