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 '16 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 '16 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 Tzameret Aug 26 '17 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.