Pengkun Yang's thesis, "Polynomial Methods in Statistical Inference: Theory and Practice" was completed in August 2018 at the Department of ECE at the University of Illinois at Urbana-Champaign under the supervision of Yihong Wu.
This thesis provides an exposition of a suite of techniques based on the theory of polynomials, collectively referred to as the polynomial methods, which are applied to address several challenging problems in statistical inference successfully. The applications in particular include the optimal estimation of the Shannon entropy, one fundamental quantity in information theory. The thesis contributes both to the design of fast algorithms and to the understanding of information-theoretical limits. In the algorithmic side, several sublinear-time algorithms are developed, which are becoming crucial nowadays when dealing with extremely large volumes of data; fundamentally, in the theoretical side, the information-theoretic limits are established using the same apparatus from the dual view.