Theory Lunch This Week (Thursday 1/30, GCS 502C, 12:00 PM)

[Grayson York]

Hi all,

This Thursday 1/30 Kewen Wu from will be visiting from Berkeley and giving the following talk at 12:00PM in GCS 502C. Hope to see you all there!

Title: Locally Sampleable Uniform Symmetric Distributions

Abstract: We characterize the power of constant-depth Boolean circuits 
in generating uniform symmetric distributions. Let f:{0,1}^m -> {0,1}^n 
be a Boolean function where each output bit of f depends only on O(1) 
input bits. Assume the output distribution of f on uniform input bits is 
close to a uniform distribution D with a symmetric support. We show that 
D is essentially one of the following six possibilities: (1) point 
distribution on 0^n, (2) point distribution on 1^n, (3) uniform over 
{0^n,1^n}, (4) uniform over strings with even Hamming weights, (5) 
uniform over strings with odd Hamming weights, and (6) uniform over all 
strings. This confirms a conjecture of Filmus, Leigh, Riazanov, and 
Sokolov (RANDOM 2023).
Joint work with Daniel M. Kane and Anthony Ostuni.

[Grayson York]

Hi all, please join us at the following zoom link:

https://usc.zoom.us/j/98386520728?pwd=gV33xULlam5K2fcO4ga26F3CzvBqrt.1