Before revision:  We first show that adaptivity helps in LIS estimation, specifically , for every constant \epsilon \in (0,1), every nonadaptive algorithm that outputs an estimate of the length of the LIS in an array of length n to within an additive error of \epsilon \cdot n has to make \log^{\Omega(\log (1/\epsilon))} n) queries.
After revision:  We first show that adaptivity helps in LIS estimation, and also provide novel algorithms that complement our lower bound. Specifically , for every constant \epsilon \in (0,1), every nonadaptive algorithm that outputs an estimate of the length of the LIS in an array of length n to within an additive error of \epsilon \cdot n has to make \log^{\Omega(\log (1/\epsilon))} n) queries.