Title: Some applications of logic to additive number theory

Abstract: I will review the Loeb measure construction; I will
assume some exposure to nonstandard analysis, or at least 1st order logic,
comparable to the review I gave last semester in my seminars on fixed
points. Time permitting I will give the Loeb-measure proof of Szemeredi’s
Theorem.

Logic seminar: David Ross
Title: Some applications of logic to additive number theory (cont.)
Room: Keller 404.

Abstract:
I will continue with some examples of results about sets of positive upper Banach density proved using Loeb measures.

The Logic Seminar will meet again this Friday. The speaker will be Bjørn Kjos-Hanssen.

Title:
Superposition as memory: unlocking quantum automatic complexity

Time:
Friday March 17, 2:30-3:20

Place: Keller 404 (Note: this might change)

Abstract:
Imagine a lock with two states, “locked” and “unlocked”, which may be manipulated using two operations, called 0 and 1. Moreover, the only way to (with certainty) unlock using four operations is to do them in the sequence 0011, i.e., $0^n1^n$ where $n=2$. In this scenario one might think that the lock needs to be in certain further states after each operation, so that there is some memory of what has been done so far. Here we show that this memory can be entirely encoded in superpositions of the two basic states “locked” and “unlocked”, where, as dictated by quantum mechanics, the operations are given by unitary matrices. Moreover, we show using the Jordan–Schur lemma that a similar lock is not possible for $n=60$.

The Logic Seminar will meet again this Friday, usual place: Keller Hall 404. The speaker will be Achilles Beros.

Title: Teachers, Learners and Oracles

Abstract: When identifying r.e. sets from enumeration, a teacher is a
computational aide that pre-processes the data and only passes the
“useful” examples to the learner. Access to a teacher does not affect
the learnability of a family of r.e. sets, but it can affect the speed
with which learning is accomplished. Another computational aide is the
membership oracle. We consider four different forms of polynomial
bounds on learning and compare the performance of learners equipped with
teachers and learners equipped with oracles. We find that in most cases
neither strategy is uniformly superior. In this talk I will survey the
results and show a proof that utilizes a strategy analogous to integrity
checks in TCP (Transmission Control Protocol). The paper presented is
joint work with Colin de la Higuera.