[Colloquium] Theory Seminars at Computer Science

[Donna Brooms via Colloquium]

REMINDER:

Departments of Computer Science & Mathematics
Combinatorics & Theory Seminar

Tuesday, May 9, 2017
Ryerson 251 @ 3pm

Erik Waingarten
Columbia University

Title: “On the query complexity of Boolean monotonicity testing”

In this talk, I will discuss recent adaptive lower bounds on the query complexity of testing monotonicity of Boolean functions. The problem asks to minimize the number of queries to an unknown Boolean function a randomized algorithm must make in order to distinguish between the case the function is monotone and then case the function is far from monotone. I will show an Omega(n^{1/3}) lower bound by introducing a new family of random Boolean functions extending Talagrand's random DNFs. This talk is based on joint work with Xi Chen and Jinyu Xie. 

Host:  Prof. Li-Yang Tan

Refreshments will be served before the talk in Ry 255.

 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Erik W.docx
Type: application/vnd.openxmlformats-officedocument.wordprocessingml.document
Size: 157863 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20170509/1d2dede7/attachment-0001.docx>
-------------- next part --------------