%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Last modified: January 10, 2008
% Template latex file to create a schedule and abstracts
% for BIRS 5 day workshops in 2008--.
%
% 1. Use the command:
% pdflatex programme.tex
% to create the pdf file programme.pdf.
%
% 2. Email programme.pdf to
% the BIRS Programme Coordinator birs@birs.ca
% AND the BIRS Station Manager birsmgr@birs.ca.
%
% 3. Questions and comments should be sent to either
% birs@birs.ca or birsmgr@birs.ca.
%
% WORKSHOP SCHEDULING ADDITIONAL GUIDELINES:
%
% 1. LECTURES:
%
% You are welcome to set up your own schedule for lectures at BIRS.
% The attached recommended schedule is just a guideline. The
% following are a few points to consider should you decide to create
% your own schedule. (a) Many BIRS participants have commented that
% having no more than 4-5 lectures per day is satisfactory. Some
% groups have opted to work through the day and then have evenings
% free while other groups have opted to work the mornings and
% evenings. (b) Meal times cannot be changed and are as follows:
% Breakfast, 7-9 am, Lunch, 11:30 am-1:30 pm, Dinner, 5:30-7:30 pm.
% They are all served buffet style so you may join the meals at any
% time during these set hours. (c) It is encouraged that you leave
% one afternoon completely free so that participants can have the time
% to explore the area of Banff and Lake Louise. There are many types
% of extracurricular activities one can enjoy at any time throughout
% the year.
%
% 2. COFFEE BREAKS:
%
% When you are setting up your schedule, please keep in mind that your
% coffee breaks should be 20-30 minutes in length, as it takes a
% minute or two to walk from the meeting room to the coffee break
% room.
%
% Morning coffee breaks are available from 10.00 am onwards but must
% finish by 11.00 am
%
% Afternoon coffee breaks are available from 2.00 pm but must finish
% by 3.30 pm.
%
% 3. Friday:
%
% Most participants have scheduled their departure flights throughout
% the day on Friday. Some are forced to take early flights due to
% long journeys. Please check with your Friday speakers to ensure
% that they are not among those who are scheduled to leave before or
% during their own talk that day.
%
% 4. GROUP PHOTO:
%
% The time for the group photo (Monday, after the Banff Centre tour)
% can be changed, should you feel that another day and/or time is
% suitable for your group. Should you decide on another time, please
% contact the Station Manager to arrange the details. Minimum 24
% hours notice required.
%
% 5. TOUR OF THE BANFF CENTRE:
%
% We recommend that participants take part in a free guided tour of
% The Banff Centre facilities. We suggest taking the tour on Monday
% (early in the week) so that participants can appreciate and perhaps
% take in some of the many other programs and services that are
% offered at The Banff Centre. The date and time are flexible for
% this, depending on the availability of the tour guide. Minimum 24
% hour notice required.
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\documentclass[11pt]{article}
\usepackage{pdfsync}
\usepackage{color}
\usepackage[pdftex]{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\setlength{\textwidth}{7.0in}
\setlength{\textheight}{9.5in}
\setlength{\oddsidemargin}{-0.30in}
\setlength{\evensidemargin}{0.25in}
\setlength{\topmargin}{-1in}
\definecolor{lgray}{gray}{.8}
\newcommand{\xbox}{\colorbox{lgray}{ X }}
\begin{document}
\begin{center}
\Large{\bf Computability, Reverse Mathematics and Combinatorics}\\
\Large{\bf December 7--12, 2008}\\
Last updated on \today \\
\end{center}
\begin{center} {\bf MEALS}
\end{center}
\noindent
*Breakfast (Buffet): 7:00--9:30 am, Sally Borden Building, Monday--Friday\\
*Lunch (Buffet): 11:30 am--1:30 pm, Sally Borden Building, Monday--Friday\\
*Dinner (Buffet): 5:30--7:30 pm, Sally Borden Building, Sunday--Thursday\\
Coffee Breaks: As per daily schedule, 2nd floor lounge, Corbett Hall\\
{\bf *Please remember to scan your meal card at the host/hostess
station in the dining room for each meal.}
\begin{center} {\bf MEETING ROOMS}
\end{center}
\noindent {\bf All lectures will be held in Max Bell 159 (Max Bell
Building accessible by walkway on 2nd floor of Corbett Hall). LCD
projector, overhead projectors and blackboards are available for
presentations.} Please note that the meeting space designated for
BIRS is the lower level of Max Bell, Rooms 155--159. Please respect
that all other space has been contracted to other Banff Centre guests,
including any Food and Beverage in those areas.
\begin{center} {\bf SCHEDULE}
\end{center}
% \noindent
% You are welcome to schedule lectures as you see fit, as long as you
% adhere to the meal times (noted above), coffee break start and end
% times (noted below) and take into account the ``welcome'' on Monday
% morning, the Banff Centre tour on
% Monday afternoon and group photo on Tuesday morning.\\
% \noindent
% When your schedule is finalized, please e-mail it to the BIRS
% Station
% Manager birsmgr@birs.ca by 12 noon on the Thursday before your arrival.\\
% \noindent
% You are also encouraged to e-mail the schedule to all of your
% participants. An electronic mail list is offered to each workshop,
% at the address: $<$birs event id$>$@lists.birs.ca. More information
% about your mail list is available by clicking on the "Mailing List"
% link on your workshop home page. If there is no such link,
% and you would like a mail list, please request one at help@birs.ca.\\
\begin{tabular}{ll}
{\bf\large Sunday} & \\
& \\
{\bf 16:00} & Check-in begins (Front Desk - Professional Development Centre - open 24 hours)\\
& Lecture rooms available after 16:00 (if desired)\\
{\bf 17:30--19:30} & Buffet Dinner, Sally Borden Building\\
{\bf 20:00} & Informal gathering in 2nd floor lounge, Corbett Hall \\
&Beverages and small assortment of snacks available on a cash honour-system.\\
\end{tabular}
\vspace{.5in}
\begin{tabular}{ll}
{\bf\large Monday} & \\ & \\
{\bf 7:00--8:45} & Breakfast\\
{\bf 8:45--9:00} & Introduction and Welcome to BIRS by BIRS Station Manager, Max Bell 159\\
{\bf 9:00--9:50} & Hirst, Two variants of Ramsey's theorem\\
{\bf 10:00--10:30} & Coffee Break, 2nd floor lounge, Corbett Hall \\
{\bf 10:30--11:20} & Simpson, The G\"odel Hierarchy and Reverse
Mathematics\\ %V
{\bf 11:30--13:00}& Lunch\\
{\bf 13:00--14:00}& Guided Tour of The Banff Centre; meet in the 2nd floor lounge, Corbett Hall\\
{\bf 14:00} & Group Photo; meet on the front steps of Corbett Hall \\
{\bf 14:15--15:00 } & Coffee Break, 2nd floor lounge, Corbett Hall\\
{\bf 15:00--15:50} & Keisler, Nonstandard Arithmetic,
Reverse Mathematics, and Recursive
Comprehension \\
{\bf 16:00--16:50} & Chong, $\Pi^1_1$ conservation of the
COH Principle over models of $B\Sigma_2$ \\
{\bf 17:30--19:30} & Dinner\\
\end{tabular}
% \vspace{.5in}
\begin{tabular}{ll}
{\bf\large Tuesday} & \\ & \\
{\bf 7:00--9:00} & Breakfast\\
{\bf 9:00--9:50} & Montalban, On the Strength of
Fra\"{\i}ss\'e's conjecture. \\
{\bf 10:00--10:30} & Coffee Break, 2nd floor lounge, Corbett Hall \\
{\bf 10:30--11:20} & Kohlenbach, Tao's correspondence
principle, a finitary mean ergodic theorem\\ & and conservation results for Ramsey's theorem for pairs\\
{\bf 11:30--13:00} & Lunch\\
{\bf 13:30--14:20} & Carlson, Combinatorics of Words \\
{\bf 14:20--15:00 } & Coffee Break, 2nd floor lounge, Corbett Hall\\
{\bf 15:00--15:50} & Kierstead, Recursive and On-line Graph Coloring \\
{\bf 16:00--16:50} & Weiermann, Well partial orderings and
their strength in terms of maximal order types\\
{\bf 17:30--19:30} & Dinner\\
{\bf 20:00--?} & Problem Session\\
\end{tabular}
\vspace{.25in}
\begin{tabular}{ll}
{\bf\large Wednesday} & \\ & \\
{\bf 7:00--8:50} & Breakfast\\
{\bf 8:50 - 9:10} & Solomon, Classically equivalent
definitions of well quasi-orders \\
{\bf 9:15 - 9:35} & Yokoyama, Non-standard analysis within
second order arithmetic \\
{\bf 9:40 - 10:00} & Marcone, An interaction
between reverse mathematics and computable analysis \\
{\bf 10:00--10:30} & Coffee Break, 2nd floor lounge, Corbett Hall \\
{\bf 10:30 - 10:50} & Kierstead, The survival game \\
{\bf 10:55 - 11:15} & Kjos-Hanssen, Birth-death processes,
bushy trees, and a law of weak subsets \\
{\bf 11:20 - 11:40} & Cenzer, Space Complexity of Abelian Groups\\
{\bf 11:30--13:30} & Lunch\\
& Free Afternoon \\
{\bf 17:30--19:30} & Dinner\\
\end{tabular}
\vspace{.25in}
\begin{tabular}{ll}
{\bf\large Thursday} & \\ & \\
{\bf 7:00--9:00} & Breakfast\\
{\bf 9:00--9:50} & Buss, Polynomial Local Search
higher in the Polynomial Hierarchy and Bounded Arithmetic\\
{\bf 10:00--10:30} & Coffee Break, 2nd floor lounge, Corbett Hall \\
{\bf 10:30--11:20} & Hirschfeldt, The Atomic Model Theorem
and Related Model Theoretic Principles \\ % (V)
{\bf 11:30--13:00} & Lunch\\
{\bf 13:30--14:20} & Towsner, How Constructive is
Furstenberg's Multiple Recurrence Theorem? \\
{\bf 14:20--15:00 } & Coffee Break, 2nd floor lounge, Corbett Hall\\
{\bf 15:00--15:50} & Jockusch, Bounded diagonalization and
Ramseyan results on edge-labeled ternary trees \\
{\bf 16:00--16:20} & Stephan, Implementing Fragments of ZFC within
an r.e.\ Universe \\
{\bf 16:30--16:50} & Harizanov, Computability and orders on
structures \\
{\bf 17:00--17:20} & Schmerl, Grundy colorings of graphs\\
{\bf 17:30--19:30} & Dinner\\
{\bf 20:00--?} & Possible Problem Session
\end{tabular}
\vspace{.25in}
\begin{tabular}{ll}
{\bf\large Friday} & \\ & \\
{\bf 7:00--9:00} & Breakfast\\
{\bf 9:00--11:30}
& Informal Discussions, if desired \\
{\bf 10:00-11:00} & Coffee Break, 2nd floor lounge, Corbett Hall\\
{\bf 11:30--13:30} & Lunch\\
\end{tabular}
\begin{tabular}{ll}
{\bf Checkout by 12 noon.} & \\
\end{tabular}
\bigskip
\noindent
** 5-day workshops are welcome to use the BIRS facilities (2nd Floor
Lounge, Max Bell Meeting Rooms, Reading Room) until 3 pm on Friday,
although participants are still required to checkout of the guest
rooms by 12 noon. **
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% ABSTRACTS
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage
\begin{center}
\Large{\bf Computability, Reverse Mathematics and Combinatorics}\\
\Large{\bf December 7--12, 2008}\\
\end{center}
\medskip
\begin{center}
{\bf ABSTRACTS}\\
\end{center}
\noindent
Speaker: {\bf Sam Buss} (Univ.\ of Calif., San Diego)\\
Title: {\it Polynomial Local Search higher in the Polynomial Hierarchy
and Bounded Arithmetic}\\
Abstract: The talk will discuss provably total functions of bounded
arithmetic, and recent characterization of the $\Sigma^b_i$ definable
functions of $S^{k+1}_2$ (or $T^k_2$), for all $i \leq k$ . The main
tool is extensions of polynomial local search problems to higher
levels of the polynomial time hierarchy, where the feasible set is
defined by a $\Pi^b_k$ predicate but the cost and neighborhood
functions are definable by polynomial time terms. These higher level
PLS problems can be used to determine the truth of $\Pi^b_k$
properties and also allow ``witness doubling''. These results can be
formalized and then Skolemized with a weak base theory such as $S^1_2$
--- the stronger theory $S^{k+1}_2$ (or $T^k_2$) is needed only to
prove the existence of a solution.
% --- the theory $T^k_2$ is needed only to prove
% the existence of a solution.
The Skolemization allows us to define sets of clauses that are
refutable in a depth m propositional refutation system (a Tait style
system for propositional logic), but are conjectured not to be
provable in a depth $m-1/2$ system. We discuss open problems and
future directions for research. This work is joint with Arnold
Beckmann.
\bigskip
\noindent
Speaker: {\bf Timothy J.\ Carlson} (Ohio State)\\
Title: {\it Combinatorics of Words}\\
Abstract: We will discuss some results on the infinite combinatorics
of words and their connection to idempotent ultrafilters.
\bigskip
\noindent
Speaker: {\bf Douglas Cenzer} (University of Florida)\\
Title: {\it Space Complexity of Abelian Groups}\\
Abstract: We develop a theory of $LOGSPACE$ structures and apply it
to construct a number of examples of Abelian Groups which have
$LOGSPACE$ presentations. We show that all computable torsion
Abelian groups have $LOGSPACE$ presentations and we show that the
groups $\mathbb Z$, $Z(p^\infty)$, and the additive group of the
rationals have $LOGSPACE$ presentations over a standard universe
such as the tally representation and the binary representation of
the natural numbers. We also study the effective categoricity of
such groups. For example, we give conditions are given under which
two isomorphic $LOGSPACE$ structures will have a linear space
isomorphism. Joint with Rodney G.\ Downey, Jeffrey B.\ Remmel, and
Zia Uddin.
\bigskip
\noindent
Speaker: {\bf Chi Tat Chong} (National University of Singapore)\\
Title: {\it $\Pi^1_1$ conservation of the COH Principle
over models of $B\Sigma_2$}\\
Abstract: We report on the joint work with Ted Slaman and Yue Yang.
The combinatorial principle COH states that every array coded in a
model has a set in the model cohesive for the array. Cholak, Jockusch
and Slaman have proved that over the base theory RCA$_0$,
COH$+\Sigma^0_2\ \mbox{induction}$ ($I\Sigma^0_2$) is
$\Pi^1_1$-conservative over $I\Sigma^0_2$ , i.e.~the stronger theory
with COH added does not prove new $\Pi^1_1$ statements. We show that
this result extends to models of RCA$_0+B\Sigma^0_2$.
\bigskip
\noindent
Speaker: {\bf Valentina Harizanov} (George Washington University)\\
Title: {\it Computability and orders on structures}\\
Abstract: A magma is left-orderable if there is a linear ordering of
its domain, which is left invariant with respect to the magma
operation. If the ordering is also right invariant, then the magma is
bi-orderable. For arbitrary magmas (not necessarily associative),
there is a natural topology on the set of all left orders, and this
space is compact. We will focus on computable orderable groups, in
particular, free groups, and computability theoretic complexity of
their orders.
\bigskip
\noindent
Speaker: {\bf Denis Hirschfeldt} (University of Chicago)\\
Title: {\it The Atomic Model Theorem and Related Model
Theoretic Principles}\\
Abstract: The Atomic Model Theorem states that every complete
countable atomic theory has a countable atomic model. In this talk I
will describe joint work with Richard A. Shore and Theodore A. Slaman
on the computability theoretic and reverse mathematical strength of
this and related results on atomic models and type omitting.
\bigskip
\noindent
Speaker: {\bf Jeffry L.\ Hirst} (Appalachian State University)\\
Title: {\it Two variants of Ramsey's theorem}\\
Abstract: This talk will explore the computability theory and reverse
mathematics of some versions of Ramsey's theorem, including Ramsey's
theorem on trees ($ {\sf TT}^n_k$) and the polarized Ramsey's theorem
(${\sf PT}^n_k$). Here are statements of those theorems:
$ {\sf TT}^n_k$: Let $2^{< \mathbb N}$ denote the full binary tree and
$[2^{< \mathbb N}]^n$ denote all $n$-tuples of comparable nodes in
$2^{< \mathbb N}$. If $f: [2^{< \mathbb N}]^n \to k$, then we can
find a $c