# Columbia computer scientists presenting four papers at STOC 2015

**On the Complexity of Nash Equilibria in Anonymous Games**

Xi Chen (Columbia University), David Durfee (Georgia Institute of Technology), Anthi Orfanou (Columbia University)

**Anthi Orfanou**

**Rocco Servedio**

**Boolean function monotonicity testing requires (almost)**

*n*^{1/2}non-adaptive queriesXi Chen (Columbia University), Anindya De (IAS), Rocco A. Servedio (Columbia University), Li-Yang Tan (UC Berkeley)

*monotone*or not, in the following sense: does increasing the input value always cause the output value to increase? Or can it sometimes cause the output to increase and sometimes to decrease? The standard way to check a data set for monotonicity is to scan through all the (input,output) pairs. However, this brute-force method is too inefficient for today’s massive high-dimensional data sets, when it is computationally too expensive to make even a single complete pass over the data.

*n*queries for

*n*-dimensional datasets (with 2

^{n}binary data entries), setting an upper bound on the query complexity of testing monotonicity of

*n*-variable Boolean functions. Subsequent work by Deeparnab Chakrabarty and C. Seshadhri recently pushed the number of queries down from

*n*to

*n*

^{7/8}.

*n*

^{1/2}non-adaptive queries,” Xi Chen, Anindya De (IAS), Rocco A. Servedio, and Li-Yang Tan (UC Berkeley) studied lower bounds on the number of queries required for monotonicity testing. Their paper proves a lower bound of

*n*

^{1/2}⁻

^{c}, for any positive constant c, on the query complexity of two-sided error non-adaptive algorithms for testing whether an

*n*-variable Boolean function is monotone versus far from monotone. This bound of

*n*

^{1/2}is also conjectured to be tight. Their result represents an improvement over the previous lower bound of

*n*

^{1/5}by Chen, Servedio, and Tan in 2014.

*n*

^{1/2}as conjectured, matching the lower bound of Chen, De, Servedio, and Tan.

**Allison Bishop**

**Indistinguishability Obfuscation for Turing Machines with Unbounded Memory**

Venkata Koppula (University of Texas at Austin), Allison Bishop (Columbia University), Brent Waters (University of Texas at Austin)

**Xiaorui Sun**

**In Faster Canonical Forms for Primitive Coherent Configurations**

Xiaorui Sun (Columbia University) and John Wilmes (University of Chicago)

^{1/2}))-time algorithm obtained more than three decades ago.

^{1/3})) and the same upper bound on the number of automorphisms of PCCs, making the first progress in 33 years on a 1982 conjecture of Babai.