[Colloquium] Reminder: Hatami/MS Presentation/Jan 19, 2012

[Margaret Jaffey]

This is a reminder about Pooya's MS Presentation tomorrow.

------------------------------------------------------------------------------
Date:  Thursday, January 19, 2012

Time:  3:00 PM

Place:  Ryerson 251

M.S. Candidate:  Pooya Hatami

M.S. Paper Title: Testing Properties of Boolean Functions: Lower
Bounds on Testing Fourier Degree

Abstract:
We consider the problem of deciding whether a given object has a given
property or it is far from any object with the property, referred to
as property testing. We focus on the case where the objects are
Boolean functions, and we survey some of the previously known results
about testing for properties such as the number of relevant variables
and Fourier degree of a Boolean function. We present the recently
developed technique for proving lower bounds in property testing,
which is based on showing connections between property testing and
communication complexity [13]. For the problem of testing whether a
Boolean function has Fourier degree ≤ k or it is ǫ-far
from any Boolean function with Fourier degree ≤ k, we improve
the known lower bound of Ω(k) [13, 18], to
Ω(k/√ǫ), using reductions from communication
complexity.

Pooya's advisor is Prof. Alexander Razborov

Login to the Computer Science Department website for details:
 https://www.cs.uchicago.edu/phd/ms_announcements#pooya

=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey            margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156)               (773) 702-6011
The University of Chicago      http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=