48 citations · 103 across the 33 of their papers we have counts for
6 papers · 1 filter
The Resolution of Keller's Conjecture
Joshua Brakensiek, Marijn Heule, John Mackey +1
We consider three graphs, , , and , related to Keller's conjecture in dimension 7. The conjecture is false for this dimension if and only if at least one…
Coded trace reconstruction in a constant number of traces
Joshua Brakensiek, Ray Li, Bruce Spang
The coded trace reconstruction problem asks to construct a code such that any is recoverable from independent outputs ("traces") of from a binary…
The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs
Joshua Brakensiek, Venkatesan Guruswami, Marcin Wrochna +1
In the field of constraint satisfaction problems (CSP), promise CSPs are an exciting new direction of study. In a promise CSP, each constraint comes in two forms: "strict" and "wea…
Bridging between 0/1 and Linear Programming via Random Walks
Joshua Brakensiek, Venkatesan Guruswami
Under the Strong Exponential Time Hypothesis, an integer linear program with Boolean-valued variables and equations cannot be solved in time for any constant .…
Constant-factor approximation of near-linear edit distance in near-linear time
Joshua Brakensiek, Aviad Rubinstein
We show that the edit distance between two strings of length can be computed within a factor of in time as long as the edit distance is at least for…
CSPs with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo M, for various choices of th…