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
Faster Combinatorial k-Clique Algorithms
Amir Abboud, Nick Fischer, Yarin Shechter
Detecting if a graph contains a -Clique is one of the most fundamental problems in computer science. The asymptotically fastest algorithm runs in time , where i…