The Taub Faculty of Computer Science Events and Talks

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.