| Efficient low-redundancy codes for correcting multiple deletions J Brakensiek, V Guruswami, S Zbarsky IEEE Transactions on Information Theory 64 (5), 3403-3410, 2017 | 82 | 2017 |
| Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy J Brakensiek, V Guruswami arXiv preprint arXiv:1704.01937, 2017 | 37* | 2017 |
| Efficient geometric probabilities of multi-transiting exoplanetary systems from corbits J Brakensiek, D Ragozzine The Astrophysical Journal 821 (1), 47, 2016 | 34 | 2016 |
| New hardness results for graph and hypergraph colorings J Brakensiek, V Guruswami 31st Conference on Computational Complexity (CCC 2016), 2016 | 30 | 2016 |
| 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 | 15 | 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 | 14 | 2020 |
| The quest for strong inapproximability results with perfect completeness J Brakensiek, V Guruswami Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2017 | 13 | 2017 |
| 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 | 11 | 2020 |
| The resolution of Keller’s conjecture J Brakensiek, M Heule, J Mackey, D Narváez International Joint Conference on Automated Reasoning, 48-65, 2020 | 8 | 2020 |
| Symmetric polymorphisms and efficient decidability of promise CSPs J Brakensiek, V Guruswami Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete …, 2020 | 8 | 2020 |
| A simple sublinear algorithm for gap edit distance J Brakensiek, M Charikar, A Rubinstein arXiv preprint arXiv:2007.14368, 2020 | 3 | 2020 |
| The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems J Brakensiek, V Guruswami, M Wrochna, S Živný SIAM Journal on Computing 49 (6), 1232-1248, 2020 | 2* | 2020 |
| 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 | 2 | 2019 |
| Csps with global modular constraints: Algorithms and hardness via polynomial representations J Brakensiek, S Gopi, V Guruswami Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing …, 2019 | 1 | 2019 |
| Vertex isoperimetry and independent set stability for tensor powers of cliques J Brakensiek arXiv preprint arXiv:1702.04432, 2017 | 1 | 2017 |
| Bounds on the size of sound monotone switching networks accepting permutation sets of directed trees J Brakensiek, A Potechin arXiv preprint arXiv:1301.3780, 2013 | 1 | 2013 |
| Conditional Dichotomy of Boolean Ordered Promise CSPs J Brakensiek, V Guruswami, S Sandeep arXiv preprint arXiv:2102.11854, 2021 | | 2021 |
| 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 | | 2021 |
| Smoothed Complexity of 2-player Nash Equilibria S Boodaghians, J Brakensiek, SB Hopkins, A Rubinstein arXiv preprint arXiv:2007.10857, 2020 | | 2020 |
| A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover. J Brakensiek, V Guruswami Electronic Colloquium on Computational Complexity (ECCC) 24, 141, 2017 | | 2017 |
Venkatesan GuruswamiCarnegie Mellon UniversityEmail verificata su cmu.edu
