Calendar

Mar
17
Fri
Kjos-Hanssen: Superposition as memory
Mar 17 @ 2:30 pm – 3:30 pm

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$.

Mar
20
Mon
9.7
Mar 20 @ 9:30 am – 10:30 am
Mar
22
Wed
9.8 (9.3, 9.4, 9.5 due)
Mar 22 @ 9:30 am – 10:30 am
Mar
24
Fri
week 11 starts
Mar 24 all-day
9.9
Mar 24 @ 9:30 am – 10:30 am
Logic seminar: Achilles Beros @ Keller Hall 404
Mar 24 @ 2:30 pm – 3:30 pm

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.

Apr
3
Mon
9.10 Binomial series (optional)
Apr 3 @ 9:30 am – 10:30 am
Apr
5
Wed
Review
Apr 5 @ 9:30 am – 10:30 am
Apr
7
Fri
Midterm 3 (8.7, 9.1-9.5)
Apr 7 @ 9:30 am – 10:30 am
Logic seminar: Jack Yoon @ Keller 404
Apr 7 @ 2:30 pm – 3:20 pm

The Logic Seminar will meet again this Friday, usual place and time. The speaker will be Jack Yoon.

Title: Proof Mining

Abstract: Proof mining (proof unwinding) is a technique used to extract
constructive information from seemingly non-constructive proofs. We
discuss the idea behind the topic and describe the foundations which
form the basis for proof mining.

Apr
10
Mon
Week 12 starts; start Ch. 16
Apr 10 all-day
16.1
Apr 10 @ 9:30 am – 10:30 am
Apr
12
Wed
16.1
Apr 12 @ 9:30 am – 10:30 am
Due: 9.6, 9.7, 9.8, 9.9
Apr 12 @ 9:30 am – 10:30 am
Apr
17
Mon
Week 13 starts
Apr 17 all-day
16.2 (theory)
Apr 17 @ 9:30 am – 10:30 am
Apr
19
Wed
16.2 (applications) (16.1 due)
Apr 19 @ 9:30 am – 10:30 am
Apr
21
Fri
Solving jellybeans equation + 17.1
Apr 21 @ 9:30 am – 10:30 am
Apr
24
Mon
Week 14 starts
Apr 24 all-day
17.1
Apr 24 @ 9:30 am – 10:30 am
Apr
26
Wed
“Week 15″ starts: polar coordinates
Apr 26 all-day
10.1 (16.2 due)
Apr 26 @ 9:30 am – 10:30 am
Apr
28
Fri
10.2 (graphing r=f(theta))
Apr 28 @ 9:30 am – 10:30 am
Logic Seminar: Jack Yoon @ Keller 404
Apr 28 @ 2:30 pm – 3:30 pm

Jack Yoon will continue his explication of Proof Mining.

May
1
Mon
3.9, 10.3
May 1 @ 9:30 am – 10:30 am
May
3
Wed
Review (17.1, 10.1, 10.2, 3.9, 10.3 due)
May 3 @ 9:30 am – 10:30 am
May
5
Fri
Logic Seminar: David Webb
May 5 @ 1:00 pm – May 5 @ 2:00 pm

David Webb will speak at 1:00-2:00 in Keller 402

Title: Every Function Can be Computable

Abstract: I will relay an interesting result of Joel David Hamkins: that
there is an algorithm which can compute any function f of natural
numbers, if it is carried out in the right model of arithmetic
(corresponding to f). In particular, I will construct the necessary
models using Rosser sentences and describe the algorithm.

May
7
Sun
TA’s review session in Bilger 335 @ Bilger 335
May 7 @ 10:45 am – 12:00 pm
May
9
Tue
Review session MATH 252A Keller 401
May 9 @ 10:30 am – 11:45 am
May
10
Wed
MATH 252A final exam in Sakamaki A-101
May 10 @ 12:00 pm – May 10 @ 2:00 pm