In the comparison tree model, we establish lower bounds on computing $\min$ and $\max$ of $n$ numbers via the adversary argument. Are there problems on which we know lower bounds in the algebraic decision tree model via the adversary argument? Please suggest relevant references.
3
-
$\begingroup$ Of course there are lots of other problems on which we can show lower bounds in comparison trees using adversary argument. But I haven't seen any lower bound using adversary argument in the algebraic decision tree model. $\endgroup$– SadguruDec 21, 2016 at 17:38
-
$\begingroup$ Also, the lower bound you have pointed to is via a topological argument and not via an adversary game. $\endgroup$– SadguruDec 21, 2016 at 17:41
-
$\begingroup$ What about linear decision trees, namely, decision trees in which nodes are linear equations over GF(2)? These have exponential size lower bounds using an "adversary" argument. That is, a game between a Prover and a Delayed. Cf. Impagliazzo/Pudlak 2001, and Itsykson/Sokolov 2014. $\endgroup$– Iddo TzameretAug 26, 2017 at 16:43
Add a comment
|