Skip to main content
Technical Reports
Navigation
Technical Reports
UCSC-CRL-90-31: COMPOSITE GEOMETRIC CONCEPTS AND POLYNOMIAL PREDICTABILITY
« Previous
Next »
Authors
Published On
07/01/1990 09:00 AM
Department
Computer Science
Abstract
We study the predictability of geometric concepts, in particular those defined by boolean combinations of simple geometric objects. First, we give a negative result, showing that the problem of predicting the class of convex polytopes encoded by listing their vertices is prediction complete for P . Thus, an efficient solution to this prediction problem implies the existence of efficient solutions to all prediction problems whose associated evaluation problem is in P . Assuming the existence of a one-way function that is hard on iterates, there are such prediction problems which do not admit efficient solutions. Thus we show under minimalist cryptographic assumptions that the class of convex polytopes encoded by listing their vertices is not predictable. As a side effect, we show that determining membership in the convex hull of a given set of points is complete for P with respect to log space reductions. Next, we establish the predictability of the class consisting of unions of a fixed number of flats by reducing its prediction problem to that of the class of flats, which has previously been shown to be predictable. Finally, we given an Occam algorithm for predicting fixed finite unions of boxes. Both constructive results for flats and boxes hold if the dimension is variable.
Download
UCSC-CRL-90-31
Error | Technical Reports
Technical Reports
Error
The website encountered an unexpected error. Please try again later.