Speaker this week's QuSoft seminar is Srinivasan Arunachalam on 'Positive spectrahedra: Invariance principles and Pseudorandom
generators'.
Abstract:
In a recent work, O'Donnell, Servedio and Tan (STOC 2019) gave explicit pseudorandom generators (PRGs) for arbitrary m-facet polytopes in n variables with seed length poly-logarithmic in m,n, concluding a sequence of works in the last decade, that was started by Diakonikolas, Gopalan, Jaiswal, Servedio, Viola (SICOMP 2010) and Meka, Zuckerman (SICOMP 2013) for fooling linear and polynomial threshold functions, respectively. In this work, we consider a natural extension of PRGs for intersections of positive spectrahedra. A positive spectrahedron is a Boolean function f(x)=[x_1 A_1+⋯+x_n A_ n \preceq B] where the Ais are k × k positive semidefinite matrices. We construct explicit PRGs that δ-fool "regular" width-M positive spectrahedrons (i.e., when none of the
A_i s are dominant) over the Boolean space with seed length poly (log k,log n,M,1/δ).
Our main technical contributions are the following: We first prove an invariance principle for positive spectrahedra via the well-known Lindeberg method. As far as we are aware such a generalization of the Lindeberg method was unknown. Second, we prove an upper bound on noise sensitivity and a Littlewood-Offord theorem for positive spectrahedra. Using these results, we give applications for constructing PRGs for positive spectrahedra, learning theory, discrepancy sets for positive spectrahedra (over the Boolean cube) and PRGs for intersections of structured polynomial threshold~functions.
Joint work with Penghui Yao and available at https://arxiv.org/abs/2101.08141
Please contact Subhasree Patro or Jop Briet for the zoom link.
