We study some problems relating to polynomials evaluated either at random Gaussian or random Bernoulli inputs. We present a structure theorem for degree-d polynomials with Gaussian inputs. In particular, if p is a given degree-d polynomial, then p can be written in terms of some bounded number of other polynomials q_1,...,q_m so that the joint probability density function of q_1(G),...,q_m(G) is close to being bounded. This says essentially that any abnormalities in the distribution of p(G) can be explained by the way in which p decomposes into the q_i. We then present some applications of this result.
Daniel Kane studied mathematics and computer science as an undergraduate at MIT, doing research with Erik Demaine, Joe Gallian, and Cesar Silva. He received his PhD from the Mathematics Department of Harvard under the supervision of Barry Mazur, Benedict Gross, and Henry Cohn. He is currently a postdoc in the Mathematics Department at Stanford. He has won Best Paper awards at CCC 2013 and PODS 2010, and Best Student Paper awards at CCC 2010 and FOCS 2005. His diverse research interests include analytic number theory, polynomial threshold functions, and derandomization.
Faculty Hosts: Ryan O'Donnell, Po-Shen Log
Refreshments: 4:00 pm - Wean 6220
pj [atsymbol] andrew.cmu.edu