ACO Seminar - Noah Singer
— 4:00pm
Location:
In Person
-
Wean 8220
Speaker:
NOAH SINGER
,
Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://noahsinger.org/
“Direct-product testers” are objects used in the design of (some) probabilistically checkable proofs, which, in turn, play a fundamental role in modern complexity theory and cryptography. We gently introduce the direct-product testing problem and its relationship with expansion properties of simplicial complexes. Then, we discuss the so-called “Kaufman—Oppenheim coset complex” and our proof that it has direct-product testing properties which were previously known only for less-elementary constructions. We only assume a basic background in finite group theory (and no prior knowledge of theoretical computer science).
Based on joint work with Ryan O’Donnell.
4:00 pm → Jane Street-sponsored tea and cookies at in the math lounge (bring your mug!).
For More Information:
rkrueger@andrew.cmu.edu