Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

On the usefulness of blowing things up (combinatorially)
event speaker icon
Eyal Rozenberg (Ph.D. Thesis Seminar)
event date icon
Tuesday, 01.11.2011, 13:30
event location icon
Taub 601
event speaker icon
Advisor: Assoc. Prof. Eldar Fischer
This talk will overview the results of my doctoral research in Property Testing of dense combinatorial structures. In Property Testing, we are concerned with the number of queries one has to make, or information one has to read, from an input combinatorial structure in order to make a rough distinctions between 'good' and 'significantly bad' inputs, where bad inputs are far from being good; specifically, most studies concerns such testing algorithms which read only a small fraction of their input, sometimes only a constant-size amount, independently of the size of the input. In much of my work I have made use of 'blowups' of smaller combinatorial objects into larger ones, analyzing the behavior of property testing algorithms applied to such blowups as input. The talk will highlight the use of blowups and aspects of their analysis, outlining how they can "force the hand" of property testing algorithms, leading to hardness results, and somewhat surprisingly also to a method of strengthening desirable features of such testing algorithms.