MathDB1 problem
- 0 votes0 replies1 view
Brennan et al.'s semi-random planted dense subgraph hardness conjecture
Consider the planted dense subgraph model with adversarial edge deletions outside the planted subgraph, and let weak recovery mean producing an estimate correlated with the planted…