BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1506
DTSTAMP:20241218T060403Z
SUMMARY:On Fourier analysis of sparse Boolean functions over certain Abelia
 n groups
DESCRIPTION:Speaker: Swarnalipa Datta (ISI Kolkata)\n\nAbstract: \nGiven an
  Abelian group G\, a Boolean-valued function $f: G \\to \\{-1\,+1\\}$\, is
  said to be s-sparse\, if it has at most s-many non-zero Fourier coefficie
 nts over the domain G. In a seminal paper\, Gopalan et al. in ``Testing Fo
 urier dimensionality and sparsity'' proved ``Granularity'' for Fourier coe
 fficients of Boolean valued functions over $\\mathbb{Z}_2^n$\, that have f
 ound many diverse applications in theoretical computer science and combina
 torics. They also studied structural results for Boolean functions over $\
 \mathbb{Z}_2^n$ which are approximately Fourier-sparse. In this work\, we 
 obtain structural results for approximately Fourier-sparse Boolean valued 
 functions over Abelian groups G of the form\, $G:= \\mathbb{Z}_{p_1}^{n_1}
  \\times \\cdots \\times \\mathbb{Z}_{p_t}^{n_t}$\, for distinct primes p_
 i. We also obtain a lower bound of the form $1/(m^{2}s)^{\\lceil \\varphi(
 m)/2 \\rceil}$\, on the absolute value of the smallest non-zero Fourier co
 efficient of an s-sparse function\, where $m=p_1 \\cdots p_t$\, and $\\var
 phi(m)=(p_1-1) \\cdots (p_t-1)$. We carefully apply probabilistic techniqu
 es from Gopalan et al.\, to obtain our structural results\, and use some n
 on-trivial results from algebraic number theory to get the lower bound.\nW
 e construct a family of at most s-sparse Boolean functions over $\\mathbb{
 Z}_p^n$\, where p > 2\, for arbitrarily large enough s\, where the minimum
  non-zero Fourier coefficient is o(1/s). The ``Granularity'' result of Gop
 alan et al. implies that the absolute values of non-zero Fourier coefficie
 nts of any s-sparse Boolean valued function over $\\mathbb{Z}_2^n$ are $\\
 Omega(1/s)$. So\, our result shows that one cannot expect such a lower bou
 nd for general Abelian groups.Using our new structural results on the Four
 ier coefficients of sparse functions\, we design an efficient sparsity tes
 ting algorithm for Boolean function\, which tests whether the given functi
 on is s-sparse\, or $\\epsilon$-far from any sparse Boolean function\, and
  it requires $\\mathrm{poly}((ms)^{\\varphi(m)}\,1/\\epsilon)$-many querie
 s.\nShort Bio: Swarnalipa Datta is a Senior Research Fellow in Computer S
 cience at the Indian Statistical Institute\, Kolkata\, working under the s
 upervision of Dr. Sourav Chakraborty and Dr. Arijit Ghosh on the Fourier a
 nalysis of Boolean functions. Swarnalipa completed a Bachelor's in Mathema
 tics from St. Xavier's College\, Kolkata\, and a Master's in Mathematics f
 rom the Indian Institute of Science\, Bangalore.\n
URL:https://www.tcs.tifr.res.in/web/events/1506
DTSTART;TZID=Asia/Kolkata:20241223T160000
DTEND;TZID=Asia/Kolkata:20241223T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR