Dimension, Halfspaces, and the Density of Hard Sets

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

John M. Hitchcock, Ryan C. Harkins

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

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

Mathematics Subject Classification ID

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

Cited In (6)

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