\ n

\n

\nSymmetric properties of distributio ns arise in multiple settings. For each of these\, separate estimators and analysis techniques have been developed. Recently\, Orlitsky et al showed that a single estimator that maximizes profile maximum likelihood (PML) i s sample competitive for all symmetric properties. Further\, they showed t hat even a 2^{n^{1-delta}}-approximate maximizer of the PML objective can serve as such a universal plug-in estimator. (Here n is the size of the sa mple). Unfortunately\, no polynomial time computable PML estimator with su ch an approximation guarantee was known. We provide the first such estimat or and show how to compute it in time nearly linear in n.

\n

\nJoint work with Kiran Shiragur and Aaron Sidford.

\n

\n

\nMoses Charikar is a professor of Computer Science at Stanford Uni versity. He obtained his PhD from Stanford in 2000\, spent a year in the r esearch group at Google\, and was on the faculty at Princeton from 2001-20 15. He is broadly interested in approximation algorithms (especially the p ower of mathematical programming approaches)\, metric embeddings\, algorit hmic techniques for big data\, efficient algorithms for computational prob lems in high-dimensional statistics and optimization problems in machine l earning. He won the best paper award at FOCS 2003 for his work on the impo ssibility of dimension reduction\, the best paper award at COLT 2017 and t he 10 year best paper award at VLDB 2017. He was jointly awarded the 2012 Paris Kanellakis Theory and Practice Award for his work on locality sensit ive hashing inspired by random hyperplane rounding\, and was named a Simon s Investigator in theoretical computer science in 2014.

\n

\n