Joshua Brakensiek
I am a thirdyear PhD student in Computer Science at Stanford University. I am fortunate to be coadvised 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 KnasterMcWilliams Scholar. While there, my advisor in the Honors Program was the truly excellent Venkatesan Guruswami.
Research
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 NAESAT. SODA 2021. (arXiv)
 Boodaghians, S., Brakensiek, J., Hopkins, S., and Rubinstein, A. Smoothed Complexity of 2player 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. Constantfactor Approximation of Nearlinear Edit Distance in Nearlinear 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 LowRedundancy 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
MultiTransiting 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
Professional Service
 Webmaster of theory.stanford.edu (2019present)
 Undergraduate representative in the MCS College Council (201718)
 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
Selected Awards
In high school, I participated in various mathematics and computer science competitions.
 2time 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
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 ChandlerGilbert Community College in Arizona appears in the Mathematical Association of America's 100th anniversary calendar: