Fall 2013

The Analysis of Partially Symmetric Functions

Tuesday, August 27th, 2013 3:00 pm3:25 pm

Add to Calendar

A partially symmetric function is a boolean function that is invariant to the reordering of all but a constant number of its variables. The set of partially symmetric functions includes juntas, symmetric functions, and a number of other functions as well. They were first studied by Shannon (1949) in the context of circuit complexity and have since been studied (under various names) in many other areas of theoretical computer science as well. Most recently, partially symmetric functions appeared in the context of property testing, where they are conjectured to essentially characterize the set of functions for which isomorphism testing can be done with a constant number of queries.

In this talk, we will examine how tools from the analysis of boolean functions might be used to understand partially symmetric functions and resolve some fundamental open problems related to the se functions.