Adaptivity
What an algorithm loses when its queries cannot depend on the answers to earlier ones – the resource that separates Pollard’s Rho from baby-step giant-step, and whose value in the preprocessing model is largely unquantified.
| Status | Statement | Tags |
|---|---|---|
|
r-round DLOG tradeoff Open for every intermediate r: the r = 1 endpoint is the source’s own theorem and r = T is Corrigan-Gibbs–Kogan, with nothing proved in between. The source conjectures the interpolating formula and says a matching attack exists at every r, so the missing half is the lower bound. 6 open |
AdaptivityDiscrete LogarithmGeneric Group ModelTime Space Tradeoffsggmtight-bound | |
|
Non-adaptive DDH bound Open, and asserted rather than asked: the source proves 1/2 + O~(T^2/N + sqrt(ST/N)), states twice that it conjectures this is not tight for DDH, and names 1/2 + O~(T^2/N + ST/N) as the right answer. The same theorem’s square-DDH bound is sharp, with a matching attack, which is what makes the DDH case a question rather than a suspicion. 6 open |
AdaptivityDiscrete LogarithmGeneric Group ModelTime Space Tradeoffsggmtight-boundadaptation (ai) |
No matching items