BEGIN:VCALENDAR
PRODID:-//PSU Mathematics Department//Seminar iCalendar Generator//EN
VERSION:2.0
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Logic Seminar
X-WR-TIMEZONE:America/New_York
BEGIN:VTIMEZONE
TZID:America/New_York
X-LIC-LOCATION:America/New_York
BEGIN:DAYLIGHT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
TZNAME:EDT
DTSTART:19700308T020000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=2SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
DTSTART:19701101T020000
RRULE:FREQ=YEARLY;BYMONTH=11;BYDAY=1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140114T143000
DTEND;TZID=America/New_York:20140114T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20068
SUMMARY:Logic Seminar - Organizational Session
DESCRIPTION:Seminar: Logic Seminar\nTitle: Organizational Session\nSpeaker:
Jan Reimann\, Penn State
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140121T143000
DTEND;TZID=America/New_York:20140121T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20071
SUMMARY:Logic Seminar - Applications of computable conditional probability
to randomness
DESCRIPTION:Seminar: Logic Seminar\nTitle: Applications of computable condi
tional probability to randomness\nSpeaker: Jason Rute\, Penn State\nAbstra
ct: In this talk\, I will discuss the computability of conditional probabi
lity and how it can be used to prove results about randomness. The primar
ily result is that if x is computably random and T is a computable map for
which the conditional probability P[ | T] is also computable\, then T(x)
is computably random on the push-forward measure P_T. I will discuss othe
r applications of computable conditional probability as well. (The slides
from a previous version of this talk are available here\, http://www.pers
onal.psu.edu/jmr71/talks/rute_2013_ARA.pdf .)
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140128T143000
DTEND;TZID=America/New_York:20140128T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20074
SUMMARY:Logic Seminar - Algorithmic Randomness and Stochastic Processes II
DESCRIPTION:Seminar: Logic Seminar\nTitle: Algorithmic Randomness and Stoch
astic Processes II\nSpeaker: Adrian Maler\, Penn State\nAbstract: Having p
reviously introduced effective Skorokhod space\, a suitable setting for ge
neralizing Martin-Löf randomness to sample paths of discontinuous stochas
tic processes\, we discuss results pertaining to random sample paths of co
mputable Levy processes\; in particular\, Poisson processes.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140204T143000
DTEND;TZID=America/New_York:20140204T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20077
SUMMARY:Logic Seminar - Algorithmically random probability measures
DESCRIPTION:Seminar: Logic Seminar\nTitle: Algorithmically random probabili
ty measures\nSpeaker: Quinn Culver\, Notre Dame University\nAbstract: We d
efine a natural\, computable map that associates to each real a Borel prob
ability measure on Cantor space\, so that we can talk about random measure
s\, the images of the (ML) random reals. We show that such random measures
are atomless yet mutually singular with respect to the Lebesgue measure.
We show also that any two relatively random measures share a random real
\, yet are mutually singular. We finish with some miscellaneous results a
nd some open questions.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140211T143000
DTEND;TZID=America/New_York:20140211T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20080
SUMMARY:Logic Seminar - On the computability of rates of metastable converg
ence
DESCRIPTION:Seminar: Logic Seminar\nTitle: On the computability of rates of
metastable convergence\nSpeaker: Jason Rute\, Penn State\nAbstract: There
are many ways to express that a sequence converges. They range from the m
ost explicit but least uniform---a rate of convergence\; to the moderately
explicit and moderately uniform---a bound on the number of jumps by epsil
on\; to the least explicit but most uniform---a bound of metastable conver
gence (which I will define in this talk).\n\nUsing proof theory\, Kolhenba
ch showed that (under certain conditions) uniform metastable bounds can be
computably extracted from the proof of a convergence theorem. Using model
theory\, Avigad and Iovino showed that (under similar conditions) metasta
ble bounds of a convergence theorem are always uniform---but their methods
do not provide a way to compute the bounds. Using computable analysis and
computable model theory\, I show that not only are the bounds always unif
orm\, but they can computed from the statement of the theorem alone (witho
ut regards to the proof).
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140218T143000
DTEND;TZID=America/New_York:20140218T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20083
SUMMARY:Logic Seminar - NO SEMINAR THIS WEEK
DESCRIPTION:Seminar: Logic Seminar\nTitle: NO SEMINAR THIS WEEK\nSpeaker: N
O SEMINAR THIS WEEK
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140225T143000
DTEND;TZID=America/New_York:20140225T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20086
SUMMARY:Logic Seminar - Invariant measures on homogeneous structures
DESCRIPTION:Seminar: Logic Seminar\nTitle: Invariant measures on homogeneou
s structures\nSpeaker: Jan Reimann\, Penn State\nAbstract: Many constructi
ons of universal homogeneous structures can be randomized. The most famous
example is arguably the Rado graph\, which can obtained by chosing edges
randomly with probability 0 < p < 1. Other examples include the universal
K_n-free graph (Petrov and Vershik)\, and the Urysohn space (Vershik). The
existence of such a randomized construction is closely tied to the existe
nce of a measure on the homogeneous structure that is invariant under the
logic action. In this talk I will survey a number of important results on
such measures.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140304T143000
DTEND;TZID=America/New_York:20140304T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20089
SUMMARY:Logic Seminar - Reverse mathematics\, Young diagrams\, and the ACC
DESCRIPTION:Seminar: Logic Seminar\nTitle: Reverse mathematics\, Young diag
rams\, and the ACC\nSpeaker: Stephen G. Simpson\, Pennsylvania State Unive
rsity\nAbstract: In abstract algebra\, a ring is said to satisfy the ACC (
ascending chain condition) if it has no infinite ascending sequence of ide
als. According to a famous and controversial theorem of Hilbert\, 1890\,
polynomial rings with finitely many indeterminates satisfy the ACC. There
is also a similar theorem for noncommuting indeterminates\, due to J. C.
Robson\, 1978. In 1988 I performed a reverse-mathematical analysis of the
theorems of Hilbert and Robson\, proving that they are equivalent over RC
A_0 to the well-orderedness of (the standard notation systems for) the ord
inal numbers omega^omega and omega^{omega^omega} respectively. Now I perf
orm a similar analysis of a theorem of Formanek and Lawrence\, 1976. Let
S be the group of finitely supported permutations of the natural numbers.
Let K[S] be the group ring of S over a countable field K of characteristi
c 0. Formanek and Lawrence proved that K[S] satisfies the ACC. All of th
ese results concerning the ACC involve well partial ordering theory. I no
w prove that the Formanek/Lawrence theorem is equivalent over RCA_0 to the
well-orderedness of omega^omega. The proof involves an apparently new\,
combinatorial lemma concerning Young diagrams. I also show that\, in all
of these reverse-mathematical results\, RCA_0 can be weakened to RCA*_0.
This recent work was done jointly with Kostas Hatzikiriakou.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140318T143000
DTEND;TZID=America/New_York:20140318T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20095
SUMMARY:Logic Seminar - Ramsey-like Theorems and their Reverse Mathematical
Properties
DESCRIPTION:Seminar: Logic Seminar\nTitle: Ramsey-like Theorems and their R
everse Mathematical Properties\nSpeaker: John Pardo\, Pennsylvania State U
niversity\nAbstract: The basic statements of Ramsey's Theorem have long be
en a topic of great interest in the study of reverse mathematics. Thus\,
it naturally makes sense to look at "Ramsey-like Theorems"\, i.e. results
which are stated in a similar fashion to the usual Ramsey's Theorem\, in o
rder to better understand the so-called reverse mathematical zoo. I will
discuss several such Ramsey-like Theorems and explain some of the refineme
nts to the reverse mathematical zoo that we are able to achieve with them.
This talk is based on recent work by Keita Yokoyama.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140326T160000
DTEND;TZID=America/New_York:20140326T170000
LOCATION:MB106
URL:http://www.math.psu.edu/seminars/meeting.php?id=23124
SUMMARY:Logic Seminar - Martin-Löf random Brownian motion
DESCRIPTION:Seminar: Logic Seminar\nTitle: Martin-Löf random Brownian moti
on\nSpeaker: Kelty Allen\, UC Berkeley\nAbstract Link: http://\nAbstract:
Brownian motion is a probabilistic process that can be defined as a limit
of random walks and captures the idea of a random continuous function. App
lying techniques from algorithmic randomness to Brownian motion provides n
ew insight into Brownian motion and the power of algorithmic randomness.
\n\nIn this talk we will define Martin-Lof random Brownian motion and inve
stigate some of its properties. We will see some of the "almost surely" re
sults from classical probability theory that hold for every Martin-Lof ran
dom Brownian path\, and discuss some of the computability theoretic proper
ties of Martin-Lof random Brownian motion.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140401T143000
DTEND;TZID=America/New_York:20140401T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20101
SUMMARY:Logic Seminar - Degrees of unsolvability: a survey.
DESCRIPTION:Seminar: Logic Seminar\nTitle: Degrees of unsolvability: a surv
ey.\nSpeaker: Stephen G. Simpson\, Pennsylvania State University\nAbstract
: In 1936 Turing produced the first example of a mathematical problem whic
h is algorithmically unsolvable. This was followed by various attempts to
classify such problems according to their degrees of unsolvability\, i.e.
\, the amount of algorithmic unsolvability which is inherent in them. The
theory of Turing degrees applies to decision problems and is very rich\,
but unfortunately not very useful for the original purpose. The more rece
nt theory of Muchnik degrees applies to a more general class of problems k
nown as mass problems\, and is therefore much more relevant in this respec
t. Recent investigations have revealed many examples of natural\, specifi
c\, Muchnik degrees which can be used to classify unsolvable problems aris
ing in various contexts\, especially algorithmic randomness and reverse ma
thematics. I will survey various results of this type. I will also annou
nce a structural result\, to the effect that the lattice of Muchnik degree
s of effectively closed sets is dense. This new result will appear in a j
oint paper by Binns\, Shore\, and myself.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140408T143000
DTEND;TZID=America/New_York:20140408T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20104
SUMMARY:Logic Seminar - Invariant measures on Triangle-free graphs
DESCRIPTION:Seminar: Logic Seminar\nTitle: Invariant measures on Triangle-f
ree graphs\nSpeaker: Jan Reimann\, Penn State\nAbstract: We present the co
nstruction\, due to Petrov and Vershik (2010)\, of a measure on the set of
all countable infinite graphs that concentrates on the triangle free grap
hs and is invariant under the canonical action of the symmetric group of t
he natural numbers.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140415T143000
DTEND;TZID=America/New_York:20140415T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20107
SUMMARY:Logic Seminar - Invariant measures on Triangle-free graphs (II)
DESCRIPTION:Seminar: Logic Seminar\nTitle: Invariant measures on Triangle-f
ree graphs (II)\nSpeaker: Jan Reimann\, Penn State\nAbstract: We finish th
e construction by Petrov and Vershik of an invariant measure on the counta
ble triangle-free graphs and describe how this construction can be general
ized to arbitrary structures with trivial definable closure (due to Ackerm
an-Freer-Patel).
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140418T143000
DTEND;TZID=America/New_York:20140418T154500
LOCATION:MB216
URL:http://www.math.psu.edu/seminars/meeting.php?id=22843
SUMMARY:Logic Seminar - An Analytic Approach to Quasirandom (Hyper)graphs
DESCRIPTION:Seminar: Logic Seminar\nTitle: An Analytic Approach to Quasiran
dom (Hyper)graphs\nSpeaker: Henry Towsner\, University of Pennsylvania\nAb
stract: The many equivalent characterizations of quasirandomness for graph
s have been extensively studied. When generalized to hypergraphs\, these n
otions split into a partially ordered family of distinct notions\, recentl
y shown by Lenz and Mubayi to not even be linearly ordered.\n\nThe ultrapr
oduct setting\, equipped with Loeb measure\, turns out to be a natural pla
ce to examine these notions. We show that notions of hypergraph randomnes
s have a natural analytic characterization---orthogonality to certain sigm
a algebras generated by definable sets---and that all the notions which ha
ve been previously studied can be considered examples of this phenomenon.
We use this to generalize several results known about some notions to all
these randomness notions.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140422T143000
DTEND;TZID=America/New_York:20140422T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20110
SUMMARY:Logic Seminar - Introduction to Kleene's realizability interpretati
on of intuitionistic number theory
DESCRIPTION:Seminar: Logic Seminar\nTitle: Introduction to Kleene's realiza
bility interpretation of intuitionistic number theory\nSpeaker: Sankha Bas
u\, Penn State\nAbstract: Kleene\, in his 1945 paper "On the interpretatio
n of intuitionistic number theory"\, introduced the notion of recursive re
alizability. The notion of realizability provides a connection between int
uitionism and the theory of recursive functions. Since then\, over the las
t 70 years\, this has developed into a major subject of interest\, and has
infiltrated many other realms of the study of logic and foundations. In t
his talk\, I will introduce and discuss the above notion of recursive real
izability as laid out in Kleene's "Introduction to Metamathematics"\, publ
ished in 1948.
END:VEVENT
BEGIN:VEVENT
DTSTART;TZID=America/New_York:20140429T143000
DTEND;TZID=America/New_York:20140429T154500
LOCATION:MB315
URL:http://www.math.psu.edu/seminars/meeting.php?id=20113
SUMMARY:Logic Seminar - Lebesgue density and \\Pi^0_1 classes
DESCRIPTION:Seminar: Logic Seminar\nTitle: Lebesgue density and \\Pi^0_1 cl
asses\nSpeaker: Mushfeq Khan\, University of Wisconsin - Madison\nAbstract
: Analyzing the effective content of the Lebesgue density theorem was an i
mportant step towards the recent solutions of the ML-covering and ML-cuppi
ng problems. Two new classes of reals emerged from this analysis: the posi
tive density points with respect to effectively closed (or \\Pi^0_1) sets
of reals\, and a proper subclass\, the density-one points. Bienvenu\, Holz
l\, Miller\, and Nies have shown that the ML-random positive density point
s are exactly the ones that do not compute the halting problem. Using this
theorem as a starting point\, I will discuss several new results on the i
nteractions between density\, domination properties\, minimality\, complet
eness\, 1-genericity\, and randomness.
END:VEVENT
END:VCALENDAR