# CS Theory @ CU Boulder

Welcome to the website of the CS theory group at CU Boulder! Our faculty and students research all aspects of theoretical computer science, from core areas such as algorithms, complexity, and cryptography, to connections with other fields such as machine learning, algebraic geometry, economics, dynamical systems, biology, and control theory.

Follow us @bouldertheory on Twitter or @bouldertheory.bsky.social on BlueSky. To hear about upcoming talks, events, and other opportunities, please join the cs-theory-announce email list.

Check out our **Theory Seminar** and **Theory Reading Groups****.**

We're grateful to have our internal group discussions powered by a sponsored hosted instance of Zulip (for academic research).

## Positions

- We are a growing group, and are currently taking on students at both the master and doctoral level.
- We frequently mentor undergraduates (and occasionally high school students) in research projects. If you share interests with one of the professors in the group, please reach out to them by email directly to inquire about potential opportunities. (Not limited to CU students.)

## Faculty

(Core faculty in the CS Theory Group)

Huck Bennett (joined Jan '24!): lattices, fine-grained complexity, geometric and algebraic algorithms

Rafael Frongillo: theoretical machine learning, algorithmic economics, symbolic dynamics

Joshua Grochow: computational complexity (esp. algebraic and geometric), algebraic algorithms, complex systems and dynamics, complex networks

Ashutosh Trivedi: cyber-physical system analysis, stochastic systems, logic and automata

Bo Waggoner: algorithmic game theory, theoretical machine learning, differential privacy

## Theory-Associated Faculty

(Faculty from across the university who are at least "CS Theory"-adjacent in terms of their research, and/or whom the Theory Group frequently interacts with)

Stephen Becker, Applied Math: convex and non-convex optimization, signal processing, numerical linear algebra, compressed sensing and sparse/low-rank recovery

John Black: cryptography, combinatorial algorithms, graph theory

Sebastian "Yano" Casalaina-Martin, Math: algebraic geometry (curves, abelian varieties, cubic threefolds, vector bundles, moduli spaces)

Lijun Chen, CS & Telecommunications: optimization, control, game theory, networked systems theory

Aaron Clauset, CS & BioFrontiers Institute: network science, computational social science, computational systems biology

Josh Combes, Physics: quantum computation, quantum error correction, and quantum measurement theory

Emiliano Dall'anese, Electrical, Computer, and Energy Engineering (ECEE): Online optimization, learning, data-driven control, cyber-physical systems, energy systems

David Grant, Math: number theory (finding rational points on curves and abelian varieties), space-time codes, cryptography

Keith Kearnes, Math: algebra, logic, combinatorics

Kyle Luh, Math: random matrices and randomized algorithms

Peter Mayr, Math: algebra, foundations, computational problems

Claire Monteleoni, CS: machine learning algorithms and theory (data streams, unsupervised learning, latent structure, privacy), applications for social good (climate informatics, environment, sustainability)

Rebecca Morrison, CS: probabilistic modeling and graphs, data-driven models with physical constraints, uncertainty quantification

Grzegorz Rozenberg, CS (Adjoint) and Leiden University: DNA computing, theory of concurrent systems, theory of transition systems, theory of traces, graph transformations, formal languages and automata, 2-structures

Sriram Sankaranarayanan, CS: cyber-physical system analysis, probabilistic program verification, randomized algorithms

Katherine Stange, Math: cryptography and number theory, including post-quantum cryptography

Ágnes Szendrei, Math (emeritus): algebra, combinatorics, logic (including computational problems)

Jonathan Wise, Math: algebraic geometry (logarithmic geometry, deformation theory, moduli of curves, Gromov-Witten theory)

## Postdocs

### Former

Nathan Lindzey (starting as Assistant Professor at University of Memphis Dept. of Mathematics in Fall '24)

Ewan Davies (now Assistant Professor at Colorado State University)

Abhiram Natarajan (now EPSRC Fellow at U. Warwick)

Eric Reckwerdt (now Instructor in the post-bacc program at CU Boulder)

## Ph.D. Students

Robin Bowers

Robert Green

Melody Hsu

Gülce Kardeş

Drona Khurana

Dhamma Kimpara

Elias Lindgren

Mary Monroe

Rick Nueve

Maneesha Papireddygari

Elise Tate

Anish Thilagar

### Former

Maya Ornstein (Math, Ph.D. 2023, now Instructor at U. Colorado Boulder Mathematics)

Charlie Carlson (Ph.D. 2023, now postdoc at UC Santa Barbara)

Tzu-Chi Yen (Ph.D. 2023, now postdoc at the U. Colorado BioFrontiers Institute)

Michael Levet (Ph.D. 2023, now Assistant Professor at the College of Charleston Department of Computer Science)

Steven Kordonowy (moved to UC Santa Cruz with his advisor)

Gabriel Andrade (Ph.D. 2022, now Applied Scientist at Amazon)

Jessie Finocchiaro (Ph.D. 2022, Assistant Professor at the Boston College Department of Computer Science starting Fall '24, previously NSF postdoc @ Harvard EconCS)

Tyler Schrock (Math, Ph.D. 2019, now Software Engineer at Google)

## Master's Students

## Undergraduate Researchers

### Current

Adithya Bhaskara

Lucy Pipkorn* (post-bacc researcher)

### Former

Mabel Cluff (senior thesis defended 2023)

Nathaniel Collins (senior thesis defended 2023, now Ph.D. student at Colorado State University Dept. of Mathematics)

Emma Goodwill (senior thesis defended 2022)

Robert Gomez (senior thesis defended 2021)

Justin Cai (senior thesis defended 2020)

Tarek Tohme (American U. Beirut, Summer 2019 and 2020, now Ph.D. student at École Normale Supérieure)

Yerim Song (high school, Summer 2020, now undergrad at Carnegie Mellon University)

Michael Klyachman (high school, Summer 2020, now undergrad at The University of Chicago)

Robert Cope (Fall 2019)

Arthur Pellegrino (Summer 2019)

Luke Meszar (senior thesis defended Spring 2019)

Sam Schlesinger (U. Mass., Amherst, Summer 2018)

Jamie Tucker-Foltz (Amherst, Summer 2017, now @ Harvard CS PhD program)

Michael Vienneau (academic year 2017-2018)

Nicole Woytarowicz (senior thesis defended Spring 2017)

Yang Song (academic year 2016-2017)

Brennan McConnell (senior thesis defended Spring 2017)

Elliot Gorokhovsky (high school, during academic year 2016-2017)

## Graduate Courses

Note: 5xxx denotes master's-level, 6xxx denotes PhD-level, 7000 denotes a topics course that may only run once or sporadically, 4xxx denotes (joint with) an upper-level undergraduate course.

### Core Theory

CSCI 5454: Algorithms [recent offering]

CSCI 5444: Theory of Computation [recent offering]

CSCI 5114: Practical Algorithmic Complexity [started Fall 2019, every other year]

CSCI 5654: Linear and Integer Programming [recent offering] [coursera]

CSCI 6114: Computational Complexity Theory [Fall 2023 offering, every other year]

CSCI 6214: Randomized Algorithms [new course! First offering Fall 2021, every other year]

CSCI 6314: Algorithmic Economics [new course! First offering Spring 2022, similar to this topics course]

CSCI 6564: Advanced Algorithms [recent offering]

CSCI 5254: Convex Optimization [recent offering]

APPM 5630: Advanced Convex Optimization [Spring of odd years, recent offering]

CSCI 7000: Cryptography and Cryptanalysis [recent offering (applied)]

### Related Courses

CSCI 7000: Topics in CS: Lattices in Computer Science [Spring '24]

CSCI 7000: Topics in CS: Topics in Combinatorics with a view toward Computational Complexity [Fall '23] (aka "Advanced Counting")

CSCI 7000: Topics in CS: Online Machine Learning, E-Values, and Markets [Fall '23]

APPM 4490/5490 / sometimes CSCI 7000: Theory of Machine Learning [regular site for APPM version; Spring '21 CSCI edition]

CSCI 5314: Algorithms in Molecular Biology [recent offering]

CSCI 5352: Network Analysis and Modeling [recent offering]

MATH 4440/5440: The Mathematics of Coding and Cryptography [recent offering]

MATH 8174: Topics in Algebra: Mathematical Cryptography [Spring '24, course announcement]

CSCI 7000: Topics in CS: Tensors and Computational Complexity [Fall '17]

CSCI 5854: Foundations of Cyber-Physical Systems

## Emeriti and Past Faculty

Alexandra Kolla, at CU 2017-2021, now at UC Santa Cruz

Andrzej Ehrenfeucht, Distinguished Professor Emeritus

Harold "Hal" Gabow, Professor Emeritus