Calendar

Sep
14
Wed
Analysis Seminar: Thomas Hangelbroek @ Keller 313
Sep 14 @ 3:30 pm – 4:30 pm
Sep
15
Thu
Logic seminar: Manabu Hagiwara @ Keller 303
Sep 15 @ 1:30 pm – Sep 15 @ 2:30 pm

I will give a tutorial talk, how to use LEAN and Coq/MathCopm.SSReflect, which are famous proof assistant systems.

Keller 303

Sep
19
Mon
Topology Qualifying Exam
Sep 19 @ 9:00 am – 1:00 pm
Sep
21
Wed
Analysis Seminar: Mirza Baig @ Keller 313
Sep 21 @ 3:30 pm – 4:30 pm

Title: On the Radon Transform

Abstract: In this talk we will introduce, motivate and discuss some of the elementary properties of the Radon transform operator. We will cover a little about how to invert this operator via its adjoint (i.e. back-projection operator) and approximate identities.

Sep
22
Thu
Logic seminar: Mushfeq Khan
Sep 22 @ 1:30 pm – Sep 22 @ 2:30 pm

This week Mushfeq Khan is continuing his
seminar from 2 weeks ago on
“Turing degrees and Muchnik degrees of recursively bounded DNR functions”.

Summary:

This talk is based on a forthcoming paper by Steve Simpson. It contains
some results that shed light on a part of the Muchnik lattice that remains
poorly understood: the various degrees of recursively bounded DNR functions
obtained by varying the recursive bound.

Keller Hall 303

Sep
26
Mon
Applied Math Qualifying Exam
Sep 26 @ 9:00 am – 1:00 pm
Sep
28
Wed
NCG seminar: Smale spaces and C*-algebras
Sep 28 @ 3:30 pm – 4:30 pm
Sep
29
Thu
Logic Seminar: William DeMeo @ Keller 303
Sep 29 @ 1:30 pm – Sep 29 @ 2:20 pm

TITLE: The Algebraic Approach to Determining the Complexity of Constraint Satisfaction Problems

SPEAKER: William DeMeo

ABSTRACT: The “CSP-dichotomy conjecture” of Feder and Vardi asserts that every constraint satisfaction problem (CSP) is in P or is NP-complete. Sometime around the late 1990′s it was observed that a CSP is naturally associated with a general (universal) algebra via a certain Galois connection, and that this connection makes it possible to use algebraic methods to determine the complexity class of a CSP. This led to the “algebraic CSP-dichotomy conjecture” which, after more than a decade of substantial research, has been reduced to the following conjecture: the CSP associated with a finite idempotent algebra A is tractable if and only if the variety generated by A has a Taylor term.

In this talk we try to give most of the background required to understand the algebraic approach to CSP. We give some concrete examples that demonstrate how one uses properties of a universal algebra to determine the complexity class of a CSP. If time permits, we will highlight some of our most recent discoveries that have helped resolve the dichotomy conjecture for most idempotent varieties.

The talk should be fairly self-contained for anyone greater than or equal to a math or cs graduate student. Roughly speaking, if you have heard of the complexity classes P and NP and if you know what a universal algebra is, then you should understand most of this talk.