48 citations · 103 across the 33 of their papers we have counts for
Showing 2019 · cs.DSShow all
3 papers · 2 filters
cs.DS2019★ 31 cited
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…
cs.DS2019
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 .…
cs.DS2019
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…