Group:Student Seminar
Title: Property Testing: Graphs and Boolean Functions
Speaker: Chenggang Wu University
Time: 2010-12-02 16:00-2010-12-02 17:00
Venue: FIT 1-222

Abstract:

 this talk I will give some differences and relations between testing graph properties and boolean function properties. The first problem I will focus on is the isomorphism problem. I will review results on graph isomorphism testing, and compare this with boolean function isomorphism, which will be shown in the theory lunch meeting. Later I will show testing graph bipartitenss for dense graph model, which is an example for canonical tester for graph properties. I will also show some recent attemps on finding canonical tester for boolean function properties.