Approximate degree and bounded indistinguishability
COM1 Level 3
MR1, COM1-03-19
A Boolean function has approximate degree d if it can be approximated pointwise by a degree-d polynomial. Two distributions over n bits are d-wise indistinguishable (for d ≤ n) if their marginals on any subset of d bits are identical. The duality between these two notions can be used to prove composition theorems in one direction and construct secret sharing schemes in the other direction. I plan to show this connection and describe some recent developments in both domains.
Biodata:
Andrej Bogdanov is an Associate Professor in the Department of Computer Science and Engineering and Associate Director of the Institute of Theoretical Computer Science and Communications at the Chinese University of Hong Kong. He graduated from MIT and obtained his PhD from UC Berkeley. He was a postdoctoral researcher at the Institute for Advanced Study, DIMACS at Rutgers University, and ITCS at Tsinghua University before joining CUHK in 2008. His research interests include pseudorandomness, cryptography, and sublinear-time algorithms.