Planted Subgraph Problems
Hiding a clique, an independent set or another subgraph in a random graph, and the hardness of finding or distinguishing it.
| Status | Problem | Tags |
|---|---|---|
|
Planted-Subgraph Character Sum The source derives the formula governing low-degree detection of a planted subgraph, observes the character sum in it should be small for most graphs, and says it leaves the rigorous study of the question to future work. No bound is proved and none is stated as a target. 5 open |
Average Case HardnessPlanted Subgraph Problemslower-boundadaptation (ai) | |
|
Sub-log Share Size for 2-out-of-\(n\) The information-theoretic share size is exactly \(\log n\) and Shamir’s scheme matches it. The source proves a \((1/5)\log\log n\) lower bound for the computational setting with public information, leaving a \(\log n\) versus \(\log\log n\) gap, and proves that beating \(\log n\) by any constant factor is equivalent to a concrete planted clique-and-independent-set problem. 4 open |
Average Case HardnessPlanted Subgraph ProblemsThreshold Secret Sharingtight-bound |
No matching items