Seguir
Joshua Brakensiek
Título
Citado por
Citado por
Año
Efficient low-redundancy codes for correcting multiple deletions
J Brakensiek, V Guruswami, S Zbarsky
IEEE Transactions on Information Theory 64 (5), 3403-3410, 2017
1652017
Promise constraint satisfaction: Algebraic structure and a symmetric boolean dichotomy
J Brakensiek, V Guruswami
SIAM Journal on Computing 50 (6), 1663-1700, 2021
80*2021
New hardness results for graph and hypergraph colorings
J Brakensiek, V Guruswami
31st Conference on Computational Complexity (CCC 2016), 2016
522016
Constant-factor approximation of near-linear edit distance in near-linear time
J Brakensiek, A Rubinstein
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing …, 2020
502020
Efficient geometric probabilities of multi-transiting exoplanetary systems from corbits
J Brakensiek, D Ragozzine
The Astrophysical Journal 821 (1), 47, 2016
492016
The resolution of Keller’s conjecture
J Brakensiek, M Heule, J Mackey, D Narváez
Journal of Automated Reasoning 66 (3), 277-300, 2022
462022
Coded trace reconstruction in a constant number of traces
J Brakensiek, R Li, B Spang
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020
342020
The power of the combined basic linear programming and affine relaxation for promise constraint satisfaction problems
J Brakensiek, V Guruswami, M Wrochna, S Zivny
SIAM Journal on Computing 49 (6), 1232-1248, 2020
332020
An algorithmic blend of LPs and ring equations for promise CSPs
J Brakensiek, V Guruswami
Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete …, 2019
322019
Generic reed-solomon codes achieve list-decoding capacity
J Brakensiek, S Gopi, V Makam
Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 1488-1501, 2023
222023
The quest for strong inapproximability results with perfect completeness
J Brakensiek, V Guruswami
ACM Transactions on Algorithms (TALG) 17 (3), 1-35, 2021
21*2021
Conditional Dichotomy of Boolean Ordered Promise CSPs
J Brakensiek, V Guruswami, S Sandeep
TheoretiCS 2, 2023
172023
Symmetric polymorphisms and efficient decidability of promise CSPs
J Brakensiek, V Guruswami
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete …, 2020
152020
Smoothed complexity of 2-player Nash equilibria
S Boodaghians, J Brakensiek, SB Hopkins, A Rubinstein
2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS …, 2020
122020
A simple sublinear algorithm for gap edit distance
J Brakensiek, M Charikar, A Rubinstein
arXiv preprint arXiv:2007.14368, 2020
112020
Lower bounds for maximally recoverable tensor codes and higher order MDS codes
J Brakensiek, S Gopi, V Makam
IEEE Transactions on Information Theory 68 (11), 7125-7140, 2022
102022
Improved field size bounds for higher order MDS codes
J Brakensiek, M Dhar, S Gopi
2023 IEEE International Symposium on Information Theory (ISIT), 1243-1248, 2023
82023
Constraint satisfaction problems with global modular constraints: Algorithms and hardness via polynomial representations
J Brakensiek, S Gopi, V Guruswami
SIAM Journal on Computing 51 (3), 577-626, 2022
7*2022
On the mysteries of MAX NAE-SAT
J Brakensiek, N Huang, A Potechin, U Zwick
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA …, 2021
62021
Bridging between 0/1 and linear programming via random walks
J Brakensiek, V Guruswami
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing …, 2019
62019
El sistema no puede realizar la operación en estos momentos. Inténtalo de nuevo más tarde.
Artículos 1–20