Universal Algebra and Logic
Spring 2018 Seminars
| Time: Monday, January 22 2018, 4:10 PM Place: SC 1312 Speaker: Andrew Moorhead Title: The Algebraic Approach to the Constraint Satisfaction Problem (Part I) Abstract: The Constraint Satisfation Problem is a general combinatorial problem that asks whether there exists an assignment of values belonging to some finite domain to a finite set of variables subject to certain constraints. The Constraint Satisfaction Problem Dichotomy Conjecture is the statement that this problem is either solvable with a polynomial time algorithm or is complete for the class NP. A fruitful line of investigation into this problem has been to associate to a given template of constraints a universal algebra that consists of all higher order symmetries, or polymorphisms, of the relational structure determined by the template. This series of talks will introduce the Constraint Satisfaction Problem. |
| Time: Monday, January 29 2018, 4:10 PM Place: SC 1312 Speaker: Andrew Moorhead Title: The Algebraic Approach to the Constraint Satisfaction Problem (Part II) Abstract: We discuss a Galois connection between operations and relations on some domain that allows for an algebraic classification of the time complexity associated to a constraint language. The important fact is this: for a finite domain, the closed sets of operations are exactly the function clones and the closed sets of relations are exactly the relational clones, or those sets of relations that are closed under positive-primitive definitions. We will see that this implies that the complexity of a constraint language is determined by its algebra of polymorphisms. Time permitting, we will discuss an algebraic characterization of the width 1 constraint languages. |
| Time: Monday, February 5 2018, 4:10 PM Place: SC 1312 Speaker: Andrew Moorhead Title: The Algebraic Approach to the Constraint Satisfaction Problem (Part III) Abstract: We will finish our discussion of a Galois connection between operations and relations on some domain that allows for an algebraic classification of the time complexity associated to a constraint language. We will then discuss an algebraic characterization of the width 1 constraint languages. |
| Time: Monday, February 12 2018, 4:10 PM Place: SC 1312 Speaker: Andrew Moorhead Title: The Algebraic Approach to the Constraint Satisfaction Problem (Part IV) Abstract: This week we will discuss the so-called bounded width heirarchy. A constraint language is said to have bounded relational width if a certain local consistency checking algorithm is certain to produce a contradiction exactly when there is no solution to a CSP instance. Barto showed that this heirarchy collapses to a trichotomy and characterized the constraint languages that are of bounded width with the algebraic condition of congruence meet semidistributivity. |
| Time: Monday, February 19 2018, 4:10 PM Place: SC 1312 Speaker: Stephen Simpson Title: Degrees of unsolvability: a brief survey Abstract: A great landmark in the history of mathematics was Turing’s 1936 discovery of the existence of algorithmically unsolvable problems. Actually, Turing provided a specific, natural example of such a problem, namely, the halting problem for Turing machines. Building on Turing’s discoveries, other mathematicians from the 1940s to the present have developed a line of research known as degrees of unsolvability. In this line one identifies other algorithmically unsolvable problems beyond the halting problem, and one attempts to compare these problems according to the amount of algorithmic unsolvabililty which is inherent in them. Two important types of algorithmically unsolvable problems are decision problems — classified by their Turing degrees — and mass problems — classified by their Muchnik degrees. We explain these degree structures and survey what is known about them. |
| Time: Monday, February 26 2018, 4:10 PM Place: SC 1312 Speaker: Stephen Simpson Title: Degrees of unsolvability: a brief survey -part 2 Abstract: A great landmark in the history of mathematics was Turing’s 1936 discovery of the existence of algorithmically unsolvable problems. Actually, Turing provided a specific, natural example of such a problem, namely, the halting problem for Turing machines. Building on Turing’s discoveries, other mathematicians from the 1940s to the present developed a line of research known as degrees of unsolvability. In this line one identifies other algorithmically unsolvable problems beyond the halting problem, and one classifies these problems according to the amount of algorithmic unsolvability which is inherent in them. Two important types of algorithmically unsolvable problems are decision problems ― classified by their Turing degrees ― and mass problems ― classified by their Muchnik degrees. We explain these degree structures and survey what is known about them.
|
| Time: Monday, March 12 2018, 4:10 PM Place: SC 1312 Speaker: Andrew Moorhead Title: The Algebraic Approach to the Constraint Satisfaction Problem (Part V) Abstract: This week continue our discussion of the bounded width heirarchy. A constraint language is said to have bounded relational width if a certain local consistency checking algorithm is certain to produce a contradiction exactly when there is no solution to a CSP instance. Barto showed that this heirarchy collapses to a trichotomy and characterized the constraint languages that are of bounded width with the algebraic condition of congruence meet semidistributivity. |
| Time: Monday, March 19 2018, 4:10 PM Place: SC 1312 Speaker: Stephen Simpson Title: Degrees of unsolvability: a survey – part 3 Abstract: A degree of unsolvability is a quantity which measures the amount of algorithmic unsolvability which is inherent in an algorithmically unsolvable problem. We consider two degree structures: (1) the semilattice of Turing degrees, and (2) its completion, the lattice of Muchnik degrees. We emphasize degrees that are associated with specific, natural, algorithmically unsolvable problems. Historically, the first example of such a degree was 0′ = the Turing degree of the halting problem, and by iteration of the Turing jump operator we obtain a transfinite sequence 0, 0′, 0”, 0”’, …, 0^alpha, … where alpha ranges over some large initial segment of the ordinal numbers. If we limit ourselves to the Turing degrees, then these are the only known examples. But there are many more examples among the Muchnik degrees, including 1 = the degree of the problem of finding a completion of a consistent, recursively axiomatizable, effectively essentially undecidable theory; r = the degree of the problem of finding an infinite binary sequence which is random in the sense of Martin-Löf; r_alpha = the degree of the problem of finding an infinite binary sequence which is Martin-Löf random relative to 0^gamma for all gamma < alpha; b_alpha = the degree of the problem of finding a Turing oracle whose derandomization power is at least as great as that of 0^alpha; d = the degree of the problem of finding a diagonally nonrecursive function; d_REC = the degree of the problem of finding a diagonally nonrecursive function which is dominated by some recursive function; d_f = the degree of the problem of finding a diagonally nonrecursive function which is dominated by a specific recursive function such as f(n) = log n or f(n) = n or f(n) = 2^n; d_slow = the degree of the problem of finding a diagonally nonrecursive function which is dominated by some slow-growing recursive function h, where slow-growing means that sum_n 1/h(n) = infinity; and k_f = the degree of the problem of finding an infinite binary sequence such that the Kolmogorov complexity of the first n bits of the sequence is at least f(n). We shall discuss some of these examples as time permits. |
| Time: Monday, March 26 2018, 4:10 PM Place: SC 1312 Speaker: Constantine Tsinakis Title: From Lattice-Ordered Groups to Algebras of Logic Abstract: There is a substantial body of literature demonstrating the significant role of lattice-ordered groups (l-groups) in logic. The fact that underpins these studies is the realization that important algebras of logic may be viewed as l-groups with a modal operator. These connections are just the tip of the iceberg. The purpose of my talks is to precent the recent development of a Conrad type approach to the study of algebras of logic. The term “Conrad Program” refers to Paul Conrad’s approach to the study of l-groups, which analyzes the structure of individual or classes of l-groups by primarily using strictly lattice theoretic properties of their lattices of convex l-subgroups. I will show that large parts of the Conrad Program can be profitably extended in the setting of “e-cyclic” residuated lattices — that is residuated lattices that satisfy the identity x\e=e/x. |
| Time: Friday, March 30 2018, 4:10 PM Place: SC 1312 Speaker: Matthew Moore Title: Promising Satisfaction Abstract: The constraint satisfaction problem (CSP) represents a broad class of problems in theoretical computer science. Boolean satisfiability, graph colorability, and linear equation consistency are all examples of CSP instances. Quite recent work seeks to generalize the CSP framework to so-called “Promise Constraint Satisfaction” (PCSP). Being quite new, not very much is known about PCSP instances. In this talk, we will introduce the constraint satisfaction problem, motivate its generalization to the promise constraint satisfaction problem, and present some newly proved and wide-ranging results on the overall structure of PCSPs. |
| Time: Monday, April 2 2018, 4:10 PM Place: SC 1312 Speaker: Constantine Tsinakis Title: From Lattice-Ordered Groups to Algebras of Logic (part 2) Abstract: There is a substantial body of literature demonstrating the significant role of lattice-ordered groups (l-groups) in logic. The fact that underpins these studies is the realization that important algebras of logic may be viewed as l-groups with a modal operator. These connections are just the tip of the iceberg. The purpose of my talks is to precent the recent development of a Conrad type approach to the study of algebras of logic. The term “Conrad Program” refers to Paul Conrad’s approach to the study of l-groups, which analyzes the structure of individual or classes of l-groups by primarily using strictly lattice theoretic properties of their lattices of convex l-subgroups. I will show that large parts of the Conrad Program can be profitably extended in the setting of “e-cyclic” residuated lattices — that is residuated lattices that satisfy the identity x\e=e/x. |
| Time: Monday, April 16 2018, 4:10 PM Place: SC 1312 Speaker: Andrew Moorhead Title: The Algebraic Approach to the Constraint Satisfaction Problem (Part 6) Abstract: This week continue our discussion of the bounded width heirarchy. A constraint language is said to have bounded relational width if a certain local consistency checking algorithm is certain to produce a contradiction exactly when there is no solution to a CSP instance. Barto showed that this heirarchy collapses to a trichotomy and characterized the constraint languages that are of bounded width with the algebraic condition of congruence meet semidistributivity. |
| Time: Monday, April 23 2018, 4:10 PM Place: SC 1312 Speaker: Andrew Moorhead Title: The Algebraic Approach to the Constraint Satisfaction Problem (Part 7) Abstract: This week we conclude our discussion of the bounded width heirarchy. A constraint language is said to have bounded relational width if a certain local consistency checking algorithm is certain to produce a contradiction exactly when there is no solution to a CSP instance. Barto showed that this heirarchy collapses to a trichotomy and characterized the constraint languages that are of bounded width with the algebraic condition of congruence meet semidistributivity. |
©2024 Vanderbilt University ·
Site Development: University Web Communications