English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this work we study the quantitative relation between the recursiveteaching dimension (RTD) and the VC dimension (VCD) of concept classes offinite sizes. The RTD of a concept class $\mathcal C \subseteq \{0, 1\}^n$,introduced by Zilles et al. (2011), is a combinatorial complexity measurecharacterized by the worst-case number of examples necessary to identify aconcept in $\mathcal C$ according to the recursive teaching model.  For any finite concept class $\mathcal C \subseteq \{0,1\}^n$ with$\mathrm{VCD}(\mathcal C)=d$, Simon & Zilles (2015) posed an open problem$\mathrm{RTD}(\mathcal C) = O(d)$, i.e., is RTD linearly upper bounded by VCD?Previously, the best known result is an exponential upper bound$\mathrm{RTD}(\mathcal C) = O(d \cdot 2^d)$, due to Chen et al. (2016). In thispaper, we show a quadratic upper bound: $\mathrm{RTD}(\mathcal C) = O(d^2)$,much closer to an answer to the open problem. We also discuss the challenges infully solving the problem.

Quadratic Upper Bound for Recursive Teaching Dimension of Finite VC Classes