Dylan McKay

Lecturer at Yale University

Professional Email: first initial dot last name at yale dot ee dee you

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)

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