Expander Graphs
Expansion properties of random or structured graphs, and how to certify them.
| Status | Statement | Tags |
|---|---|---|
|
RM Gap to Capacity for BEC Conjecture 14 of the source. That Reed-Muller codes achieve capacity for the BEC is a theorem of Kudekar et al.; the gap to capacity – a polynomial rate of convergence – is open. The source needs it to strengthen its refutation of the expansion-implies-hardness conjecture for noisy k-XOR from quasi-polynomially many constraints to polynomially many, and notes the question was raised explicitly in three prior works. 4 open |
Average Case HardnessCode Based CryptographyExpander GraphsReed Solomon Codestight-bound | |
|
Certifying no small non-expanding set Open: whether the non-existence of a small non-expanding set in a random unbalanced bipartite graph admits a nondeterministic certificate that is sound and complete on average, at the parameters the ABW cryptosystem uses. The survey poses it as one of two closing open questions, takes no position, and does not return to it. |
Average Case HardnessExpander Graphsseparation |
No matching items