Joshua Brakensiek

Email: josh.brakensiek@berkeley.edu

I am an NSF Mathematical Sciences Postdoctoral Scholar in EECS at the University of California, Berkeley, where I am supervised by Venkatesan Guruswami. My CV is available here.

In 2024, I graduated with a PhD in Computer Science from Stanford University. I was fortunate to be co-advised by Aviad Rubinstein and Moses Charikar. My thesis "Higher Order MDS Codes" is available here.

Before that, I graduated from Carnegie Mellon University with a B.S. and M.S. in Mathematical Sciences as a Knaster-McWilliams Scholar.

I am on the academic job market in 2026-27!

Research

My primary research agenda is to tackle fundamental questions in theoretical computer science and mathematics, particularly questions inspired by modern challenges in computing. Towards this goal, I apply theoretical and computational techniques from many areas including combinatorics, algebra, convex optimization, and formal methods.

Some of my recent works with various collaborators include:

Formulating the theory of higher order MDS codes which unify a number of concepts in coding theory including connecting the recoverability of a real-world distributed storage architecture with fundamental questions in matroid theory. Of recent interest are connections to subspace design codes.

Advancing the theory of (promise) constraint satisfaction problems, which has led to exciting connections between the theory of approximation algorithms and universal algebra.

Understanding the sparsifiability of constraint satisfaction problems. Many such questions can be unified under a common combinatorial framework known as non-redundancy.

Ascertaining the structure of edit distance, including finding improved approximation algorithms for computing edit distance and finding better error-correcting codes which can withstand edit distance errors.

