Joshua Brakensiek

Publication Activity (10 Years)

Years Active: 2013-2024
Publications (10 Years): 63

Top Topics

Linear Programming

Nash Equilibria

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Joshua Brakensiek, Manik Dhar, Jiyang Gao, Sivakanth Gopi, Matt Larson
Rigidity matroids and linear algebraic matroids with applications to matrix completion and tensor codes. CoRR (2024)
Joshua Brakensiek, Sami Davies
Robust Factorizations and Colorings of Tensor Graphs. SIAM J. Discret. Math. 38 (1) (2024)
Joshua Brakensiek, Neng Huang, Uri Zwick
Tight approximability of MAX 2-SAT and relatives, under UGC. SODA (2024)
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, Zihan Zhang
AG Codes Achieve List Decoding Capacity over Constant-Sized Fields. STOC (2024)
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
Generalized GM-MDS: Polynomial Codes Are Higher Order MDS. STOC (2024)
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
Separating MAX 2-AND, MAX DI-CUT and MAX CUT. FOCS (2023)
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
Generalized GM-MDS: Polynomial Codes are Higher Order MDS. CoRR (2023)
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
SDPs and Robust Satisfiability of Promise CSP. STOC (2023)
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, Zihan Zhang
AG codes achieve list decoding capacity over contant-sized fields. CoRR (2023)
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
Improved Field Size Bounds for Higher Order MDS Codes. ISIT (2023)
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
Conditional Dichotomy of Boolean Ordered Promise CSPs. TheoretiCS 2 (2023)
Joshua Brakensiek, Sivakanth Gopi, Visu Makam
Generic Reed-Solomon Codes Achieve List-Decoding Capacity. STOC (2023)
Joshua Brakensiek, Neng Huang, Uri Zwick
Tight approximability of MAX 2-SAT and relatives, under UGC. CoRR (2023)
Joshua Brakensiek, Marijn Heule, John Mackey, David E. Narváez
The Resolution of Keller's Conjecture. J. Autom. Reason. 66 (3) (2022)
Joshua Brakensiek, Sami Davies
Robust Factorizations and Colorings of Tensor Graphs. CoRR (2022)
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
Separating MAX 2-AND, MAX DI-CUT and MAX CUT. CoRR (2022)
Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. SIAM J. Comput. 51 (3) (2022)
Joshua Brakensiek, Sivakanth Gopi, Visu Makam
Generic Reed-Solomon codes achieve list-decoding capacity. CoRR (2022)
Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
Improved Field Size Bounds for Higher Order MDS Codes. CoRR (2022)
Joshua Brakensiek, Sivakanth Gopi, Visu Makam
Lower Bounds for Maximally Recoverable Tensor Codes and Higher Order MDS Codes. IEEE Trans. Inf. Theory 68 (11) (2022)
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
SDPs and Robust Satisfiability of Promise CSP. CoRR (2022)
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
On the Mysteries of MAX NAE-SAT. SODA (2021)
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
Conditional Dichotomy of Boolean Ordered Promise CSPs. CoRR (2021)
Joshua Brakensiek, Venkatesan Guruswami
The Quest for Strong Inapproximability Results with Perfect Completeness. ACM Trans. Algorithms 17 (3) (2021)
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
Conditional Dichotomy of Boolean Ordered Promise CSPs. Electron. Colloquium Comput. Complex. 28 (2021)
Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
Conditional Dichotomy of Boolean Ordered Promise CSPs. ICALP (2021)
Joshua Brakensiek, Sivakanth Gopi, Visu Makam
Lower Bounds for Maximally Recoverable Tensor Code and Higher Order MDS Codes. CoRR (2021)
Joshua Brakensiek, Venkatesan Guruswami
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. SIAM J. Comput. 50 (6) (2021)
Joshua Brakensiek, Moses Charikar, Aviad Rubinstein
A Simple Sublinear Algorithm for Gap Edit Distance. CoRR (2020)
Joshua Brakensiek, Ray Li, Bruce Spang
Coded trace reconstruction in a constant number of traces. FOCS (2020)
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein
Smoothed Complexity of 2-player Nash Equilibria. FOCS (2020)
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein
Smoothed Complexity of 2-player Nash Equilibria. CoRR (2020)
Joshua Brakensiek, Venkatesan Guruswami
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. SODA (2020)
Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný
The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs. Electron. Colloquium Comput. Complex. 27 (2020)
Joshua Brakensiek, Marijn Heule, John Mackey, David E. Narváez
The Resolution of Keller's Conjecture. IJCAR (1) (2020)
Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
On the Mysteries of MAX NAE-SAT. CoRR (2020)
Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný
The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems. SIAM J. Comput. 49 (6) (2020)
Joshua Brakensiek, Aviad Rubinstein
Constant-factor approximation of near-linear edit distance in near-linear time. STOC (2020)
Joshua Brakensiek, Venkatesan Guruswami
Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. CoRR (2019)
Joshua Brakensiek, Ray Li, Bruce Spang
Coded trace reconstruction in a constant number of traces. CoRR (2019)
Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. CoRR (2019)
Joshua Brakensiek, Venkatesan Guruswami
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. SODA (2019)
Joshua Brakensiek, Venkatesan Guruswami
Bridging between 0/1 and linear programming via random walks. STOC (2019)
Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. Electron. Colloquium Comput. Complex. 26 (2019)
Joshua Brakensiek, Marijn Heule, John Mackey
The Resolution of Keller's Conjecture. CoRR (2019)
Joshua Brakensiek, Venkatesan Guruswami
Bridging between 0/1 and Linear Programming via Random Walks. CoRR (2019)
Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
CSPs with global modular constraints: algorithms and hardness via polynomial representations. STOC (2019)
Joshua Brakensiek, Aviad Rubinstein
Constant-factor approximation of near-linear edit distance in near-linear time. CoRR (2019)
Joshua Brakensiek, Venkatesan Guruswami
Bridging between 0/1 and Linear Programming via Random Walks. Electron. Colloquium Comput. Complex. 26 (2019)
Joshua Brakensiek, Venkatesan Guruswami
Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy. SODA (2018)
Joshua Brakensiek, Venkatesan Guruswami
Combining LPs and Ring Equations via Structured Polymorphisms. Electron. Colloquium Comput. Complex. 25 (2018)
Joshua Brakensiek, Venkatesan Guruswami
An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. CoRR (2018)
Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
Efficient Low-Redundancy Codes for Correcting Multiple Deletions. IEEE Trans. Inf. Theory 64 (5) (2018)
Joshua Brakensiek, Venkatesan Guruswami
A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover. Electron. Colloquium Comput. Complex. 24 (2017)
Joshua Brakensiek
Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques. APPROX-RANDOM (2017)
Joshua Brakensiek
Vertex isoperimetry and independent set stability for tensor powers of cliques. CoRR (2017)
Joshua Brakensiek, Venkatesan Guruswami
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. CoRR (2017)
Joshua Brakensiek, Venkatesan Guruswami
The Quest for Strong Inapproximability Results with Perfect Completeness. APPROX-RANDOM (2017)
Joshua Brakensiek, Venkatesan Guruswami
The Quest for Strong Inapproximability Results with Perfect Completeness. Electron. Colloquium Comput. Complex. 24 (2017)
Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
Efficient Low-Redundancy Codes for Correcting Multiple Deletions. SODA (2016)
Joshua Brakensiek, Venkatesan Guruswami
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. Electron. Colloquium Comput. Complex. 23 (2016)
Joshua Brakensiek, Venkatesan Guruswami
New Hardness Results for Graph and Hypergraph Colorings. Computational Complexity Conference (2016)
Joshua Brakensiek, Venkatesan Guruswami
New hardness results for graph and hypergraph colorings. Electron. Colloquium Comput. Complex. 23 (2016)
Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
Efficient Low-Redundancy Codes for Correcting Multiple Deletions. Electron. Colloquium Comput. Complex. 22 (2015)
Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
Efficient Low-Redundancy Codes for Correcting Multiple Deletions. CoRR (2015)
Joshua Brakensiek, Aaron Potechin
Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees CoRR (2013)