Dimension, halfspaces, and the density of hard sets
From MaRDI portal
Publication:649114
DOI10.1007/S00224-010-9288-1zbMath1227.68035OpenAlexW2037549187MaRDI QIDQ649114
Ryan C. Harkins, John M. Hitchcock
Publication date: 30 November 2011
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.684.8045
complexity classesclass Pclass Eonline mistake-bound model of learningpolynomial-time dimension zeroresource-bounded dimension
Computational learning theory (68Q32) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Almost everywhere high nonuniform complexity
- Geometric sets of low information content
- Resource-bounded measure and learnability
- Effective Strong Dimension in Algorithmic Information and Computational Complexity
- Measure, Stochasticity, and the Density of Hard Languages
- Dimension in Complexity Classes
- The Density of Weakly Complete Problems under Adaptive Reductions
- With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets
- Online Learning and Resource‐Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
This page was built for publication: Dimension, halfspaces, and the density of hard sets
