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