Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees - Joshua Brakensiek; Aaron Potechin (CoRR, 2013)

Efficient Low-Redundancy Codes for Correcting Multiple Deletions. - Joshua Brakensiek; Venkatesan Guruswami; Samuel Zbarsky (Electron. Colloquium Comput. Complex., 2015)

New hardness results for graph and hypergraph colorings. - Joshua Brakensiek; Venkatesan Guruswami (Electron. Colloquium Comput. Complex., 2016)

Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques. - Joshua Brakensiek (APPROX-RANDOM, 2017)

The Quest for Strong Inapproximability Results with Perfect Completeness. - Joshua Brakensiek; Venkatesan Guruswami (Electron. Colloquium Comput. Complex., 2017)

A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover. - Joshua Brakensiek; Venkatesan Guruswami (Electron. Colloquium Comput. Complex., 2017)

Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy. - Joshua Brakensiek; Venkatesan Guruswami (SODA, 2018)

Combining LPs and Ring Equations via Structured Polymorphisms. - Joshua Brakensiek; Venkatesan Guruswami (Electron. Colloquium Comput. Complex., 2018)

An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. - Joshua Brakensiek; Venkatesan Guruswami (SODA, 2019)

The Resolution of Keller's Conjecture. - Joshua Brakensiek; Marijn Heule; John Mackey (CoRR, 2019)

Bridging between 0/1 and Linear Programming via Random Walks. - Joshua Brakensiek; Venkatesan Guruswami (Electron. Colloquium Comput. Complex., 2019)

CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. - Joshua Brakensiek; Sivakanth Gopi; Venkatesan Guruswami (Electron. Colloquium Comput. Complex., 2019)

Smoothed Complexity of 2-player Nash Equilibria. - Shant Boodaghians; Joshua Brakensiek; Samuel B. Hopkins 001; Aviad Rubinstein (FOCS, 2020)

Coded trace reconstruction in a constant number of traces. - Joshua Brakensiek; Ray Li; Bruce Spang (FOCS, 2020)

Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. - Joshua Brakensiek; Venkatesan Guruswami (SODA, 2020)

Constant-factor approximation of near-linear edit distance in near-linear time. - Joshua Brakensiek; Aviad Rubinstein (STOC, 2020)

A Simple Sublinear Algorithm for Gap Edit Distance. - Joshua Brakensiek; Moses Charikar; Aviad Rubinstein (CoRR, 2020)

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs. - Joshua Brakensiek; Venkatesan Guruswami; Marcin Wrochna; Stanislav Zivný (Electron. Colloquium Comput. Complex., 2020)

The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems. - Joshua Brakensiek; Venkatesan Guruswami; Marcin Wrochna; Stanislav Zivný (SIAM J. Comput., 2020)

The Resolution of Keller's Conjecture - Computation Logs. - Joshua Brakensiek; Marijn Heule; John Mackey; David E. Narváez (Zenodo, 2020)

Lower Bounds for Maximally Recoverable Tensor Code and Higher Order MDS Codes. - Joshua Brakensiek; Sivakanth Gopi; Visu Makam (CoRR, 2021)

Conditional Dichotomy of Boolean Ordered Promise CSPs. - Joshua Brakensiek; Venkatesan Guruswami; Sai Sandeep (Electron. Colloquium Comput. Complex., 2021)

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. - Joshua Brakensiek; Venkatesan Guruswami (SIAM J. Comput., 2021)

The Resolution of Keller's Conjecture. - Joshua Brakensiek; Marijn Heule; John Mackey; David E. Narváez (J. Autom. Reason., 2022)

Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. - Joshua Brakensiek; Sivakanth Gopi; Venkatesan Guruswami (SIAM J. Comput., 2022)

Lower Bounds for Maximally Recoverable Tensor Codes and Higher Order MDS Codes. - Joshua Brakensiek; Sivakanth Gopi; Visu Makam (IEEE Trans. Inf. Theory, 2022)

Separating MAX 2-AND, MAX DI-CUT and MAX CUT. - Joshua Brakensiek; Neng Huang; Aaron Potechin; Uri Zwick (FOCS, 2023)

Generic Reed-Solomon Codes Achieve List-Decoding Capacity. - Joshua Brakensiek; Sivakanth Gopi; Visu Makam (STOC, 2023)

AG codes achieve list decoding capacity over contant-sized fields. - Joshua Brakensiek; Manik Dhar; Sivakanth Gopi; Zihan Zhang 001 (CoRR, 2023)

Tight approximability of MAX 2-SAT and relatives, under UGC. - Joshua Brakensiek; Neng Huang; Uri Zwick (SODA, 2024)

Generalized GM-MDS: Polynomial Codes Are Higher Order MDS. - Joshua Brakensiek; Manik Dhar; Sivakanth Gopi (STOC, 2024)

Rigidity matroids and linear algebraic matroids with applications to matrix completion and tensor codes. - Joshua Brakensiek; Manik Dhar; Jiyang Gao; Sivakanth Gopi; Matt Larson (CoRR, 2024)

Robust Factorizations and Colorings of Tensor Graphs. - Joshua Brakensiek; Sami Davies (SIAM J. Discret. Math., 2024)

Improved Field Size Bounds for Higher Order MDS Codes. - Joshua Brakensiek; Manik Dhar; Sivakanth Gopi (IEEE Trans. Inf. Theory, 2024)

Redundancy Is All You Need. - Joshua Brakensiek; Venkatesan Guruswami (STOC, 2025)

SDPs and Robust Satisfiability of Promise CSP. - Joshua Brakensiek; Venkatesan Guruswami; Sai Sandeep (Electron. Colloquium Comput. Complex., 2025)

On the Mysteries of MAX NAE-SAT. - Joshua Brakensiek; Neng Huang; Aaron Potechin; Uri Zwick (SIAM J. Discret. Math., 2025)

Unique Decoding of Reed-Solomon and Related Codes for Semi-Adversarial Errors. - Joshua Brakensiek; Yeyuan Chen; Manik Dhar; Zihan Zhang 001 (CoRR, 2025)

The Richness of CSP Non-redundancy. - Joshua Brakensiek; Venkatesan Guruswami; Bart M. P. Jansen; Victor Lagerkvist; Magnus Wahlström (CoRR, 2025)

AG Codes Achieve List-Decoding Capacity Over Constant-Sized Fields. - Joshua Brakensiek; Manik Dhar; Sivakanth Gopi; Zihan Zhang 001 (IEEE Trans. Inf. Theory, 2025)