All UW logic students, faculty and staff (including family/partner) are welcome to attend! The UW logic faculty will provide burgers, brats (including vegetarian alternatives) and beverages. Please bring a salad or dessert to share.
We will leave from the Van Vleck loading dock at noon. Please do not drive directly to Devil's Lake unless your car is full so that everyone can get a ride.
Dan Rosendorf has agreed to organize the picnic. Please email him (rosendor@math.wisc.edu) to let him know how many there will be in your party, whether you can give or need a ride, and whether you are a vegetarian.
The first such seminar is tentatively scheduled for Tuesday, September 23. We will leave the UW campus at 9 a.m. and return around 11 p.m.
Everyone interested in coming along is asked to let me know as soon as possible so that we can plan transportation, which will be free to all logic students.
| Date | Time | Speaker | Title | Cookies, dinner, etc. |
| Tuesday, September 9 | 3:30 p.m. | Ken Kunen, UW | Locally connected compact spaces (see abstract) | cookies/beverages at 3 p.m. |
| 4:30 p.m. | Bart Kastermans, UW | Posets and stability (see abstract) | ||
| Tuesday, September 16 | 4 p.m. | Chris Conidis, University of Chicago | TBA | cookies at 3:30 p.m./ dinner at 6 p.m. |
| Tuesday, September 23 (University of Chicago) | 1:30 p.m. | Antonio Montalbán, University of Chicago | TBA | lunch at noon/ dinner at 6 p.m. |
| 3:00 p.m. | Logan Axon, University of Notre Dame | TBA | ||
| 4:30 p.m. | Joe Miller, UW | TBA | ||
| Tuesday, October 7 | 3:30 p.m. | Joe Miller, UW | TBA | cookies/beverages at 3 p.m. |
| 4:30 p.m. | TBA | TBA |
Instructor: Joe Miller
Prereq: Math 773
Description: Martin-Löf defined the random binary sequences as those which pass certain effectively presented statistical tests. Levin and Chaitin both used a form of Kolmogorov complexity to characterize Martin-Löf randomness in terms of incompressibility, while Schnorr gave a characterization in terms of betting games. Thus we have three equivalent formulations of effective randomness which can be seen as formalizing three different fundamental intuitions: random sequences are "unremarkable", "incompressible" and "unpredictable". This course will introduce Kolmogorov complexity, effective randomness, effective Hausdorff dimension, triviality and lowness. We will go from the basic definitions to recent results and open questions of current interest. Students should have had an introductory course in computability theory.
Time/Place: Tuesdays and Thursdays, 1:00 pm - 2:15 pm.
Room 1289 Computer Science and Stat Building
Instructor: Jin-Yi Cai
Description: This course is a first year graduate level introduction to Computational Complexity Theory.
We will start with a review of some topics from a typical undergraduate course in Theory of Computing, including such concepts as Turing machines, recursive functions, computability and incomputability, and the Church-Turing thesis.
We then consider time and space bounded computation; deterministic and non-deterministic time classes and space classes, LOGSPACE, NL, P, NP, PSPACE, etc; Savitch's theorem, Immerman-Szelepcsenyi Theorem, Cook-Levin Theorem, NP-completeness and P-completeness, Karp's problems. We will also introduce randomized complexity classes ZPP, RP, BPP; polynomial time hierarchy; Sipser-Lautemann Theorem, interactive proofs, Arthur-Merlin Games, LFKN protocol and Shamir's Theorem (with a proof by Shen, using "diagram chasing"), probabilistically checkable proofs; non-uniform complexity, Karp-Lipton Theorem, graph non-isomorphism problem; circuit lower bounds, bounded depth circuits; Counting problems and Valiant's theory, Permanent and determinant problem. If time permit we may also discuss other topics such as pseudorandom generators and hardness versus randomness, or dichotomy theorems.
The prerequisite for the course is a typical undergraduate course in Theory of Computing such as CS 520 or equivalent. Students without the formal prerequisite but who are mathematically capable generally are encouraged to talk to the professor, and most likely will find themselves quite equal to the challenge.
A 1982 question of M. E. Rudin and/or P. Nyikos asks whether MA + not CH implies that every locally connected hereditarily Lindelöf compact space is second countable. We show that the answer is "no" -- that is, there is a model of MA + not CH in which there is a counterexample. Filippov had produced an example under CH in 1969. There is no known ZFC example.
If you replace "locally connected" by "connected", then a ZFC example is easily made from the double arrow space.