<p>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. </p>

CC BY-SA 3.0
2016-12-21T17:38:09.880Z
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.
Sadguru
CC BY-SA 3.0
2016-12-21T17:41:06.957Z
Also, the lower bound you have pointed to is via a topological argument and not via an adversary game.
Sadguru
CC BY-SA 3.0
2017-08-26T16:43:33.203Z
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.
Iddo Tzameret
<lower-bounds><decision-trees>
Algebraic decision trees and adversary arguments
Sadguru
# Algebraic decision trees and adversary arguments

(Asked by: username_0 on 2016-12-20)

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.

**Tags:** lower-bounds, decision-trees

> **Comments:**
> **username_0**: 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.  
> **username_0**: Also, the lower bound you have pointed to is via a topological argument and not via an adversary game.  
> **username_1**: 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.  

---

## 0 answers

