I am a third-year PhD student in Computer Science at Stanford University. I am 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 with a minor in Science, Technology and Society as a Knaster-McWilliams Scholar. While there, my advisor in the Honors Program was the truly excellent Venkatesan Guruswami.
My research interests lie in theoretical computer science, particularly in the application of algebraic and geometric techniques.
My most recent work has been in approximation algorithms, particularly for edit distance and constraint satisfaction problems.
Publications and Manuscripts
Brakensiek, J., Guruswami, V., and Sandeep, S. Conditional Dichotomy of Boolean Ordered Promise CSPs. Manuscript. (arXiv)
Brakensiek, J., Huang, N., Potechin, A., and Zwick, U. On the Mysteries of MAX NAE-SAT. SODA 2021. (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., Heule, M., Mackey, J., and Narváez, D. The Resolution of Keller's Conjecture. IJCAR 2020. Best Paper Award. (arXiv, website) See the article on the project in Quanta Magazine.
- 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. Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. SODA 2020. (arXiv)
- Brakensiek, J. and Guruswami, V. Bridging between 0/1 and Linear Programming via Random Walks. STOC 2019. (arXiv)
- Brakensiek, J., Gopi, S., and Guruswami, V. CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. STOC 2019. (ECCC)
- Brakensiek, J. and Guruswami, V. An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. SODA 2019. (ECCC)
- Brakensiek, J. and Guruswami, V. Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. SODA 2018. (arXiv)
- Brakensiek, J. and Guruswami, V. A Family of Dictatorship Tests with Perfect Completeness for 2–to–2 Label Cover. Manuscript. (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. and Guruswami, V. The Quest for Strong Inapproximability Results with Perfect Completeness. APPROX 2017. (ECCC)
- 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)
- Webmaster of theory.stanford.edu (2019-present)
- Undergraduate representative in the MCS College Council (2017-18)
- Subreviewer for the conferences ISIT 2019; ICALP 2019; FOCS 2019; ESA 2019; FSTTCS 2019; SODA 2020
- Reviewer for the journals: Journal of ACM; IEEE Transactions on Information Theory; Theory of Computing Systems
- Reviewer for Mathematical Reviews/Mathscinet
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
I was also 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: