Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets

We establish a relationship between the online mistake-bound model of learning and resource-bounded dimension. This connection is combined with the Winnow algorithm to obtain new results about the density of hard sets under adaptive reductions. This improves previous work of Fu (1995) and Lutz and Zhao (2000), and solves one of Lutz and Mayordomo's “Twelve Problems in Resource-Bounded Measure” (1999).

• Publication year

  2005

• Venue

  SIAM journal on computing (Print)

• Publication date

  2005-12-13

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/050647517arXiv cs/0512053
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Effective fractal dimensions

  2005cited by this paper
• SIGACT news complexity theory column 48

  2005cited by this paper
• A note on dimensions of polynomial size circuits

  2004cited by this paper
• Scaled dimension and nonuniform complexity

  2003cited by this paper
• Effective Strong Dimension, Algorithmic Information, and Computational Complexity

  2002influential reference
• MAX3SAT is exponentially hard to approximate if NP has positive dimension

  2002cited by this paper
• Dimension in complexity classes

  2000cited by this paper
• Resource-Bounded Measure and Learnability

  1998cited by this paper
• The Computational Complexity Column

  1998cited by this paper
• Six hypotheses in search of a theorem

  1997cited by this paper
• The density of weakly complete problems under adaptive reductions

  1997influential reference
• On the Existence of Hard Sparse Sets under Weak Reductions

  1996cited by this paper
• The quantitative structure of exponential time

  1993cited by this paper
• With quasi-linear queries, EXP is not polynomial time Turing reducible to sparse sets

  1993cited by this paper
• Reductions to Sets of Low Information Content

  1992cited by this paper
• How hard are sparse sets?

  1992cited by this paper
• Relating equivalence and reducibility to sparse sets

  1991cited by this paper
• On polynomial time bounded truth-table reducibility of NP sets to sparse sets

  1990cited by this paper
• Distinguishing Conjunctive and Disjunctive Reducibilities by Sparse Sets

  1989cited by this paper
• Almost everywhere high nonuniform complexity

  1989cited by this paper
• Queries and concept learning

  1988cited by this paper
• Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

  1987influential reference
• Polynomial Time Reducibility to a Set of Small Density: (Extended Abstract)

  1987cited by this paper
• Relativized circuit complexity

  1983influential reference
• Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis

  1980cited by this paper
• On isomorphisms and density of NP and other complete sets

  1976cited by this paper

• Counting Martingales for Measure and Dimension in Complexity Classes

  2025cites this paper
• Adaptive Ensemble Fault Diagnosis Based on Online Learning of Personalized Decision Parameters

  2018cites this paper
• Mutual dimension, data processing inequalities, and randomness

  2016cites this paper
• A medley for computational complexity: With applications of information theory, learning theory, and Ketan Mulmuley's parametric complexity technique Loff, B.F.L

  2014cites this paper
• Learning Reductions to Sparse Sets

  2013cites this paper
• Towards a reverse Newman’s theorem in information complexity

  2013cites this paper
• Limitations of Efficient Reducibility to the Kolmogorov Random Strings

  2012cites this paper
• Learning Weak Reductions to Sparse Sets

  2012cites this paper
• Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds

  2011cites this paper
• Resource-bounded Dimension in Computational Learning Theory

  2010influential citation
• Lower Bounds for Reducibility to the Kolmogorov Random Strings

  2010cites this paper
• NE Is Not NP Turing Reducible to Nonexponentially Dense NP Sets

  2010cites this paper
• Effective Fractal Dimension in Algorithmic Information Theory

  2008cites this paper
• NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly

  2008cites this paper
• Dimension, Halfspaces, and the Density of Hard Sets

  2007influential citation
• Efficient learning algorithms yield circuit lower bounds

  2006cites this paper
• Pushdown dimension

  2005cites this paper