[Theory Lunch 10/02] Jiapeng Zhang: DNFs and related questions

[Haoming Li]

USC CS Theory Lunch:

DNFs and related questions
Speaker: Jiapeng Zhang (https://sites.google.com/site/jiapeng0708/)
Time: 10/02/20 12:00pm
Location: https://usc.zoom.us/j/94386654763

Abstract:

In this talk, I will discuss some structural results about disjunctive normal forms. In particular, I will discuss its connections to polynomial degrees, sunflower structure, and computational learning theory. If time permits, I will also discuss some future direction and open problems.

Related papers:
- Improved bounds for the sunflower lemma: https://arxiv.org/abs/1908.08483
- Decision list compression by mild random restriction: https://arxiv.org/abs/1909.10658
- Constant Depth Circuits, Fourier Transform, and Learnability: http://www.ma.huji.ac.il/~ehudf/courses/anal09/LMN.pdf

See rest of semester schedule at:
https://viterbi-web.usc.edu/~cstheory/theory-lunch.html