48 citations · 103 across the 33 of their papers we have counts for
3 papers · 1 filter
On the Mysteries of MAX NAE-SAT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
MAX NAE-SAT is a natural optimization problem, closely related to its better-known relative MAX SAT. The approximability status of MAX NAE-SAT is almost completely understood if al…
A Simple Sublinear Algorithm for Gap Edit Distance
Joshua Brakensiek, Moses Charikar, Aviad Rubinstein
We study the problem of estimating the edit distance between two -character strings. While exact computation in the worst case is believed to require near-quadratic time, previo…
Smoothed Complexity of 2-player Nash Equilibria
Shant Boodaghians, Joshua Brakensiek, Samuel B. Hopkins +1
We prove that computing a Nash equilibrium of a two-player () game with payoffs in is PPAD-hard (under randomized reductions) even in the smoothed analysis set…