Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR21-013 | 20th January 2021 16:32

#### Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators

TR21-013
Authors: Srinivasan Arunachalam, Penghui Yao
Publication: 14th February 2021 16:29
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 spectrahedrons. A positive spectrahedron is a Boolean function $f(x)=[x_1A^1+\cdots +x_nA^n \preceq B]$ where the $A^i$s are $k\times k$ positive semidefinite matrices. We construct explicit PRGs that $\delta$-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/\delta)$.