I am research scientist at Google DeepMind. Previously I was an assistant professor at Chalmers University of Technology, a postdoc at KTH Royal Institute of Technology with Johan Håstad, and before that a PhD student at University of California, Berkeley, advised by Prasad Raghavendra.

I am interested in topics in algorithms and complexity theory including constraint satisfaction problems, linear and semidefinite programming hierarchies, extended formulation lower bounds, hardness of approximation, the complexity of statistical inference, and the of application complexity theoretic approaches to AI alignment.

Papers

Scalable AI Safety via Doubly Efficient Debate [arxiv]
Jonah Brown-Cohen, Geoffrey Irving, and Georgios Piliouras.

Skill-Mix: a Flexible and Expandable Family of Evaluations for AI models [arxiv]
Dingli Yu, Simran Kaur, Arushi Gupta, Jonah Brown-Cohen, Anirudh Goyal, and Sanjeev Arora.

Faster Algorithms and Constant Lower Bounds for the Worst-Case Expected Error [arxiv]
Jonah Brown-Cohen.
In the 35th Conference on Neural Information Processing Systems, NeurIPS 2021.

Optimal Inapproximability with Universal Factor Graphs [ECCC]
Per Austrin, Jonah Brown-Cohen and Johan Håstad.
In the 32nd ACM-SIAM Symposium on Discrete Algorithms, SODA 2021.

Extended Formulation Lower Bounds for Refuting Random CSPs [arxiv]
Jonah Brown-Cohen and Prasad Raghavendra.
In the 31st ACM-SIAM Symposium on Discrete Algorithms, SODA 2020.

Formal Barriers to Longest-Chain Proof-of-Stake Protocols [arxiv]
Jonah Brown-Cohen, Arvind Narayanan, Christos Alexandros Psomas and S. Matthew Weinberg.
In the 20th ACM Conference on Economics and Computation, EC 2019.

Correlation Decay and Tractability of CSPs [pdf]
Jonah Brown-Cohen and Prasad Raghavendra.
In the 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016.

The Matching Problem has no Small Symmetric SDP [arxiv]
Gabor Braun, Jonah Brown Cohen, Arefin Huq, Sebastian Pokutta, Prasad Raghavendra, Aurko Roy, Benjamin Weitz and Daniel Zink.
In the 27th ACM-SIAM Symposium on Discrete Algorithms, SODA 2016.

Combinatorial Optimization Algorithms via Polymorphisms [arxiv]
Jonah Brown-Cohen and Prasad Raghavendra.
Manuscript.