A note on dimensions of polynomial size circuits

DOI10.1016/j.tcs.2006.02.022zbMath1099.68045MaRDI QIDQ2503295

Xiaoyang Gu

Publication date: 14 September 2006

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2006.02.022

zbMATH Keywords

circuit complexity; resource-bounded dimension; resource-bounded measures

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

Pushdown dimension, Scaled dimension and the Kolmogorov complexity of Turing-hard sets, Effective Dimensions and Relative Frequencies

Cites Work

• Unnamed Item
• Weak completeness in \(\text{E}\) and \(\text{E}_{2}\)
• Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups
• Almost everywhere high nonuniform complexity
• A sequence of complexly computable functions
• Resource bounded randomness and weakly complete problems
• Scaled dimension and nonuniform complexity
• The dimensions of individual strings and sequences
• Dimension, entropy rates, and compression
• Circuit-size lower bounds and non-reducibility to sparse sets
• Cosmological lower bound on the circuit complexity of a small problem in logic
• Category and Measure in Complexity Classes
• Two definitions of fractional dimension
• Dimension in Complexity Classes
• STACS 2004