Midwest
Computability Seminar
XXV
Part i
The Midwest Computability
Seminar is meeting remotely in the fall of 2020. The recurring Zoom link is:
https://notredame.zoom.us/j/99754332165?pwd=RytjK1RFZU5KWnZxZ3VFK0g4YTMyQT09
Meeting ID: 997 5433 2165
Passcode: midwest
Slides YouTube video
Panopto
video
This session will be held jointly with the Computability Theory and Applications Online Seminar.
DATE: Tuesday, August 18th, 2020
TIME: 3:00 - 4:00 PM CDT
SPEAKER: Joe Miller - University of Wisconsin–Madison
TITLE: Redundancy of information: lowering effective dimension
ABSTRACT:
A natural way to measure the similarity between two infinite
binary sequences X and Y is to take the (upper) density of
their
symmetric difference. This is the Besicovitch distance on Cantor
space. If d(X,Y) = 0, then we say that X and
Y are coarsely
equivalent. Greenberg, M., Shen, and Westrick (2018) proved that a
binary sequence has effective (Hausdorff) dimension 1 if and only if
it is coarsely equivalent to a Martin-Löf random sequence. They
went
on to determine the best and worst cases for the distance from a
dimension t sequence to the nearest dimension s>t
sequence. Thus, the
difficulty of increasing dimension is understood.
Greenberg, et al. also determined the distance from a dimension 1
sequence to the nearest dimension t sequence. But they left open
the
general problem of reducing dimension, which is made difficult by the
fact that the information in a dimension s sequence can be coded
(at
least somewhat) redundantly. Goh, M., Soskova, and Westrick recently
gave a complete solution.
I will talk about both the results in the 2018 paper and the more
recent work. In particular, I will discuss some of the coding theory
behind these results. No previous knowledge of coding theory is
assumed.
Future Sessions
- September 1st, 2020: Patrick Lutz - University of California,
Berkeley
- September 15th, 2020: Justin Miller - University of Notre Dame
- September 29th, 2020: Christopher Porter - Drake University
- October 13th, 2020: Leszek Kołodziejczyk - University of Warsaw
- October 27th, 2020: Li Ling Ko - University of Notre Dame
- November 10th, 2020: Paul Shafer - University of Leeds
- November 24th, 2020: Karen Lange - Wellesley College
- December 8th, 2020: Linda Westrick - The Pennsylvania State University
Previous Seminars:
- Sept 23rd 2008 Antonio
Montalbán - Logan Axon - Joe Miller
- Nov 11th 2008 Chris
Conidis - Keng Meng (Selwyn) Ng - Peter Gerdes
- Feb 3rd 2009 David
Diamondstone - Bart Kastermans - Richard A. Shore
- April 21st 2009 Dan Turetsky
- Julia Knight - Ted Slaman
- Sept 29th 2009 Carl Jockusch
- Rachel Epstein - Rebecca Weber
- Jan 26th 2010 Sara Quinn -
John Wallbaum - Steffen Lempp - Reed Solomon
- May 11th 2010 Adam Day -
Liang Yu - Rod Downey - Boris Zilber
- Sept 28th 2010 Maurice
Chiodo - Peter Gerdes - Damir Dzhafarov - Andy Lewis
- Feb 15th 2011 Uri Andrews -
Paola D'Aquino - David Diamondstone - Christopher Porter -
Rebecca Steiner
- Nov 1st 2011 Mingzhong Cai -
Chris Conidis - Stephen Flood -
Jeff Hirst - Asher Kach
- Nov 15th 2012 Achilles Beros
- Rod Downey - Jesse Johnson - Sam Sanders - Steven VanDendriessche -
Matthew Wright
- April 2nd 2013 Howard
Becker - Denis Hirschfeldt - Paul Schupp
- October 1st 2013 Peter Cholak
- Mushfeq Khan - Victor Ocasio-González - Jonathan Stephenson
- April 29th, 2014 Rod Downey -
Noam Greenberg - Gregory Igusa - Alexander Melnikov - Kyle Riggs
- September 30th, 2014 Eric Astor -
Quinn Culver - Jack Lutz - Timothy McNicholl
- February 17th, 2015 Carl Jockusch -
Julia Knight - Steffen Lempp
- January 28th, 2016 Reese Johnston -
Rutger Kuyper - Mariya Soskova - Mars Yamaleev
- October 22nd and 23rd, 2016
Special Meeting in Honor of Carl Jockusch's 75th Birthday
- March 16th, 2017 Greg Igusa -
Jack Lutz - Sasha Melnikov - Reed Solomon
- October 24th, 2017 Noah Schweber
- Don Stull - Dan Turetsky - Rose Weisshaar
- April 17th, 2018 Peter Cholak -
Meng-Che "Turbo" Ho - Ethan McCarthy - Joe Miller
- October 9th, 2018 Uri Andrews -
Timothy McNicholl - Alexandra Soskova
- April 18th, 2019 Wesley Calvert - Russell Miller - Steffen Lempp
- February 11th, 2020 Rachael Alvir - Tejas Bhojraj - Jun Le Goh - Neil Lutz
If you haven't
been receiving the announcements and would like to be included
in the list, send an email to drh@math.uchicago.edu.