Joshua Brakensiek

I recently graduated with a PhD in Computer Science from Stanford University. I was fortunate to be co-advised by Aviad Rubinstein and Moses Charikar. My CV is available here.

I graduated from Carnegie Mellon University with a B.S. and M.S. in Mathematical Sciences as a Knaster-McWilliams Scholar. My advisor in the Honors Program was Venkatesan Guruswami.

Research

My primary research agenda is to tackle fundamental questions in theoretical computer science and adjacent areas, 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 list-decoding.

Understanding 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.

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

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

Brakensiek, J., Dhar, M., Gopi, S, and Zhang, Z.. AG Codes Achieve List Decoding Capacity Over Constant-sized Fields. STOC 2024. (arXiv)

Brakensiek, J., Dhar, M., and Gopi, S. Generalized GM-MDS: Polynomial Codes are Higher Order MDS. STOC 2024. (arXiv)

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., Huang, N., Potechin, A., and Zwick, U. Separating MAX 2-AND, MAX DI-CUT and MAX CUT. FOCS 2023. (arXiv, GitHub) Invited to SICOMP special issue.

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., Dhar, M., and Gopi, S. Improved Field Size Bounds for Higher Order MDS Codes. ISIT 2023. (arXiv, GitHub)

Brakensiek, J., Gopi, S., and Makam, V. Generic Reed-Solomon Codes Achieve List-decoding Capacity. STOC 2023. (arXiv) Invited to SICOMP special issue.

Brakensiek, J., Guruswami, V., and Sandeep, S. SDPs and Robust Satisfiability of Promise CSP. STOC 2023. (arXiv)

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., Huang, N., Potechin, A., and Zwick, U. On the Mysteries of MAX NAE-SAT. SODA 2021. (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)

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.

Professional Service

Subreviewer/reviewer for many journals and conferences including STOC/FOCS/SODA, the Journal of the ACM, the IEEE Transactions on Information Theory, and the SIAM Journal on Computing (see CV for full list).
Webmaster of theory.stanford.edu (2019-present)
Undergraduate representative in the MCS College Council (2017-18)
Reviewer for Mathematical Reviews/Mathscinet

Selected Awards

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: