文章基本信息

标题：Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators
本地全文：下载
作者：Srinivasan Arunachalam ; Penghui Yao
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：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 mn , 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)=[x1A1++xnAnB] where the Ais are kk positive semidefinite matrices. We construct explicit PRGs that -fool "regular" width-M positive spectrahedrons (i.e., when none of the Ais are dominant) over the Boolean space with seed length poly(logklognM1) . Our main technical contributions are the following. We first prove an invariance principle for positive spectrahedrons via the well-known Lindeberg method. As far as we are aware such a generalization of the Lindeberg method was unknown. Second, we prove various geometric properties of positive spectrahedrons such as their noise sensitivity, Gaussian surface area and a Littlewood-Offord theorem for positive spectrahedrons. Using these results, we give applications for constructing PRGs for positive spectrahedrons, learning theory, discrepancy sets for positive spectrahedrons (over the Boolean cube) and PRGs for intersections of structured polynomial threshold functions.
关键词：derandomization;Invariance Principle;pseudo-random generator;Spectrahedron