BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/158
DTSTAMP:20230914T125912Z
SUMMARY:Nearly Tight Bounds for Testing Function Isomorphism
DESCRIPTION:Speaker: Sourav Chakraborty\nChennai Mathematical Institute\nPl
ot No. H1\nSIPCOT IT Park\nPadur PO\nSiruseri - 603103\n\nAbstract: \nWe s
tudy 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.\n\nWe prove t
hat 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)$.
\n\nThus our bounds are nearly tight. Our lower bound and upper bound resu
lts improves the known bound obtained by Fischer et al. (2004)\, Blais and
O'Donnell (2010)\, and recently by Alon and Blais (2010).\n\nOur proof ca
n also be extended to give polynomial query-complexity lower bounds for th
e 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 answ
ers questions posed by Diakonikolas et al. (2007).\n\nOne implication of o
ur techniques is a query-efficient procedure that given oracle access to a
ny $k$-junta $g:\\\\{0\,1\\\\} \\\\to \\\\{0\,1\\\\}$ can draw uniformly-r
andom samples $(x\,a) \\\\in \\\\{0\,1\\\\}^k \\\\times \\\\{0\,1\\\\}$ l
abelled by the core of $g$\, each sample being correct with high\nprobabil
ity. Generating such samples is one of the main ingredients of the testers
from Diakonikolas et al. (2007) while the procedure therein makes roughl
y $k$ queries to $g$ for obtaining each sample\, our procedure requires on
ly ONE query to $g$.\n\nWe also study the query complexity of testing isom
orphism 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})$.\n\nWe also conside
r the problem of testing isomorphism between two unknown functions that ca
n be queried. We prove that the (worst-case) query complexity in this sett
ing is $\\\\Omega(\\\\sqrt{2^n})$ and $O(\\\\sqrt{ 2^n n \\\\log n})$ (thi
s is a joint work with Arie Matsliah and David Garcia Soriano).\n
URL:https://www.tcs.tifr.res.in/web/events/158
DTSTART;VALUE=DATE:20110202
LOCATION:AG-69
END:VEVENT
END:VCALENDAR