Pseudo-Polynomial Time Algorithm for Computing Moments of Polynomials in Free Semicircular Elements

2019/01/23 by Rei Mizuta, Mizuta, Rei
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Mathematics and Applications #Operator Algebras (math.OA) #Polynomial and algebraic computation #Probability (math.PR) #Random Matrices and Applications #Stochastic processes and statistical mechanics

paper · pdf · doi:10.48550/arxiv.1901.08210

openalex publication_date 2019/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider about calculating Mth moments of a given polynomial in free independent semicircular elements in free probability theory. By a naive approach, this calculation requires exponential time with respect to M. We explicitly give an algorithm for calculating them in polynomial time by rearranging Schützenberger's algorithm.

Related

• On the computation of classical, boolean and free cumulants
• On the Moments of Exponential Sums over r-Free Polynomials
• Quantification of the Fourth Moment Theorem for Cyclotomic Generating Functions
• Sums of squares certificates for polynomial moment inequalities
• Algebraic certificates for the truncated moment problem