Dimension, Halfspaces, and the Density of Hard Sets

DOI10.1007/978-3-540-73545-8_15zbMATH Open1206.68130OpenAlexW157716047MaRDI QIDQ3608839FDOQ3608839

Authors Ryan C. Harkins, John M. Hitchcock

Publication date 6 March 2009

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-73545-8_15

Mathematics Subject Classification ID

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

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
• On the hardness of learning intersections of two halfspaces
• Dimension in Complexity Classes

Cited in

(7)

• The Hardness of Approximating Poset Dimension
• Dimension, halfspaces, and the density of hard sets
• Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
• Odd cutsets and the hard-core model on \(\mathbb{Z}^{d}\)
• The size of Max\((p)\) sets and density bases.
• Axiomatizing resource bounds for measure
• 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 Q3608839)