A note on dimensions of polynomial size circuits

Xiaoyang Gu

Abstract

In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every i ≥0, P/poly has i th-order scaled p3-strong dimension 0. We also show that P/polyio has p3-dimension 1/2 and p3-strong dimension 1. Our results improve previous measure results of Lutz (1992) and dimension results of Hitchcock and Vinodchandran (2004). Additionally, we establish a Supergale Dilation Theorem, which extends the martingale dilation technique introduced implicitly by Ambos-Spies, Terwijn, and Zheng (1997) and made explicit by Juedes and Lutz (1995).

Journal Version:

Last modified on August 2nd, 2006.