[Colloquium] UC Theory Seminar: A REMINDER AND TIME/VENUE CHANGE

[Donna Brooms]

> 
> Subject: UC Theory Seminar: A REMINDER 
> 
> 
> DEPARTMENT OF COMPUTER SCIENCE
> 
> UNIVERSITY OF CHICAGO
> 
> Date: Friday, January 28, 2011
> Time: 4:00 p.m.
> Place: Ryerson 251, 1100 E. 58th Street
> 
> ----------------------------------------------
> 
> Speaker: Sourav Chakraborty
> 
> From: Chennai Institute for Mathematics
> 
> Web page: http://www.cmi.ac.in/~sourav/
> 
> Title: Nearly Tight Bounds for Testing Function Isomorphism
> 
> Abstract: We study the problem of testing structural equivalence (isomorphism)
> between a pair of Boolean
> functions $f,g:\{0,1\}^n \to \{0,1\}$. Our main focus is on the most
> studied case, where one of the functions is given (explicitly), and
> the other function can be queried.
> 
> We prove that for every $k \leq n$, the query complexity of testing
> isomorphism to $k$-juntas is
> $\Omega(k)$ and $O(k \log k)$. In particular, the (worst-case) query
> complexity of testing isomorphism to a given function $f:\{0,1\}^n \to
> \{0,1\}$ is $\widetilde\Theta (n)$.
> 
> Thus our bounds are nearly tight. Our lower bound and upper bound
> results improves the known bound obtained by Fischer et al. (2004),
> Blais and O'Donnell (2010), and recently by Alon and Blais (2010).
> 
> Our proof can also be extended to give polynomial query-complexity
> lower bounds for
> the problems of testing whether a function has a circuit of size $< s$,
> and testing whether the Fourier degree of a function is $\le d$. This
> answers questions posed by Diakonikolas et al. (2007).
> 
> One implication of our techniques is a query-efficient procedure that
> given oracle access to any $k$-junta $g:\{0,1\} \to \{0,1\}$ can draw
> uniformly-random  samples $(x,a) \in \{0,1\}^k \times \{0,1\}$
> labelled by the core of $g$, each sample being correct with high
> probability. Generating such samples is one of the main ingredients of
> the testers from Diakonikolas et al. (2007); while the procedure
> therein makes roughly $k$ queries to $g$ for obtaining each sample,
> our procedure requires only ONE query to $g$.
> 
> We also study the query complexity of testing isomorphism to
> $k$-juntas with one-sided error. We
> prove that for any $1 < k < n - 1$, the query complexity is
> $\Omega(\log {n \choose k})$, which is
> almost optimal. This lower bound is obtained by proving that the query
> complexity of testing, with one-sided error, whether a function is a
> $k$-parity is $\Theta(\log {n \choose k})$.
> 
> We also consider the problem of testing isomorphism between two
> unknown functions that can be queried. We prove that the (worst-case)
> query complexity in this setting is
> $\Omega(\sqrt{2^n})$ and $O(\sqrt{ 2^n n \log n})$.
> 
> This is a joint work with Arie Matsliah and David Garcia Soriano.
> 
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20110128/e606cdd0/attachment-0001.htm