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.

  • $\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$
    – Sadguru
    Dec 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$
    – Sadguru
    Dec 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$ Aug 26, 2017 at 16:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.