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.

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

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.

Theory of Computing Systems, 49(3):601-614, 2011.
[DOI | PDF]

Proceedings of the 13th Annual International Computing and
Combinatorics Conference (Banff, Canada, July 16-19, 2007),
Lecture Notes in Computer Science 4598, pages 129-139.
Springer-Verlag, 2007.
[DOI]