Joshua Brakensiek

Orcid: 0000-0003-4149-7298

According to our database1, Joshua Brakensiek authored at least 34 papers between 2013 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
Robust Factorizations and Colorings of Tensor Graphs.
SIAM J. Discret. Math., March, 2024

2023
Tight approximability of MAX 2-SAT and relatives, under UGC.
CoRR, 2023

AG codes achieve list decoding capacity over contant-sized fields.
CoRR, 2023

Generalized GM-MDS: Polynomial Codes are Higher Order MDS.
CoRR, 2023

SDPs and Robust Satisfiability of Promise CSP.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Generic Reed-Solomon Codes Achieve List-Decoding Capacity.
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Improved Field Size Bounds for Higher Order MDS Codes.
Proceedings of the IEEE International Symposium on Information Theory, 2023

Separating MAX 2-AND, MAX DI-CUT and MAX CUT.
Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022
Lower Bounds for Maximally Recoverable Tensor Codes and Higher Order MDS Codes.
IEEE Trans. Inf. Theory, 2022

Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations.
SIAM J. Comput., 2022

The Resolution of Keller's Conjecture.
J. Autom. Reason., 2022

2021
The Quest for Strong Inapproximability Results with Perfect Completeness.
ACM Trans. Algorithms, 2021

Conditional Dichotomy of Boolean Ordered Promise CSPs.
Electron. Colloquium Comput. Complex., 2021

Lower Bounds for Maximally Recoverable Tensor Code and Higher Order MDS Codes.
CoRR, 2021

On the Mysteries of MAX NAE-SAT.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020
The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems.
SIAM J. Comput., 2020

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs.
Electron. Colloquium Comput. Complex., 2020

A Simple Sublinear Algorithm for Gap Edit Distance.
CoRR, 2020

Constant-factor approximation of near-linear edit distance in near-linear time.
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

Symmetric Polymorphisms and Efficient Decidability of Promise CSPs.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Coded trace reconstruction in a constant number of traces.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

Smoothed Complexity of 2-player Nash Equilibria.
Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

2019
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations.
Electron. Colloquium Comput. Complex., 2019

Bridging between 0/1 and Linear Programming via Random Walks.
Electron. Colloquium Comput. Complex., 2019

The Resolution of Keller's Conjecture.
CoRR, 2019

An Algorithmic Blend of LPs and Ring Equations for Promise CSPs.
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

2018
Combining LPs and Ring Equations via Structured Polymorphisms.
Electron. Colloquium Comput. Complex., 2018

Promise Constraint Satisfaction: Structure Theory and a Symmetric Boolean Dichotomy.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017
A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover.
Electron. Colloquium Comput. Complex., 2017

Vertex Isoperimetry and Independent Set Stability for Tensor Powers of Cliques.
Proceedings of the Approximation, 2017

2016
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy.
Electron. Colloquium Comput. Complex., 2016

New hardness results for graph and hypergraph colorings.
Electron. Colloquium Comput. Complex., 2016

2015
Efficient Low-Redundancy Codes for Correcting Multiple Deletions.
Electron. Colloquium Comput. Complex., 2015

2013
Bounds on the Size of Sound Monotone Switching Networks Accepting Permutation Sets of Directed Trees
CoRR, 2013


  Loading...