Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Spectrahedron:
TR21-013 | 20th January 2021
Srinivasan Arunachalam, Penghui Yao

Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators

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, ... more >>>

TR21-178 | 3rd December 2021
Srinivasan Arunachalam, Oded Regev, Penghui Yao

On the Gaussian surface area of spectrahedra

We show that for sufficiently large $n\geq 1$ and $d=C n^{3/4}$ for some universal constant $C>0$, a random spectrahedron with matrices drawn from Gaussian orthogonal ensemble has Gaussian surface area $\Theta(n^{1/8})$ with high probability.

more >>>

ISSN 1433-8092 | Imprint