The new Simons Institute for the Theory of Computing opened its doors this August, and kicked things off with a workshop on real analysis and its applications in property testing, learning theory, and inapproximability. Among many great talks (see here for the full schedule) were the following presentations on property testing and related topics.

Ryan O’Donnell on Testing Surface Area. Given a subset \(S \in [0,1]^2\) of the unit square, can we efficiently test whether the set has small perimeter? Buffon’s needle suggests a natural test: drop a (small) needle at random in the square and see if exactly one of its endpoints lands in the set \(S\). Ryan showed how elegant noise sensitivity arguments show the correctness of this test and its higher-dimensional analogues.

I gave a talk on The Analysis of Partially Symmetric Functions. I gave a brief introduction to partially symmetric functions, tools from the analysis of boolean functions that help us understand them, and their role in theoretical computer science, with a particular emphasis on the function isomorphism testing conjecture.

Hamed Hatami on Testing Affine-Invariant Properties of Algebraic Functions. Hamed gave a fascinating survey of the recent progress on testing affine-invariant properties. He showed how the tools that have been used to analyze the testability of properties of graphs can be combined with tools from higher-order Fourier analysis of boolean functions to analyze the testability of algebraic properties of functions.

Parikshit Gopalan on Locally Testable Codes and Cayley Graphs. Despite a considerable amount of interest and attention, many fundamental questions regarding locally testable codes remain open. Parikshit’s talk gave a very nice connection between LTCs and some Cayley graphs which enables us to view LTCs from a different angle and will hopefully lead to further progress on these open problems.

Nati Linial on Local Combinatorics, Or: What to do with all those gigantic graphs?. Let’s say that you want to keep a snapshot of a huge graph \(G\), but only have a very small amount of space available. What can you do? One natural solution is to keep a local k-profile of the graph: for each graph \(H\) on \(k\) vertices, count the number of embedded copies of \(H\) in \(G\). Nati’s talk showed that the study of the connections between local k-profiles of graphs and global properties of graphs leads to very nice results as well as a wealth of intriguing open problems.

Many other interesting workshops on real analysis in computer science and on the theoretical foundations of big data analysis will be held throughout the semester. See the respective pages for all the details, and for videos of the talks.