Nicholas Kocurek

Research

I am broadly interested in theoretical computer science and particularly in beyond worst-case complexity. Recently I've been thinking broadly about how Markov chains mix and the structure of CSPs from a Sum-of-Squares viewpoint.

Here are some of my projects, in reverse chronological order:

• Faster Mixing of Higher-Dimensional Random Reversible Circuits

  with William Gay and William He

  Manuscript

• Tight Semirandom CSP Refutation and Alphabet-Dependent SoS Lower Bounds

  with Peter Manohar

  Manuscript (Coming Soon)

• Streaming Stable Matchings

  with Harrison Wiseblatt

  Manuscript

Teaching

In Fall 2024, I am TAing 15-251: Great Ideas in Theoretical Science, 15-252: More Great Ideas in Theoretical Computer Science, and 15-354: Computational Discrete Math at CMU.

In the past I have TAed:

• CMU 15-251: Great Ideas in Theoretical Science (Fall 2022-Spring 2024)
• CMU 15-455: Undergraduate Complexity Theory (Spring 2024)

Along with teaching, I was also part of the CMU School of Computer Science's Student Advisory Council.

Miscellaneous

I am a big fan of mystery novels, Pittsburgh sports, and playing social deduction and horror games with my friends.

Here is a simple diagram explaining the etymology of "kolache" in Texas.