On Detecting Regularity of Functions: A Probabilistic Analysis

F. Gao, G. W. Wasilkowski

Research output: Contribution to journalArticlepeer-review


We study the problem of detecting the regularity degree deg(f{hook}) = max{k: k ≤ r, f{hook} ∈ Ck} of functions based on a finite number of function evaluations. Since it is impossible to find deg(f{hook}) for any function f{hook}, we analyze this problem from a probabilistic perspective. We prove that when the class of considered functions is equipped with a Wiener-type probability measure, one can compute deg(f{hook}) exactly with super exponentially small probability of failure. That is, we propose an algorithm which, given n function values at equally spaced points, might propose a value different than deg(f{hook}) only with probability O((n-1 ln n)(n - r)/4). Hence, regularity detection is easy in the probabilistic setting even though it is unsolvable in the worst case setting.

Original languageEnglish
Pages (from-to)373-386
Number of pages14
JournalJournal of Complexity
Issue number3
StatePublished - Sep 1993

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • General Mathematics
  • Control and Optimization
  • Applied Mathematics


Dive into the research topics of 'On Detecting Regularity of Functions: A Probabilistic Analysis'. Together they form a unique fingerprint.

Cite this