👋 Hi! I’m a postdoctoral researcher in theoretical computer science at Bocconi University supported by Luca Trevisan and Alon Rosen. In spring 2022, I obtained my PhD from the University of Chicago advised by Aaron Potechin.

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.

Update: my new work with Lucas Pesenti on Fourier Analysis of Iterative Algorithms is out, in which we connect ideas between statistical physics and low-degree polynomial analysis. Check it out!

Research

Higher-order Delsarte Dual LPs: Lifting, Constructions, and Completeness
Leonardo Nagami Coregliano, Fernando Granha Jeronimo, Chris Jones, Nati Linial, Elyassaf Loyfer
Manuscript, 2024

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

Fourier Analysis of Iterative Algorithms
Chris Jones, Lucas Pesenti
Manuscript, 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)

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)