7 citations · 7 across the 6 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2026
Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
Jarosław Błasiok, Paul Lou, Alon Rosen +1
In the noisy -XOR problem, one is given and must distinguish between uniform and , where is the adjacency matrix of a -left-regula…
cs.CC2022
PPP-Completeness and Extremal Combinatorics
Romain Bourneuf, Lukáš Folwarczný, Pavel Hubáček +2
Many classical theorems in combinatorics establish the emergence of substructures within sufficiently large collections of objects. Well-known examples are Ramsey's theorem on mono…
cs.CC2022
Downward Self-Reducibility in TFNP
Prahladh Harsha, Daniel Mitropolsky, Alon Rosen
A problem is \emph{downward self-reducible} if it can be solved efficiently given an oracle that returns solutions for strictly smaller instances. In the decisional landscape, down…