Old

Speaker: Jennifer Chubb, GWU

1957 E Street, Room B16

Speaker: Andrew Kebo,

Old

Speaker: Joseph S. Miller,

http://www.math.uconn.edu/~josephmiller/

Title: *Degrees
of unsolvability of continuous functions*

1957
E Street, Room 211

Speaker: Simon Y. Berkovitch,
Computer Science, GWU

http://cs.seas.gwu.edu/people/faculty-detail.php?personID=3

Old

Speaker: Andrey Frolov,

Old

Speaker: Rehana
Patel,

*OTHER LOGIC TALKS*

Speaker: Lenore Blum, Distinguished
Career Professor of Computer Science,

Title: *Computing over the Reals: Where Turing Meets **Newton*

Abstract:
The classical (*Turing*) *theory of computation *has been
extraordinarily successful in providing the foundations and framework for
theoretical computer science. Yet its dependence on 0’s and 1’s is
fundamentally inadequate for providing such a foundation for modern scientific
computation where most algorithms—with origins in

Mike Shub,
Steve Smale and I introduced a theory of computation
and complexity over an arbitrary ring or field *R*. If *R* is *Z*_{2}
= {0, 1}, the classical computer science theory is recovered. If *R* is
the field of real numbers, *Newton**’s
algorithm*, the paradigm algorithm of numerical analysis, fits naturally
into our model of computation.

*Complexity classes *P, NP and
the *fundamental question *“Does *P *= *NP*?” can be formulated
naturally over an arbitrary ring or field R. The answer to the fundamental
question depends on the complexity of deciding feasibility of polynomial
systems over R. When *R* is *Z*_{2}, this becomes the
classical *satisfiability** *problem of
Cook-Karp-Levin. When *R* is the field of complex numbers, the answer
depends on the complexity of *Hilbert’s Nullstellensatz*.

The notion of *reduction *between
discrete problems (e.g. between traveling salesman and satisfiability)
has been a powerful tool in classical complexity theory. But now, in addition,
the *transfer of complexity *results between domains (discrete and
continuous) becomes a real possibility.

In this talk, I
will discuss these results and indicate how basic notions from numerical
analysis such as *condition*, round off and approximation are being
introduced into complexity theory, bringing together ideas germinating from the
real calculus of Newton and the discrete computation of computer science.

This talk will
be accessible to undergraduates.

Funger Hall, Room 223

Speaker: Natasha Dobrinen,

http://www.logic.univie.ac.at/~dobrinen/

Title: *To infinity and beyond*

Abstract: We give a brief history of set theory, starting with Cantor's investigations into the transfinite and building up to the three main lines of research in modern set theory, namely, inner models, large cardinals, and forcing. We show how these work together and include applications to other areas of mathematics. In conclusion, we present some areas of active research and future trends in modern set theory.

1957 E Street, Room 112

Speaker: Bjorn Kjos-Hanssen,

http://www.geocities.com/bjoernkjoshanssen/

Title:
*Brownian motion and Kolmogorov complexity*

Abstract: Brownian motion is a mathematical model of certain erratic behaviors, such as the fluctuation of stock prices. However, the model does feature slow times, during which the movement is more predictable. Probabilists have shown that the set of slow times has Lebesgue measure zero, but positive Hausdorff dimension.

Using methods of
computability theory, we can say something about the individual real numbers *t
*that occur as slow times. We show that they are
all quite complicated, in the sense that their decimal expansions have high Kolmogorov complexity.

1957

Speaker: Timothy McNicholl,

Title: *Computable aspects of inner
functions*

Abstract: The theory of inner
functions plays an important role in the study of bounded analytic functions. Inner functions are also very useful in
applied mathematics. Two foundational results in this theory are Frostman’s Theorem and the Factorization Theorem. We prove a uniformly computable version of Frostman’s Theorem. We then show that the Factorization Theorem is
not uniformly computably true. We then
show that for an inner function *u*, the order of the zero at 0 (if there
is any) and the Blaschke sum of *u* provide the
exact amount of information necessary to compute the factorization of *u*.
Along the way, we discuss some uniform
computability results for Blaschke products. These results play a key role in the analysis
of factorization. We use Type-Two Effectivity as our foundation.

Speakers: Sarah Pingrey and Jennifer Chubb, GWU

http://home.gwu.edu/~spingrey/

Sarah
and Jennifer will each give a half hour talk.

Titles:
(first) *Complexity of relations on computable structures*, and (second) *Strong
reducibilities, scattered linear orderings, ranked
sets, and Kolmogorov complexity*

Abstract:
Harizanov showed that the Turing degree
spectrum of the *w*-part of a
linear ordering of type *w* +* w** is all of the limit computable Turing
degrees. This is not the case for truth-table
degrees. There is a computable
enumerable set *D* such that *D* is not weak truth-table reducible to
any initial segment of any computable scattered linear ordering. We will use algorithmic information theory to
establish this result.