​Dylan McKay
Lecturer at Yale University
Professional Email: first initial dot last name at yale dot ee dee you

---

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

Instructor Positions

Yale University
​Fall 2024

• CPSC 202: Mathematical Tools for Computer Science
• CPSC 468: Computational Complexity

Summer 2024

• CPSC S365: Algorithms

Spring 2024

• ​CPSC 365a and 365b: Algorithms

​Fall 2023

• CPSC 202: Mathematical Tools for Computer Science
• CPSC 442: Theory of Computation

Spring 2023

• ​CPSC 365a and 365b: Algorithms

​Fall 2022

• CPSC 202: Mathematical Tools for Computer Science
• CPSC 468: Computational Complexity

Oberlin College
​Spring 2022

• CSCI 383: Theory of Computation
• CSCI 384: Complexity Theory
• CSCI 151: Data Structures (Lab Instructor)

​Fall 2021

• CSCI 383: Theory of Computation
• CSCI 280: Algorithms​

​Spring 2021

• CSCI 383: Theory of Computation
• CSCI 384: Complexity Theory
• ​CSCI 150: Introduction to Computer Science (Lab Instructor)

​Fall 2020

• CSCI 383: Theory of Computation
• CSCI 150: Introduction to Computer Science (Lab Instructor)

Stanford University
Summer 2016

• CS 103: Mathematical Foundations for Computing

Georgia Tech
Summer 2015

• CS 3510: Design and Analysis of Algorithms

Teaching Assistantships

MIT
​Spring 2020

• 6.045: Automata, Computability, and Complexity
  Supervised by Ryan Williams

​Spring 2019

• 6.045: Automata, Computability, and Complexity
  Supervised by Ryan Williams

Fall 2018

• ​6.042: Mathematics for Computer Science
  Supervised by F. Thomson Leighton, Ankur Moitra, and Debayan Gupta

Fall 2017

• 6.841: Advanced Complexity Theory
  Supervised by Ryan Williams

Georgia Tech
Spring 2015

• CS 4510: Automata and Complexity
  Supervised by H. Venkateswaran

Fall 2014

• CS 6520: Complexity Theory
  Supervised by Richard Lipton

• ​MATH 2602: Linear and Discrete Mathematics
  Supervised by Sal Barone
• MATH 2602: Linear and Discrete Mathematics
  Supervised byShane Scott

Fall 2013

• CS 2050: Introduction to Discrete Mathematics
  Supervised by Monica Sweat

Summer 2013

• CS 3510: Design and Analysis of Algorithms
  ​Supervised by H. Venkateswaran
  
  
• MATH 3012: Applied Combinatorics*
  Supervised by Ruidong Wang
  
• MATH 3012: Applied Combinatorics*
  Supervised by Jing Hu
  

*The position for each of the Applied Combinatorics classes was a grading-only position.

Spring 2013

• CS 2051: Honors Discrete Mathematics
  Supervised by Dana Randall

Fall 2012

• MATH 2602: Linear and Discrete Mathematics
  Supervised by Alan Diaz

Spring 2012

• CS 2050: Introduction to Discrete Mathematics
  Supervised by Monica Sweat

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)

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.

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:

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