Consider the following problem: given a function from (F2)n to F2 we need to decide whether it is “highly structured”, which in our case means representable by a low-degree n-variate polynomial over F2, or “pseudorandom”, which we take to mean being far from all low-degree polynomials. Our decision has to be based on a very restricted randomized local view of the function. This question arises naturally in ‘property testing’, a sub-area of theoretical computerscience which deals with deciding whether a given combinatorial object has a certain global property or, alternatively, is far from all objects with this property, based on viewing some randomized local samples from the object. It also has some connections with other areas of theoretical cs, such as probabilistically checkable proofs and derandomization. We will discuss some recent developments regarding this question. In particular, it turns out that an attempt to measure pseudorandomness of a function analytically, via its ‘Gowers norm’, does not work so well. Based in part on joint work with Shachar Lovett, Roy Meshulam, and Luca Trevisan