2 problems

0 votes0 replies1 view
The Small Set Expansion hypothesis
Small Set Expansion hypothesis. For any $\varepsilon>0$ , there is a constant $\delta\in(0,1)$ such that no polynomial-time algorithm can distinguish between the case…
Conjectureopencomputational-complexity graph-expansion small-set-expansionarXiv posted 2 days ago
0 votes0 replies0 views
Louis–Raghavendra–Tetali–Vempala small-set expansion conjecture
Louis–Raghavendra–Tetali–Vempala conjecture. The bound
Conjectureopengraph-partitioning small-set-expansion spectral-graph-theoryarXiv posted 2 days ago

The Small Set Expansion hypothesis