@Article{YR80,
  author = 	 { Andrew C. Yao and Ronald L. Rivest },
  title = 	 { On the polyhedral decision problem },
  journal = 	 { SIAM J. Computing },
  issn =         { 0097-5397 },                  
  OPTyear = 	 { 1980 },
  OPTmonth = 	 { May },
  date =         { 1980-05 },                  
  volume = 	 { 9 },
  number = 	 { 2 },
  pages = 	 { 343--347 },
  keywords =     { adversary strategy, complexity, dimension, edge, face, linear
                   decision tree, lower bound, polyhedron },                  
  doi =          { 10.1137/0209028 },
  abstract =     {
                   Computational problems sometimes can be cast in the following form:
                   Given a point $\mathbf{x}$ in $R^n$, determine if $\mathbf{x}$ lies
                   in some fixed polyhedron.  In this paper we give a general lower bound
                   to the complexity of such problems, showing that $\frac{1}{2} \log_2 f_s$
                   linear comparisons are needed in the worst case, for any polyhedron with
                   $f_s$ $s$-dimensional faces.  For polyhedra with abundant faces, this leads
                   to lower bounds nonlinear in $n$, the number of variables.                  
                 },
}