Promise Constraint Satisfaction Problems (PCSP) are a generalization of Constraint Satisfaction Problems (CSP) that provide a common framework for many classical decision problems like graph colorability, satisfiability of Boolean formulas, solvability of linear equations, etc. Informally, a PCSP asks to distinguish between whether a given instance of a CSP has a solution or not even a specified relaxation can be satisfied. In the formulation for a fixed template of relational structures A and B, the input of PCSP(A,B) is a structure I of the same type as that of A and B. The problem is to determine if there exists a homomorphism from I into A or if there does not exist a homomorphism from I into B. The “promise” is that exactly one of these two alternatives occurs for the input I. As with CSP, the computational complexity of a PCSP is determined by the higher arity symmetries or relation preserving functions, called polymorphisms, from A to B. All polymorphisms from A to B form a clonoid, a set of finitary functions from A to a target algebra B that is closed under the usual variable operations like identifying, permuting and introducing arguments as well as closed under operations from B. We adapt the established algebraic approach for analyzing CSP to investigate the complexity of PCSP and take steps towards classifying clonoids on finite sets in general.
Join the Zoom meeting at https://cuboulder.zoom.us/j/4348160464
The first topic is based on work in [17], we study the so-called “coin-turning” walks. Let S be the random walk obtained from “coin turning” with some sequence {pn}n?2, as introduced in [16].
We investigate the scaling limits of S in the spirit of the classical Donsker invariance principle, both for the heating and for the cooling dynamics. We prove that an invariance principle, albeit with a non-classical scaling, holds for “not too small” sequences, the order const·n?1 (critical cooling regime) being the threshold. At and below this critical order, the scaling behavior is dramatically different from the one above it. The same order is also the critical one for the Weak Law of Large Numbers to hold. In the critical cooling regime, an interesting process emerges: it is a continuous, piecewise linear, recurrent process, for which the one-dimensional marginals are Beta-distributed.
In the second topic, we study equilibrium of stopping problem for a multi-dimensional continuous strong Markov processes X. We use the framework for definition of equilibrium as in [20], especially, the discount function is of decreasing impatience, which means it is log sub-additive and may not be exponential. We provide properties of nearly Borel equilibria, and build up the equivalence be- tween an equilibrium and its finely closure.
Under certain regular conditions on X, we give results of optimality of an equilibrium and prove that there exists an optimal equilibrium among a quite general family M of equilibria with some proper regularity condition for M. Moreover, the optimal one can be achieved by taking the intersection of all equilibria.
Join the Zoom meeting at https://cuboulder.zoom.us/j/511678834
Let G be a connected, nonabelian, reductive, linear algebraic group over an algebraically closed field of characteristic 0. Let T be a maximal torus of G, and let Q be a closed, connected, solvable subgroup of G whose unipotent radical is stable under the conjugation action of T . We determine necessary and sufficient conditions for the algebraic action of G on G/Q to be at least generically 2-transitive. For semisimple groups G, we determine when this action is precisely generically 2-transitive. Through examples, we show that there exist closed, connected, solvable Q such that gtd(G, G/Q) = 2, thereby showing how the conditions of our theorem can be met. We also show, through example, that not every closed, connected, solvable Q such that gtd(G, G/Q) = 2 must have its unipotent radical stable under conjugation by T.
Quotient algorithms have been a principal tool for the computational investigation of finitely presented groups as well as for constructing groups. I will describe a method for a nonsolvable quotient algorithm, that extends a known finite quotient with a module.
This is joint work with Heiko Dietrich (Monash U., Melbourne, Australia)
Towards a Nonsolvable Quotient Algorithm
Apr. 02, 2020 3pm (MATH 350)
Topology
Katharine Adamyk (CU Boulder)
X
The mod 2 Steenrod algebra, A, appears in stable homotopy theory as the algebra of stable operations on cohomology with coefficients in Z/2. In this talk, we present results that hold in the stable category of modules over A(1), a small subalgebra of A. In this category, the invariants Q_0- and Q_1-Margolis homology together detect a large amount of information about a given A(1)-module. We show that all bounded below A(1)-modules of finite type whose Q_1-Margolis homology is trivial are stably equivalent to direct sums of suspensions of a distinguished family of A(1)-modules.
The classification theorem is then used to simplify computations of localized Ext groups and to provide necessary conditions for lifting A(1)-modules to A-modules. We give the first differential for a spectral sequence converging to an h_0-localized Ext group associated to a given bounded below A(1)-module of finite type. The classification theorem allows the computation of all differentials if the desired decomposition of a module with trivial Q_1-Margolis homology can be given explicitly. This is not always possible, but we give some examples where the higher differentials can be computed. The differentials in this spectral sequence detect obstructions to lifting an A(1)-module to an A-module.
Clonoids and Promise Constraint Satisfaction Problems