SODA Conference 2019 Conference Paper
XOR Codes and Sparse Learning Parity with Noise
- Andrej Bogdanov
- Manuel Sabin
- Prashant Nalini Vasudevan
Author name cluster
Manuel Sabin
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
2 papers
1 author row
Possible papers
2STOC Conference 2017 Conference Paper
Average-case fine-grained hardness
- Marshall Ball
- Alon Rosen
- Manuel Sabin
- Prashant Nalini Vasudevan
We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., IPL '94), but these have been canonical functions that have not found further use, while our functions are closely related to well-studied problems and have considerable algebraic structure.