Jonah Brown-Cohen

Logo

View My GitHub Profile

I am an assistant professor in the division of Data Science and AI at Chalmers University of Technology. Prior to coming to Chalmers I was 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 foundations of machine learning.

Papers

[1] 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.

[2] 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.

[3] 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.

[4] 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.

[5] 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.

[6] Combinatorial Optimization Algorithms via Polymorphisms [arxiv]

Jonah Brown-Cohen and Prasad Raghavendra Manuscript