5 citations · 6 across the 2 of their papers we have counts for
Showing cs.DSShow all
2 papers · 1 filter
cs.DS2022
Worst-Case to Average-Case Reductions via Additive Combinatorics
Vahid R. Asadi, Alexander Golovnev, Tom Gur +1
We present a new framework for designing worst-case to average-case reductions. For a large class of problems, it provides an explicit transformation of algorithms running in time…
cs.DS2018
Multitasking Capacity: Hardness Results and Improved Constructions
Noga Alon, Jonathan D. Cohen, Thomas L. Griffiths +5
We consider the problem of determining the maximal such that every matching of size (or at most ) in a bipartite graph contains an induced matching of s…