Friday, April 20, 2007

10:3011:30 a.m.

Old Main (1922 F Street), Room 104

Speaker: Jennifer Chubb, GWU


Title: An introduction to Kolmogorov complexity

Abstract: The measurement of complexity of strings is the foundation for modern algorithmic information theory. The Kolmogorov complexity of a string of natural numbers is, informally, the length of the shortest program that will output the string. In this talk, I will give the formal definition of both plain and prefix-free Kolmogorov complexity, and we will see some immediate theorems and applications. Time permitting, I will give a brief introduction to the algorithmic randomness, currently an extremely active area of research where these ideas play a major role.


Thursday, April 19, 2007

2:203:35 p.m.

1957 E Street, Room B16

Speaker: Andrew Kebo, University of Maryland

Title: Why the Copenhagen interpretation of quantum mechanics stuck

Abstract: The notion of measurement in quantum mechanics is intuitively perplexing. Some physicists claim that quantum mechanics implies that a subatomic particle does not have a definite position until you measure it, i.e., the act of measuring a particle forces it to decide where to be. This sounds like new age gobbledygook, yet this is the orthodox interpretation of quantum mechanics. In this talk, I will present the reasons why this interpretation has stuck within the physics community.


Thursday, March 8, 2007

4:005:00 p.m.

Old Main (1922 F Street), Room 104

Speaker: Joseph S. Miller, University of Connecticut


Title: Degrees of unsolvability of continuous functions

Abstract: We show that the Turing degrees are not sufficient to measure the complexity of continuous functions on [0, 1]. Computability of continuous real functions is a standard, and well-understood notion from computable analysis. It would be natural to define the degree of a continuous function to be the least Turing degree relative to which it is computable. Pour-El and Lempp asked if such a degree necessarily exists. We answer this question in the negative and supply a satisfactory theory of degrees of continuous functions. The new degree structure is a proper extension of the Turing degrees and a proper subclass of the enumeration degrees (or partial degrees). Proofs draw from classical and constructive analysis, as well as from computability theory.


Friday, March 2, 2007

4:005:00 p.m.

1957 E Street, Room 211

Speaker: Simon Y. Berkovitch, Computer Science, GWU


Title: A computational model of the brain: is Google an invention or a discovery?

Abstract: The unprecedented success of Google may imply that a computational model following its constructive operational principle could elucidate the enigma of the brain.


Friday, February 16, 2007

4:005:00 p.m.

Old Main (1922 F Street), Room 104

Speaker: Andrey Frolov, Kazan State University, Russia

Title: Limit computable copies of linear orderings

Abstract: We prove that for every n>0, there is a countable linear ordering whose limit computable spectrum consists of exactly all non lown degrees. We examine properties of these orderings for n=1 and n=2.


Friday, February 2, 2007

4:005:00 p.m.

Old Main (1922 F Street), Room 104

Speaker: Rehana Patel, St. John’s University, Queens, New York

Title: Model-theoretic aspects of a family of countably universal graphs

Abstract: Given a fixed, finite graph H, a graph G is said to be H-free if G does not contain a copy of H as a subgraph, induced or otherwise.  I will consider the case of (Kl+K3)free graphs, l>2, Kl+K3 being the graph on l+2 vertices consisting of a Kl and a triangle that share exactly one vertex.  Cherlin, Shelah and Shi have shown that for each l>2, there exists a countably universal (Kl+K3)-free graph U1, in the sense that U1 is countable and it embeds every other countable (Kl+K3)-free graph as an induced subgraph.  I will describe the structure and some model-theoretic properties of these graphs U1, in particular their positions within Saharon Shelah’s classification hierarchy.




Mathematics Colloquium


Friday, April 13, 2007

1:002:00 p.m.

1957 E Street, Room 111

Speaker: Lenore Blum, Distinguished Career Professor of Computer Science, Carnegie Mellon University


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 Newton, Euler, Gauss, et al. —are real number algorithms.


Mike Shub, Steve Smale and I introduced a theory of computation and complexity over an arbitrary ring or field R. If R is Z2 = {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 Z2, 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.


Thursday, February 1, 2007

4:005:00 p.m.

Funger Hall, Room 223

Speaker: Natasha Dobrinen, Kurt Gödel Research Center for Mathematical Logic at the University of Vienna


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.


Monday, January 29, 2007

10:0011:00 a.m.

1957 E Street, Room 112

Speaker: Bjorn Kjos-Hanssen, Cornell University


 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.



Graduate Student Seminar


Friday, March 30, 2007

4:005:00 p.m.

1957 E St., NW Room 211

Speaker: Timothy McNicholl, Lamar University

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.


Friday, March 9, 2007

4:005:00 p.m.

1957 E Street, Room 212

Speakers: Sarah Pingrey and Jennifer Chubb, GWU



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.