Showing 2024Show all
2 papers · 1 filter
cs.DS2024
Recognizing Sumsets is NP-Complete
Amir Abboud, Nick Fischer, Ron Safier +1
Sumsets are central objects in additive combinatorics. In 2007, Granville asked whether one can efficiently recognize whether a given set is a sumset, i.e. whether there is a s…
cs.DS2024
Worst-Case to Expander-Case Reductions: Derandomized and Generalized
Amir Abboud, Nathan Wallheimer
A recent paper by Abboud and Wallheimer [ITCS 2023] presents self-reductions for various fundamental graph problems, which transform worst-case instances to expanders, thus proving…