Group:Student Seminar
Title: Lower Bounds for Testing Triangle-freeness in Boolean Functions
Speaker: Wei Hu Tsinghua university
Time: 2010-04-08 16:00-2010-04-08 17:00
Venue: FIT1-222

Abstract:

I will show a paper of SODA 2010. It is "Lower Bounds for Testing Triangle-freeness in Boolean Functions" by Arnab Bhattacharyya and Ning Xie which has some relation with the mini course.

Let f_1, f_2, f_3 : {0, 1}^n->{0, 1} be Boolean functions. A triple (x, y, x+y) is a triangle in the function-triple (f_1, f_2, f_3) if f_1(x)=f_2(y)=f_3(x+y)=1. (f_1, f_2, f_3) is said to be triangle-free if there is no triangle in all the triples.

In that paper they give a non-trivial lower bound of the quest number for canonical tester. That is, for multiple function case (f_1, f_2, f_3) the lower bound is (1/\epsilon)^4.847. For single function case (f_1, f_1, f_1) it is (1/\epsilon)^3.409.

Short Bio: