Joshua Brakensiek
Titolo
Citata da
Citata da
Anno
Efficient low-redundancy codes for correcting multiple deletions
J Brakensiek, V Guruswami, S Zbarsky
IEEE Transactions on Information Theory 64 (5), 3403-3410, 2017
862017
Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy
J Brakensiek, V Guruswami
arXiv preprint arXiv:1704.01937, 2017
41*2017
Efficient geometric probabilities of multi-transiting exoplanetary systems from corbits
J Brakensiek, D Ragozzine
The Astrophysical Journal 821 (1), 47, 2016
362016
New hardness results for graph and hypergraph colorings
J Brakensiek, V Guruswami
31st Conference on Computational Complexity (CCC 2016), 2016
312016
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
172019
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
152020
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
142020
The quest for strong inapproximability results with perfect completeness
J Brakensiek, V Guruswami
Approximation, Randomization, and Combinatorial Optimization. Algorithms and …, 2017
132017
The resolution of Keller’s conjecture
J Brakensiek, M Heule, J Mackey, D Narváez
International Joint Conference on Automated Reasoning, 48-65, 2020
102020
Symmetric polymorphisms and efficient decidability of promise CSPs
J Brakensiek, V Guruswami
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete …, 2020
92020
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
4*2020
A simple sublinear algorithm for gap edit distance
J Brakensiek, M Charikar, A Rubinstein
arXiv preprint arXiv:2007.14368, 2020
32020
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
22019
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
12019
Vertex isoperimetry and independent set stability for tensor powers of cliques
J Brakensiek
arXiv preprint arXiv:1702.04432, 2017
12017
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
12013
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
Il sistema al momento non può eseguire l'operazione. Riprova più tardi.
Articoli 1–20