| Efficient low-redundancy codes for correcting multiple deletions J Brakensiek, V Guruswami, S Zbarsky IEEE Transactions on Information Theory 64 (5), 3403-3410, 2017 | 193 | 2017 |
| Promise constraint satisfaction: Algebraic structure and a symmetric Boolean dichotomy J Brakensiek, V Guruswami SIAM Journal on Computing 50 (6), 1663-1700, 2021 | 125* | 2021 |
| The resolution of Keller’s conjecture J Brakensiek, M Heule, J Mackey, D Narváez Journal of Automated Reasoning 66 (3), 277-300, 2022 | 71 | 2022 |
| New hardness results for graph and hypergraph colorings J Brakensiek, V Guruswami 31st Conference on Computational Complexity (CCC 2016), 14: 1-14: 27, 2016 | 68 | 2016 |
| Efficient geometric probabilities of multi-transiting exoplanetary systems from corbits J Brakensiek, D Ragozzine The Astrophysical Journal 821 (1), 47, 2016 | 60 | 2016 |
| 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 | 58 | 2020 |
| 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 | 56 | 2020 |
| 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 | 53 | 2023 |
| 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 | 47 | 2019 |
| 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 | 46 | 2020 |
| Conditional Dichotomy of Boolean Ordered Promise CSPs J Brakensiek, V Guruswami, S Sandeep TheoretiCS 2, 2023 | 26* | 2023 |
| 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 | 24 | 2022 |
| The quest for strong inapproximability results with perfect completeness J Brakensiek, V Guruswami ACM Transactions on Algorithms (TALG) 17 (3), 1-35, 2021 | 24* | 2021 |
| Improved field size bounds for higher order MDS codes J Brakensiek, M Dhar, S Gopi IEEE Transactions on Information Theory, 2024 | 23 | 2024 |
| 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 | 23 | 2020 |
| AG codes achieve list decoding capacity over constant-sized fields J Brakensiek, M Dhar, S Gopi, Z Zhang Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 740-751, 2024 | 19* | 2024 |
| SDPs and robust satisfiability of promise CSP J Brakensiek, V Guruswami, S Sandeep Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 609-622, 2023 | 19 | 2023 |
| Separating max 2-and, max di-cut and max cut J Brakensiek, N Huang, A Potechin, U Zwick 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS …, 2023 | 15 | 2023 |
| Symmetric polymorphisms and efficient decidability of promise CSPs J Brakensiek, V Guruswami Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete …, 2020 | 15 | 2020 |
| On the mysteries of MAX NAE-SAT J Brakensiek, N Huang, A Potechin, U Zwick SIAM Journal on Discrete Mathematics 39 (1), 267-313, 2025 | 14* | 2025 |
Venkatesan GuruswamiUniversity of California, BerkeleyVerified email at berkeley.edu
