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

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.

TITLE: Asymptotic Fixed Points, Part I.

ABSTRACT: By a standard exercise, a uniform contraction on a complete metric
space has a fixed point. Easy examples show that this fails if the
contraction is not uniform. I will discuss some recent results where the
uniform property is replaced by asymptotic conditions on the contraction.
These results are most easily framed and proved using methods from
nonstandard analysis, so I will also briefly brief review those methods. If
there is interest, I will actually prove some of the fixed-point results in
a second seminar (hence the “Part I.”)

Speaker: David Webb (Associate Professor of Mathematics Education Executive Director, Freudenthal Institute US University of Colorado Boulder School of Education)

Title: Infusing Active Learning Design Principles in the Undergraduate Calculus Sequence

Abstract: This interactive presentation will provide a brief overview of undergraduate mathematics at the University of Colorado Boulder, and related activities that we and other universities have designed and used in the freshman pre-calculus through Calculus 2 sequence. Using principles of Active Learning, students are encouraged to conjecture, explore and communicate their reasoning in the process of solving mathematics problems. Underlying this approach is research that has demonstrated how students who are involved in active learning techniques can learn more effectively in their classes, resulting in lower DFW rates, increased persistence in subsequent courses, and improved dispositions towards mathematics.

Speaker: Victor Donnay, William Kenan, Jr Professor of Mathematics and Director, Environmental Studies program, Bryn Mawr College

Title: Connecting Math and Sustainability

Abstract: How can we better inspire our students to study and succeed in mathematics? Victor Donnay will discuss his experiences in using issues of civic engagement, particularly environmental sustainability, as a motivator. He will present a variety of ways to incorporate issues of sustainability into math and science classes ranging from easy to adapt extensions of standard homework problems to more elaborate service learning projects. He will share some of the educational resources that he helped collect as chair of the planning committee for Mathematics Awareness Month 2013- the Mathematics of Sustainability as well as his TED-Ed video on Tipping Points and Climate Change. He has used these approaches in a variety of courses including Calculus, Differential Equations, Mathematical Modeling and Senior Seminar.