Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 22.05.2014 at 12:20 in S6, there is the following noon lecture:

Direct Sum Testing

Elazar Goldenberg

Abstract

For a string a \in {0,1}^n its k-fold direct sum encoding is a function f_a that takes as input sets S \subseteq [n] of size k and outputs f_a(S) = \sum_{i \in S} a_i.

In this talk we are discuss the Direct Sum Testing Problem, where we are given a function f, and our goal is to test whether f is close to a direct sum encoding, i.e., whether there exists some a \in \{0,1\}^n such that f(S) = \sum_{i \in S} a_i for most inputs S. By identifying the subsets of [n] with vectors in {0,1}^n in the natural way, this problem can be thought of as linearity testing of functions whose domain is restricted to the k-th layer of the hypercube.

We first consider the case k=n/2, and analyze for it a variant of the natural 3-query linearity test introduced by Blum, Luby, and Rubinfeld (STOC '90). Our analysis proceeds via a new proof for linearity testing on the hypercube, which extends also to our setting.

We then reduce the Direct Sum Testing

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010