Dimension, Halfspaces, and the Density of Hard Sets

Ryan C. Harkins and John M. Hitchcock

Abstract: We use the connection between resource-bounded dimension and the online mistake-bound model of learning to show that the following classes have polynomial-time dimension zero.

  1. The class of problems which reduce to nondense sets via a majority reduction.

  2. The class of problems which reduce to nondense sets via an iterated reduction that composes a bounded-query truth-table reduction with a conjunctive reduction.
As corollary, all sets which are hard for exponential time under these reductions are exponentially dense. The first item subsumes two previous results and the second item answers a question asked by Lutz and Mayordomo. Our proofs use Littlestone's Winnow2 algorithm for learning r-of-k threshold functions and Maass and Turán's algorithm for learning halfspaces.