Dimension, halfspaces, and the density of hard sets

DOI10.1007/S00224-010-9288-1MaRDI QIDQ649114zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

class Eclass Pcomplexity classesonline mistake-bound model of learningpolynomial-time dimension zeroresource-bounded dimension

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational learning theory (68Q32)

Recommendations

• Dimension, Halfspaces, and the Density of Hard Sets
• Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
• Online Learning and Resource‐Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
• Dimension in Complexity Classes
• scientific article; zbMATH DE number 2038717

Cites work

• Almost everywhere high nonuniform complexity
• Dimension in Complexity Classes
• Effective Strong Dimension in Algorithmic Information and Computational Complexity
• Geometric sets of low information content
• scientific article; zbMATH DE number 1346358 (Why is no real title available?)
• scientific article; zbMATH DE number 512798 (Why is no real title available?)
• scientific article; zbMATH DE number 1072536 (Why is no real title available?)
• Measure, Stochasticity, and the Density of Hard Languages
• Online Learning and Resource‐Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
• Resource-bounded measure and learnability
• The Density of Weakly Complete Problems under Adaptive Reductions
• With Quasilinear Queries EXP Is Not Polynomial Time Turing Reducible to Sparse Sets

Cited in

(5)

• The Hardness of Approximating Poset Dimension
• Dimension, Halfspaces, and the Density of Hard Sets
• Odd cutsets and the hard-core model on \(\mathbb{Z}^{d}\)
• Online Learning and Resource‐Bounded Dimension: Winnow Yields New Lower Bounds for Hard 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q649114)