Joshua Brakensiek

88 papers A* 20A 1B 1Journal 63Unranked 3

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Classification of Non-redundancy of Boolean Predicates of Arity 4. CoRR Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
2026	J	`jnl`	Improved Approximation Algorithms for Multiway Cut by Large Mixtures of New and Old Rounding Schemes. CoRR Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2026	A*	`conf`	MAX BISECTION might be harder to approximate than MAX CUT. SODA Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2026	J	`jnl`	Maximal Recoverability: A Nexus of Coding Theory. CoRR Joshua Brakensiek, Venkatesan Guruswami
2026	A*	`conf`	New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs. SODA Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav Zivný
2026	J	`jnl`	New Algorithms and Hardness Results for Robust Satisfiability of (Promise) CSPs. CoRR Joshua Brakensiek, Lorenzo Ciardo, Venkatesan Guruswami, Aaron Potechin, Stanislav Zivný
2026	J	`jnl`	Rigidity Matroids and Linear Algebraic Matroids with Applications to Matrix Completion and Tensor Codes. Comb. Joshua Brakensiek, Manik Dhar, Jiyang Gao, Sivakanth Gopi, Matt Larson
2025	J	`jnl`	AG Codes Achieve List-Decoding Capacity Over Constant-Sized Fields. IEEE Trans. Inf. Theory Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, Zihan Zhang
2025	J	`jnl`	Combinatorial Bounds for List Recovery via Discrete Brascamp-Lieb Inequalities. CoRR Joshua Brakensiek, Yeyuan Chen, Manik Dhar, Zihan Zhang
2025	J	`jnl`	From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids. CoRR Joshua Brakensiek, Yeyuan Chen, Manik Dhar, Zihan Zhang
2025	J	`jnl`	From Random to Explicit via Subspace Designs With Applications to Local Properties and Matroids. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Yeyuan Chen, Manik Dhar, Zihan Zhang
2025	J	`jnl`	Generalized GM-MDS: Polynomial Codes Are Higher Order MDS. IEEE Trans. Inf. Theory Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
2025	J	`jnl`	Improved Constructions and Lower Bounds for Maximally Recoverable Grid Codes. CoRR Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
2025	J	`jnl`	MAX BISECTION might be harder to approximate than MAX CUT. CoRR Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2025	J	`jnl`	On the Mysteries of MAX NAE-SAT. SIAM J. Discret. Math. Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2025	A*	`conf`	Redundancy Is All You Need. STOC Joshua Brakensiek, Venkatesan Guruswami
2025	J	`jnl`	SDPs and Robust Satisfiability of Promise CSP. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2025	J	`jnl`	The Richness of CSP Non-redundancy. CoRR Joshua Brakensiek, Venkatesan Guruswami, Bart M. P. Jansen, Victor Lagerkvist, Magnus Wahlström
2025	J	`jnl`	Tight Bounds for Sparsifying Random CSPs. CoRR Joshua Brakensiek, Venkatesan Guruswami, Aaron Putterman
2025	J	`jnl`	Unique Decoding of Reed-Solomon and Related Codes for Semi-Adversarial Errors. CoRR Joshua Brakensiek, Yeyuan Chen, Manik Dhar, Zihan Zhang
2024	A*	`conf`	AG Codes Achieve List Decoding Capacity over Constant-Sized Fields. STOC Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, Zihan Zhang
2024	A*	`conf`	Generalized GM-MDS: Polynomial Codes Are Higher Order MDS. STOC Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
2024	J	`jnl`	Improved Field Size Bounds for Higher Order MDS Codes. IEEE Trans. Inf. Theory Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
2024	J	`jnl`	Redundancy Is All You Need. CoRR Joshua Brakensiek, Venkatesan Guruswami
2024	J	`jnl`	Rigidity matroids and linear algebraic matroids with applications to matrix completion and tensor codes. CoRR Joshua Brakensiek, Manik Dhar, Jiyang Gao, Sivakanth Gopi, Matt Larson
2024	J	`jnl`	Robust Factorizations and Colorings of Tensor Graphs. SIAM J. Discret. Math. Joshua Brakensiek, Sami Davies
2024	A*	`conf`	Tight approximability of MAX 2-SAT and relatives, under UGC. SODA Joshua Brakensiek, Neng Huang, Uri Zwick
2023	J	`jnl`	AG codes achieve list decoding capacity over contant-sized fields. CoRR Joshua Brakensiek, Manik Dhar, Sivakanth Gopi, Zihan Zhang
2023	J	`jnl`	Conditional Dichotomy of Boolean Ordered Promise CSPs. TheoretiCS Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2023	J	`jnl`	Generalized GM-MDS: Polynomial Codes are Higher Order MDS. CoRR Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
2023	A*	`conf`	Generic Reed-Solomon Codes Achieve List-Decoding Capacity. STOC Joshua Brakensiek, Sivakanth Gopi, Visu Makam
2023	B	`conf`	Improved Field Size Bounds for Higher Order MDS Codes. ISIT Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
2023	A*	`conf`	SDPs and Robust Satisfiability of Promise CSP. STOC Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2023	A*	`conf`	Separating MAX 2-AND, MAX DI-CUT and MAX CUT. FOCS Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2023	J	`jnl`	Tight approximability of MAX 2-SAT and relatives, under UGC. CoRR Joshua Brakensiek, Neng Huang, Uri Zwick
2022	J	`jnl`	Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. SIAM J. Comput. Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
2022	J	`jnl`	Generic Reed-Solomon codes achieve list-decoding capacity. CoRR Joshua Brakensiek, Sivakanth Gopi, Visu Makam
2022	J	`jnl`	Improved Field Size Bounds for Higher Order MDS Codes. CoRR Joshua Brakensiek, Manik Dhar, Sivakanth Gopi
2022	J	`jnl`	Lower Bounds for Maximally Recoverable Tensor Codes and Higher Order MDS Codes. IEEE Trans. Inf. Theory Joshua Brakensiek, Sivakanth Gopi, Visu Makam
2022	J	`jnl`	Robust Factorizations and Colorings of Tensor Graphs. CoRR Joshua Brakensiek, Sami Davies
2022	J	`jnl`	SDPs and Robust Satisfiability of Promise CSP. CoRR Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2022	J	`jnl`	Separating MAX 2-AND, MAX DI-CUT and MAX CUT. CoRR Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2022	J	`jnl`	The Resolution of Keller's Conjecture. J. Autom. Reason. Joshua Brakensiek, Marijn Heule, John Mackey, David E. Narváez
2021	A*	`conf`	Conditional Dichotomy of Boolean Ordered Promise CSPs. ICALP Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2021	J	`jnl`	Conditional Dichotomy of Boolean Ordered Promise CSPs. CoRR Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2021	J	`jnl`	Conditional Dichotomy of Boolean Ordered Promise CSPs. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami, Sai Sandeep
2021	J	`jnl`	Lower Bounds for Maximally Recoverable Tensor Code and Higher Order MDS Codes. CoRR Joshua Brakensiek, Sivakanth Gopi, Visu Makam
2021	A*	`conf`	On the Mysteries of MAX NAE-SAT. SODA Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2021	J	`jnl`	Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. SIAM J. Comput. Joshua Brakensiek, Venkatesan Guruswami
2021	J	`jnl`	The Quest for Strong Inapproximability Results with Perfect Completeness. ACM Trans. Algorithms Joshua Brakensiek, Venkatesan Guruswami
2020	J	`jnl`	A Simple Sublinear Algorithm for Gap Edit Distance. CoRR Joshua Brakensiek, Moses Charikar, Aviad Rubinstein
2020	A*	`conf`	Coded trace reconstruction in a constant number of traces. FOCS Joshua Brakensiek, Ray Li, Bruce Spang
2020	A*	`conf`	Constant-factor approximation of near-linear edit distance in near-linear time. STOC Joshua Brakensiek, Aviad Rubinstein
2020	J	`jnl`	On the Mysteries of MAX NAE-SAT. CoRR Joshua Brakensiek, Neng Huang, Aaron Potechin, Uri Zwick
2020	A*	`conf`	Smoothed Complexity of 2-player Nash Equilibria. FOCS Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein
2020	J	`jnl`	Smoothed Complexity of 2-player Nash Equilibria. CoRR Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins, Aviad Rubinstein
2020	A*	`conf`	Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. SODA Joshua Brakensiek, Venkatesan Guruswami
2020	J	`jnl`	The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný
2020	J	`jnl`	The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems. SIAM J. Comput. Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna, Stanislav Zivný
2020	—	`conf`	The Resolution of Keller's Conjecture. IJCAR (1) Joshua Brakensiek, Marijn Heule, John Mackey, David E. Narváez
2019	A*	`conf`	An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. SODA Joshua Brakensiek, Venkatesan Guruswami
2019	J	`jnl`	Bridging between 0/1 and Linear Programming via Random Walks. CoRR Joshua Brakensiek, Venkatesan Guruswami
2019	J	`jnl`	Bridging between 0/1 and Linear Programming via Random Walks. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami
2019	A*	`conf`	Bridging between 0/1 and linear programming via random walks. STOC Joshua Brakensiek, Venkatesan Guruswami
2019	J	`jnl`	CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. CoRR Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
2019	J	`jnl`	CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
2019	A*	`conf`	CSPs with global modular constraints: algorithms and hardness via polynomial representations. STOC Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
2019	J	`jnl`	Coded trace reconstruction in a constant number of traces. CoRR Joshua Brakensiek, Ray Li, Bruce Spang
2019	J	`jnl`	Constant-factor approximation of near-linear edit distance in near-linear time. CoRR Joshua Brakensiek, Aviad Rubinstein
2019	J	`jnl`	Symmetric Polymorphisms and Efficient Decidability of Promise CSPs. CoRR Joshua Brakensiek, Venkatesan Guruswami
2019	J	`jnl`	The Resolution of Keller's Conjecture. CoRR Joshua Brakensiek, Marijn Heule, John Mackey
2018	J	`jnl`	An Algorithmic Blend of LPs and Ring Equations for Promise CSPs. CoRR Joshua Brakensiek, Venkatesan Guruswami
2018	J	`jnl`	Combining LPs and Ring Equations via Structured Polymorphisms. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami
2018	J	`jnl`	Efficient Low-Redundancy Codes for Correcting Multiple Deletions. IEEE Trans. Inf. Theory Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
2018	A*	`conf`	Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy. SODA Joshua Brakensiek, Venkatesan Guruswami
2017	J	`jnl`	A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami
2017	J	`jnl`	Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. CoRR Joshua Brakensiek, Venkatesan Guruswami
2017	—	`conf`	The Quest for Strong Inapproximability Results with Perfect Completeness. APPROX-RANDOM Joshua Brakensiek, Venkatesan Guruswami
2017	J	`jnl`	The Quest for Strong Inapproximability Results with Perfect Completeness. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami
2017	—	`conf`	Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques. APPROX-RANDOM Joshua Brakensiek
2017	J	`jnl`	Vertex isoperimetry and independent set stability for tensor powers of cliques. CoRR Joshua Brakensiek
2016	A*	`conf`	Efficient Low-Redundancy Codes for Correcting Multiple Deletions. SODA Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
2016	A	`conf`	New Hardness Results for Graph and Hypergraph Colorings. CCC Joshua Brakensiek, Venkatesan Guruswami
2016	J	`jnl`	New hardness results for graph and hypergraph colorings. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami
2016	J	`jnl`	Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami
2015	J	`jnl`	Efficient Low-Redundancy Codes for Correcting Multiple Deletions. CoRR Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
2015	J	`jnl`	Efficient Low-Redundancy Codes for Correcting Multiple Deletions. Electron. Colloquium Comput. Complex. Joshua Brakensiek, Venkatesan Guruswami, Samuel Zbarsky
2013	J	`jnl`	Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees CoRR Joshua Brakensiek, Aaron Potechin