Dylan McKay
Visiting Professor at Oberlin College
Oberlin email: dmckay
Visiting Professor at Oberlin College
Oberlin email: dmckay
Education
|
Massachusetts Institute of Technology
Stanford University Georgia Institute of Technology Georgia institute of Technology Budapest Semesters in Mathematics UCLA Logic Center Summer School in Logic |
PhD in Computer Science
MSc in Computer Science BSc in Computer Science BSc in Discrete Mathematics |
2017-2020
2015-2016 2011-2015 2011-2015 Spring 2014 Summer 2014 |
Teaching
|
Teaching Assistant
6.045 Spring 2020 Teaching Assistant 6.045 Spring 2019 Teaching Assistant 6.042 Fall 2018 Teaching Assistant 6.841 Fall 2017 Instructor CS 103 Summer 2016 Instructor CS 3510 Summer 2015 Teaching Assistant CS 4510 Spring 2015 Teaching Assistant CS 6520 Fall 2014 Teaching Assistant MATH 2602 Fall 2014 Teaching Assistant MATH 2602 Fall 2014 Teaching Assistant CS 2050 Fall 2013 Teaching Assistant CS 3510 Summer 2013 Grader MATH 3012 Summer 2013 Grader MATH 3012 Summer 2013 Teaching Assistant CS 2051 Spring 2013 Teaching Assistant MATH 2602 Fall 2012 Teaching Assistant CS 2050 Spring 2012 |
Under Ryan Williams
Automata, Computability, and Complexity Theory Massachusetts Institute of Technology Under Ryan Williams Automata, Computability, and Complexity Theory Massachusetts Institute of Technology Under F. Thomson Leighton, Ankur Moitra, and Debayan Gupta Mathematics for Computer Science Massachusetts Institute of Technology Under Ryan Williams Advanced Complexity Theory Massachusetts Institute of Technology Mathematical Foundations of Computing Stanford University Under advisement of H. Venkateswaran Design and Analysis of Algorithms Georgia institute of Technology Under H. Venkateswaran Automata and Complexity Georgia institute of Technology Under Richard Lipton Complexity Theory Georgia institute of Technology Under Sal Barone Linear and Discrete Mathematics Georgia institute of Technology Under Shane Scott Linear and Discrete Mathematics Georgia institute of Technology Under Monica Sweat Introduction to Discrete Mathematics Georgia institute of Technology Under H. Venkateswaran Design and Analysis of Algorithms Georgia institute of Technology Under Ruidong Wang Applied Combinatorics Georgia institute of Technology Under Jing Hu Applied Combinatorics Georgia institute of Technology Under Dana Randall Honors Discrete Mathematics Georgia institute of Technology Under Alan Diaz Linear and Discrete Mathematics Georgia institute of Technology Under Monica Sweat Introduction to Discrete Mathematics Georgia institute of Technology |
Publications
2019
"Relations and Equivalences Between Circuit Lower Bounds and Karp-Lipton Theorems" with Lijie Chen, Cody Murray, and Ryan Williams. To appear in CCC 2019 (link coming soon)
"Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes" with Cody Murray and Ryan Williams. To appear in STOC 2019 (link coming soon)
"Quadratic Time-Space Lower Bounds for Computing Natural Functions With a Random Oracle" with Ryan Williams, ITCS 2019. (link coming soon)
"Weak Lower Bounds on Resource-Bounded Compression Imply Strong Separations of Complexity Classes" with Cody Murray and Ryan Williams. To appear in STOC 2019 (link coming soon)
"Quadratic Time-Space Lower Bounds for Computing Natural Functions With a Random Oracle" with Ryan Williams, ITCS 2019. (link coming soon)
2017
"Theoretical Foundations of Team Matchmaking" with Josh Alman, AAMAS 2017.
Thesis (2020)
Intermediate Lowers Bounds and Their Relationship with Complexity Theory (link or pdf upload coming soon)
Fun Open Problems
."Mathematical Bugs" - problems which are easy to understand and seem very easy but are still open and are probably extremely difficult to resolve. [Disclaimer: my aim in putting these problems here is not to encourage anyone to work on these problems for a significant amount of time.]
Is there an algorithm which decides if the output of a circuit over subsets of the natural numbers outputs the empty set? Reference.
Is there a binary operation over the non-negative reals which satisfies the metric axioms and the group axioms? (Disclaimer: I don't know if this problem is actually open) Reference.
Is it true that for every finite union-closed family of sets, there is some x such that x is in at least half of the sets (in the family)? This is the Frankl Conjecture. Reference.
Given a list of integers x_1, x_2, x_3,..., x_n, and an integer k, how quickly can we decide if sqrt(x_1)+sqrt(x_2)+...+sqrt(x_n) < k? There is no known proof that this can be done in polynomial time... Reference.
Is there a binary operation over the non-negative reals which satisfies the metric axioms and the group axioms? (Disclaimer: I don't know if this problem is actually open) Reference.
Is it true that for every finite union-closed family of sets, there is some x such that x is in at least half of the sets (in the family)? This is the Frankl Conjecture. Reference.
Given a list of integers x_1, x_2, x_3,..., x_n, and an integer k, how quickly can we decide if sqrt(x_1)+sqrt(x_2)+...+sqrt(x_n) < k? There is no known proof that this can be done in polynomial time... Reference.
Selected Outreach
As an undergrad, I started an organization at Georgia Tech called Big O to bring together undergraduates interested in CS Theory and Math. I still give talks there when I visit. I also regularly participate in ESP at Stanford and MIT because I like teaching cool things to high school and middle school students, too!
If you are looking for volunteers for things similar to what I described, please feel free to let me know!
Past SPLASH/SPARK classes through ESP:
If you are looking for volunteers for things similar to what I described, please feel free to let me know!
Past SPLASH/SPARK classes through ESP:
- 2015 Fall Stanford:
- "That's so Random!" with Josh Alman and Michael Kim.
- 2016 Spring Stanford:
- "That's so Random!" with Josh Alman and Michael Kim.
- "The Mathematics of Games" with Josh Alman and Michael Kim.
- 2017 Spring MIT:
- "Compass and Straightedge Constructions" with Josh Alman.