All reports by Author Penghui Yao:

__
TR21-013
| 20th January 2021
__

Srinivasan Arunachalam, Penghui Yao#### Positive spectrahedrons: Geometric properties, Invariance principles and Pseudorandom generators

__
TR17-010
| 18th January 2017
__

Xiaodi Wu, Penghui Yao, Henry Yuen#### Raz-McKenzie simulation with the inner product gadget

Revisions: 1

Srinivasan Arunachalam, Penghui Yao

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 >>>

Xiaodi Wu, Penghui Yao, Henry Yuen

In this note we show that the Raz-McKenzie simulation algorithm which lifts deterministic query lower bounds to deterministic communication lower bounds can be implemented for functions $f$ composed with the Inner Product gadget $g_{IP}(x,y) = \sum_i x_iy_i \mathrm{mod} \, 2$ of logarithmic size. In other words, given a function $f: ... more >>>