Strong XOR Lemma

Advisor: Professor Joshua Brody

Jae Tak Kim, Peem Lerdputtipongporn, Hari Srinivasulu

Given a computation task, one natural question a researcher can ask is how difficult it is or how much resource is required to perform such computation. Query Complexity is a field in Theoretical Computer Science that explores these questions. Our research group researches on Strong Direct Sum problem – a subfield in Query Complexity that studies how the computational resources (e.g. time, space, energy) and error scale with the instances of computation. More specifically, our research group works on Strong XOR lemma as defined below:

Let f be a Boolean function (a function that takes n-bit inputs and outputs 0 or 1) with some very low error. Suppose we want to compute multiple copies of f and XOR them (i.e. count if there are odd or even number of output 1) altogether, how much resource do we need to compute those XOR with a low error?

Because XOR is itself a Boolean function, this Strong XOR lemma lends itself to several interesting mathematical properties.