👋 Hi! I’m a Math Fellow (postdoc) in the Math Department at UC Davis hosted by Alex Wein. Previously, I was a postdoctoral researcher at Bocconi University supported by Luca Trevisan and Alon Rosen. I obtained my PhD in 2022 from the University of Chicago advised by Aaron Potechin.

My research is in theoretical computer science. I am interested in mathematically-inspired algorithm design techniques. Recently I’ve been working on semidefinite programming algorithms (specifically the Sum-of-Squares hierarchy), low-degree algorithms, and algorithms from statistical physics. Most of my work has studied average-case (a.k.a random/statistical) inputs.

Some Recorded Talks

(30 minutes) Fourier Analysis of Iterative Algorithms
Les Houches workshop on “Towards a Theory for Typical-Case Algorithmic Hardness”, February 2025
(video) (paper)

(30 minutes) Almost-Orthogonal Bases for Inner Product Polynomials
Innovations in Theoretical Computer Science conference, January 2022
(video) (paper)

Research

Universality of First-order Methods on Random and Deterministic Matrices
Nicola Gorini, Chris Jones, Lucas Pesenti, Dmitriy Kunisky
Manuscript (pdf)

The Grothendieck Constant is Strictly Larger than Davie-Reeds’ Bound
Chris Jones, Giulio Malavolta
Manuscript (pdf)

Higher-order Delsarte Dual LPs: Lifting, Constructions, and Completeness
Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones, Nati Linial, Elyassaf Loyfer
ITCS, 2026 (pdf)

Sparsest Cut and Eigenvalue Multiplicities on Low-Degree Abelian Cayley Graphs
Tommaso d’Orsi, Chris Jones, Jake Ruotolo, Salil Vadhan, Jiyu Zhang
APPROX, 2025 (pdf)
Invited to Theory of Computing special issue for APPROX/RANDOM 2025

Fourier Analysis of Iterative Algorithms
Chris Jones, Lucas Pesenti
ICALP, 2025 (pdf) (video)

Low-degree Security of the Planted Random Subgraph Problem
Andrej Bogdanov, Chris Jones, Alon Rosen, Ilias Zadik
TCC 2024 (pdf)

Key-Recovery Attack on a Public-Key Encryption Related to Planted Clique
Caicai Chen, Chris Jones
Manuscript, 2024 (pdf)

Sum-of-Squares Lower Bounds for Densest k-Subgraph
Chris Jones, Aaron Potechin, Goutham Rajendran, Jeff Xu
STOC 2023 (pdf)

Exact Completeness of LP Hierarchies for Linear Codes
Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones
ITCS 2023 (pdf)

Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses
Chris Jones, Kunal Marwaha, Juspreet Singh Sandhu, Jonathan Shi
ITCS 2023 (pdf) (slides) (video)

A Complete Linear Programming Hierarchy for Linear Codes
Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones
ITCS 2022 (pdf) (video)

Almost-Orthogonal Bases for Inner Product Polynomials
Chris Jones, Aaron Potechin
ITCS 2022 (pdf) (video)

Sum-of-Squares Lower Bounds for Sparse Independent Set
Chris Jones, Aaron Potechin, Goutham Rajendran, Madhur Tulsiani, Jeff Xu
FOCS 2021 (pdf)

Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes
Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris Jones, Aaron Potechin, Goutham Rajendran
FOCS 2020 (pdf) (slides) (video)

Spherical Discrepancy Minimization and Algorithmic Lower Bounds for Covering the Sphere
Chris Jones, Matt McPartlon
SODA 2020 (pdf) (slides)

Notes

Notes on the proof of the second LP bound and association schemes
(pdf)

Other

Symmetrized Fourier Analysis of Convex Relaxations for Combinatorial Optimization Problems
PhD thesis, advised by Aaron Potechin.
(pdf)

Sum-of-Squares for Unique Games
Slides from my PhD candidacy exam presentation
(slides)

A Noisy-Influence Regularity Lemma for Boolean Functions
Undergraduate senior thesis, advised by Ryan O’Donnell.
(pdf)