{"ID":3084375,"CreatedAt":"2026-06-05T06:46:15.197025399Z","UpdatedAt":"2026-06-06T11:11:21.995702784Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.05245","arxiv_id":"2606.05245","title":"Worst-Case Update Complexity of the Preisach Extremum Stack","abstract":"The Preisach extremum stack $Π_n$ is the minimal sufficient statistic for the class $\\mathcal{R}$ of computable rate-independent functionals in the Kolmogorov complexity sense [1]. Its standard update algorithm runs in amortised $O(1)$ time, but adversarial inputs can force $Θ(k)$ operations per step (where $k$ is the current depth). We establish a three-level complexity picture: (i) any compact exact $\\mathcal{R}$-minimal representation incurs $Θ(k)$ output changes per step in the worst case (in a model-independent output-change metric); (ii) the monotone ordering of the Preisach wiping property enables binary search, reducing boundary detection to $O(log k)$, though physical deletion remains $Θ(d)$; (iii) a finger-tree implementation achieves $O(log k)$ worst-case time per step for both search and deletion, at the cost of a more complex data structure, while maintaining exact $\\mathcal{R}$-minimality with no approximation error. These results settle the worst-case complexity of the Preisach extremum stack across all three levels.","short_abstract":"The Preisach extremum stack $Π_n$ is the minimal sufficient statistic for the class $\\mathcal{R}$ of computable rate-independent functionals in the Kolmogorov complexity sense [1]. Its standard update algorithm runs in amortised $O(1)$ time, but adversarial inputs can force $Θ(k)$ operations per step (where $k$ is the...","url_abs":"https://arxiv.org/abs/2606.05245","url_pdf":"https://arxiv.org/pdf/2606.05245v1","authors":"[\"Piotr Frydrych\"]","published":"2026-06-03T11:23:57Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.FA\"]","methods":"[]","has_code":false}