he/him

ðŸ‘‹ Hi! Iâ€™m a postdoctoral researcher in theoretical computer science at Bocconi University supported by Luca Trevisan. 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) and algorithms from statistical physics. Most of my work has studied average-case (a.k.a random/statistical) inputs. You can read more in my PhD thesis.

**Update:** my new work with Lucas Pesenti on Diagram Analysis of Iterative Algorithms is out, in which we connect ideas between Sum-of-Squares algorithms and statistical physics. Check it out!

**Diagram 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)

**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)