  What is the value of input information in solving linear programming? The
celebrated ellipsoid algorithm tells us that the full information of input
constraints is not necessary; the algorithm works as long as there exists an
oracle that, on a proposed candidate solution, returns a violation in the
format of a separating hyperplane. Can linear programming still be efficiently
solved if the returned violation is in other formats?
  We study this question in a trial-and-error framework: there is an oracle
that, upon a proposed solution, returns the index of a violated constraint
(with the content of the constraint still hidden). When more than one
constraint is violated, two variants in the model are investigated. (1) The
oracle returns the index of a "most violated" constraint, measured by the
Euclidean distance of the proposed solution and the half-spaces defined by the
constraints. In this case, the LP can be efficiently solved. (2) The oracle
returns the index of an arbitrary (i.e., worst-case) violated constraint. In
this case, we give an algorithm with running time exponential in the number of
variables. We then show that the exponential dependence on n is unfortunately
necessary even for the query complexity. These results put together shed light
on the amount of information that one needs in order to solve a linear program
efficiently.
  The proofs of the results employ a variety of geometric techniques, including
McMullen's Upper Bound Theorem, the weighted spherical Voronoi diagram, and the
furthest Voronoi diagram. In addition, we give an alternative proof to a
conjecture of L\'aszl\'o Fejes T\'oth on bounding the number of disconnected
components formed by the union of m convex bodies in R^n. Our proof, inspired
by the Gauss-Bonnet Theorem in global differential geometry, is independent of
the known and reveals more clear insights into the problem and the bound.