Using SAT-solving/formal methods to resolve a 90-year-old question in mathematics (Keller's conjecture in seven dimensions), as featured in Quanta, Wired, and Popular Mechanics.

Publications and Manuscripts (Google Scholar, DBLP, arXiv)

Brakensiek, J., Chen, Y., Putterman, A., Zhang, Z., and Zheng, K. Algorithmic List Decoding of Reed-Solomon Codes up to Capacity. Manuscript. (arXiv)

Brakensiek, J., Guruswami, V., and Putterman, A. Separating Non-redundancy and Chain Length. Manuscript (arXiv)

Basu, A., Brakensiek, J., Chen, Y., Putterman, A., Reis, V., Zhang, Z. Optimal Sparsifiers for Minkowski Sums and Sums of Seminorms. Manuscript (arXiv)

Brakensiek, J., Guruswami, V., Jansen, B., Lagerkvist, V., and Wahlström, M. Super-linear Lower Bounds for CSP Non-Redundancy via Shrinking Instances. IPEC 2026. Best Paper Award. (arXiv)

Brakensiek, J., Chen, Y., Putterman, A., and Zhang, Z. Bounds and Limitations on Codes Achieving List Recovery Capacity. Manuscript. (arXiv)

Brakensiek, J., Guruswami, V., Jansen, B., Lagerkvist, V., and Wahlström, M. The Richness of CSP Non-redundancy. FOCS 2026. (arXiv)

Basu, A. Brakensiek, J., Kothari, P., and Putterman, A. Quantum Cut Sparsifiers. Manuscript. (arXiv)

Basu, A., Brakensiek, J., and Putterman, A. Many Hamiltonians Are Sparsifiable. Manuscript. (arXiv)

Brakensiek, J., Guruswami, V., and Putterman, A. Classification of Non-redundancy of Boolean Predicates of Arity 4. Principles and Practice of Constraint Programming (CP 2026). (arXiv)

Brakensiek, J., Guruswami, V., and Putterman, A. Multiplicative error set system sparsification: A simpler proof via chain length contraction. ICALP 2026. (arXiv)

Brakensiek, J., Chen, Y., Dhar, M., and Zhang, Z. Unique Decoding of Reed–Solomon and Related Codes for Semi-Adversarial Errors. ICALP 2026. (arXiv)

Brakensiek, J., Dhar, M., and Gopi, S. Improved Constructions and Lower Bounds for Maximally Recoverable Grid Codes. IEEE Transactions on Information Theory, 2026. (arXiv)

Brakensiek, J., Huang, N., Potechin, A., and Zwick, U. Separating MAX 2-AND, MAX DI-CUT and MAX CUT. SIAM Journal on Computing, 2026. Special Issue for FOCS 2023. (arXiv, GitHub)

Brakensiek, J., Dhar, M., Gao, J., Gopi, S., and Larson, M. Rigidity Matroids and Linear Algebraic Matroids with Applications to Matrix Completion and Tensor Codes. Combinatorica, 2026. (arXiv)

Brakensiek, J., Huang, N., Potechin, A., and Zwick, U. Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes. STOC 2026. (arXiv)

Brakensiek, J., Chen, Y., Dhar, M., and Zhang, Z. Combinatorial Bounds for List Recovery via Discrete Brascamp–Lieb Inequalities. STOC 2026. (arXiv)

Brakensiek, J., Chen, Y., Dhar, M., and Zhang, Z. From Random to Explicit via Subspace Designs with Applications to Local Properties and Matroids. STOC 2026. (arXiv)

Brakensiek, J., Ciardo, L., Guruswami, V., Potechin, A., and Zivny, S. New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs. SODA 2026. (arXiv)

Brakensiek, J., Huang, N., Potechin, A., and Zwick, U. MAX BISECTION Might Be Harder to Approximate than MAX CUT. SODA 2026. (arXiv)

Brakensiek, J. and Guruswami, V. Maximal Recoverability: A Nexus of Coding Theory. IEEE BITS (Special Issue on Error-Correcting Codes), 2025. (extended version: arXiv)

Brakensiek, J., Eur, C., Larson, M., and Li, S. Kapranov Degrees. International Mathematics Research Notices (IMRN), 2025. (arXiv)

Brakensiek, J., Guruswami, V., and Sandeep, S. SDPs and Robust Satisfiability of Promise CSP. Discrete Analysis, 2025. (Conference version: STOC 2023.) (arXiv)

Brakensiek, J., Guruswami, V., and Putterman, A. Tight Bounds for Sparsifying Random CSPs. Manuscript. (arXiv)

Brakensiek, J., Dhar, M., and Gopi, S. Generalized GM-MDS: Polynomial Codes are Higher Order MDS. IEEE Transactions on Information Theory, 2025. (Conference version: STOC 2024.) (arXiv)

Brakensiek, J., Dhar, M., Gopi, S. and Zhang, Z. AG Codes Achieve List Decoding Capacity Over Constant-sized Fields. IEEE Transaction on Information Theory, 2025. (Conference version: STOC 2024.) (arXiv)

Brakensiek, J. and Guruswami, V. Redundancy Is All You Need. STOC 2025. (arXiv)

Brakensiek, J., Huang, N., Potechin, A., and Zwick, U. On the Mysteries of MAX NAE-SAT. SIAM Journal on Discrete Mathematics (SIDMA), 2025. (Conference version: SODA 2021.) (arXiv)

Brakensiek, J., Gopi, S., and Makam, V. Generic Reed-Solomon Codes Achieve List-decoding Capacity. SIAM Journal on Computing, 2024. Special Issue for STOC 2023. (arXiv)

Brakensiek, J., Dhar, M., and Gopi, S. Improved Field Size Bounds for Higher Order MDS Codes. IEEE Transactions on Information Theory, 2024. (Conference version: ISIT 2023.) (arXiv, GitHub)

Brakensiek, J. and Davies, S. Robust Factorizations and Colorings of Tensor Graphs. SIAM Journal on Discrete Mathematics (SIDMA), 2024. (arXiv)

Brakensiek, J., Huang, N., and Zwick, U. Tight Approximability of MAX 2-SAT and Relatives, under UGC. SODA 2024. (arXiv, GitHub)

Brakensiek, J. and Guruswami, V. A Family of Dictatorship Tests with Perfect Completeness for 2–to–2 Label Cover. Chicago Journal of Theoretical Computer Science, 2023. (ECCC, CJTCS)

Brakensiek, J., Guruswami, V., and Sandeep, S. Conditional Dichotomy of Boolean Ordered Promise CSPs. TheoretiCS, 2023. (Conference version: ICALP 2021.) (arXiv, TheoretiCS)

Brakensiek, J., Gopi, S., and Makam, V. Lower Bounds for Maximally Recoverable Tensor Codes and Higher Order MDS Codes. IEEE Transactions on Information Theory, 2022. (arXiv)

Brakensiek, J., Heule, M., Mackey, J., and Narváez, D. The Resolution of Keller's Conjecture. Special Issue, Journal of Automated Reasoning, 2022. (Conference version: IJCAR 2020. Best Paper Award.) (arXiv, website)

Brakensiek, J., Gopi, S., and Guruswami, V. Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. SIAM Journal on Computing, 2022. (Conference version: STOC 2019.) (arXiv, ECCC)

Brakensiek, J. and Guruswami, V. The Quest for Strong Inapproximability Results with Perfect Completeness. ACM Transactions on Algorithms, 2021. (Conference version: APPROX 2017.) (ECCC)

Brakensiek, J. and Guruswami, V. Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. SIAM Journal on Computing, 2021. (Conference version: SODA 2018.) (arXiv)

Brakensiek, J., Charikar, M., and Rubinstein, A. A Simple Sublinear Algorithm for Gap Edit Distance. Manuscript. (arXiv)

Brakensiek, J., Guruswami, V., Wrochna, M., and Zivny, S. The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs. SIAM Journal on Computing, 2020. (Conference version: Brakensiek, J. and Guruswami, V. Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. SODA 2020.) (arXiv)

Boodaghians, S., Brakensiek, J., Hopkins, S., and Rubinstein, A. Smoothed Complexity of 2-player Nash Equilibria. FOCS 2020. (arXiv)

Brakensiek, J., Li, R., and Spang, B. Coded Trace Reconstruction in a Constant Number of Traces. FOCS 2020. (arXiv)

Brakensiek, J. and Rubinstein, A. Constant-factor Approximation of Near-linear Edit Distance in Near-linear Time. STOC 2020. (arXiv)

Brakensiek, J. and Guruswami, V. Bridging between 0/1 and Linear Programming via Random Walks. STOC 2019. (arXiv)

Brakensiek, J. and Guruswami, V. An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. SODA 2019. (ECCC)

Brakensiek, J., Guruswami, V., and Zbarsky, S. Efficient Low-Redundancy Codes for Correcting Multiple Deletions. IEEE Transactions on Information Theory, 2017. (Conference version: SODA 2016.) (arXiv)

Brakensiek, J. Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques. RANDOM 2017. (arXiv)

Brakensiek, J. and Guruswami, V. New Hardness Results for Graph and Hypergraph Colorings. CCC 2016. (ECCC)

Brakensiek, J and Ragozzine, D. Efficient Geometric Probabilities of Multi-Transiting Exoplanetary Systems from CORBITS. The Astrophysical Journal, 2016, 821, 47. (arXiv, code)

Brakensiek, J. and Potechin, A. Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees. Manuscript. (arXiv)

Professional Service

PC Member: MFCS 2026
I write 20+ referee reports a year for leading journals and conferences in computer science and mathematics, including STOC/FOCS/SODA, the Journal of the ACM, the IEEE Transactions on Information Theory, and the SIAM Journal on Computing.
Former webmaster of theory.stanford.edu (2019-2023)
Undergraduate representative in the MCS College Council (2017-18)
Reviewer for Mathematical Reviews/Mathscinet

Teaching

In Spring 2021, I was a Course Assistant for Stanford's CS 269I: Incentives in Computer Science.
In Spring 2019, I was Course Assitant for Stanford's CS 354: Unfulfilled Algorithmic Fantasies.
In Fall 2017, I was a Teaching Assistant for the CMU course 15-458/858B: Discrete Differential Geometry taught by Keenan Crane.
I was a grader at the 2017 Math Olympiad Program directed by Po-Shen Loh. While there, I led a problem session on coding theory.
From 2014-17, I have helped grade the Team Selection Tests which decide the USA team for the International Mathematical Olympiad.

Selected Awards

2025 NSF Mathematical Sciences Postdoctoral Research Fellowship
2021 Microsoft Research PhD Fellowship
2020 IJCAR Best Paper Award (co-winner)
2018 NSF Graduate Research Fellowship
2018 Computing Research Association Outstanding Undergraduate Research Award
2017 Phi Beta Kappa
2016 Putnam Fellow (top 5 out of over 4000 students) and first place team
2016 Goldwater Scholar
2014 Akamai Foundation Scholarship
2013 Davidson Fellow

In high school, I participated in various mathematics and computer science competitions.

2-time Gold medalist: 2013/2014 International Olympiad in Informatics
Silver medalist: 2014 International Mathematical Olympiad
Samuel L. Greitzer/Murray S. Klamkin Award for Mathematical Excellence: Sole perfect scorer on the 2014 USA Mathematical Olympiad

Other

My PhD quals have been published as a pair of blog posts. (Part 1, Part 2)

At CMU, I was a member of Keenan Crane's Geometry Collective.

I am a class of 2012 alumnus of the Research Science Institute.

The following photograph I took of Chandler-Gilbert Community College in Arizona appears in the Mathematical Association of America's 100th anniversary calendar: