## Abstract

We study the problem of detecting the regularity degree deg(f{hook}) = max{k: k ≤ r, f{hook} ∈ C^{k}} 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 language | English |
---|---|

Pages (from-to) | 373-386 |

Number of pages | 14 |

Journal | Journal of Complexity |

Volume | 9 |

Issue number | 3 |

DOIs | |

State | Published - Sep 1993 |

## ASJC Scopus subject areas

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