BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1622
DTSTAMP:20251208T054637Z
SUMMARY:Fourier Analysis on finite Abelian groups and its Applications
DESCRIPTION:Speaker: Swarnalipa Datta (ISI Kolkata)\n\nAbstract: \n\nA Bool
 ean-valued function is a map from a domain D to a range of cardinality two
 \, such as {−1\, +1}\, or {0\, 1}. These functions play a central role i
 n theoretical computer science\, additive combinatorics\, and several othe
 r areas. When the domain D is equipped with an algebraic structure\, parti
 cularly that of a finite Abelian group\, Boolean-valued functions become e
 specially important for studying algorithms and complexity. Such settings 
 allow us to investigate the Fourier analysis of Boolean functions\, examin
 e the structure of their Fourier spectra\, and understand the behavior of 
 their Fourier coefficients.Most prior work has focused on the case D=Z_2^n
 \, the space of binary strings of length n. A natural question is whether 
 these results extend to Boolean-valued functions defined over arbitrary fi
 nite Abelian groups. This talk will address several problems that we have 
 generalized to this broader setting.Granularity: The Fourier sparsity s_f 
 of f is the number of nonzero Fourier coefficients. When s_f is small\, wh
 at can be said about the magnitude of the Fourier coefficients? Gopalan et
  al. (2011) showed that for Boolean functions on Z_2^n\, every nonzero Fou
 rier coefficient has absolute value at least 1/s_f.Upper bounds on Fourier
  dimension: The Fourier dimension r_f is the dimension of the Fourier supp
 ort of f. Sanyal (2019) proved that r_f = O(\\sqrt{s_f} log s_f ). This wa
 s improved by Chakraborty et al. (2020)\, who showed that r_f = O(\\sqrt{s
 _f \\delta_f} log s_f )\, where \\delta_f = Pr_x[f(x) = −1]. These resul
 ts demonstrate that Boolean functions with small sparsity cannot have arbi
 trarily large Fourier dimension. Improved bounds for Chang's lemma and Coh
 en's idempotent theorem have also been obtained in the Z_2^n setting.\n \
 nPage 1 of 2.... \n \n \n \n \n \nContinued from Page 1...\nLinear I
 somorphism Testing: The linear isomorphism testing problem for Boolean fun
 ctions over Z_2^n is also an important area of study. For A \\in Z_2^n×n\
 , let f ◦ A : Z_2^n → {−1\, 1} be the function f ◦A(x) = f(Ax) fo
 r all x ∈ Z_2^n. The Linear Isomorphism Distance between f : Z_2^n → 
 {−1\, 1} and g : Z_2^n → {−1\, 1} is defined as dist_{Z_2^n}(f\, g)
  = min_{A\\in Z_2^{n×n}: A is non-singular} \\delta(f ◦A\, g). Assume t
 hat f and g satisfy the promise that either dist_{Z_2^n}(f\, g)=0 or dist_
 {Z_2^n}(f\, g) \\geq \\epsilon\, the question of Linear Isomorphism testin
 g is that of deciding which is the case. \n \nAdditional investigations 
 include the approximate degree of Boolean functions\, the Fourier–Entrop
 y Influence (FEI) conjecture\, and related topics. A key challenge in exte
 nding results from Z_2^n to arbitrary finite Abelian groups is that genera
 l Abelian groups are not vector spaces\, and their Fourier coefficients ar
 e complex numbers. Consequently\, many structural properties used in the Z
 _2^n setting break down\, making such generalizations nontrivial. The talk
  will highlight these challenges and discuss the main obstacles to develop
 ing analogous results over finite Abelian groups.\n \nThe talk is based o
 n the following works:\n(1) On Fourier analysis of sparse Boolean functio
 ns over certain Abelian groups [Chakraborty\, Datta\, Dutta\, Ghosh\, San
 yal]\, MFCS 2024\n(2) Testing Isomorphism of Boolean Functions over Fini
 te Abelian Groups [Datta\, Ghosh\, Kayal\, Paraashar\, Roy]\, RANDOM 2025
 \n(3) Structure of Sparse Boolean Functions over Abelian Groups\, and its
  Application to Testing [Chakraborty\, Datta\, Dutta\, Ghosh\, Sanyal]\n(
 4) No Vector Space? No Problem: Lifting Boolean Function Results to Abeli
 an Groups [Chakraborty\, Datta\, Ghosh\, Sanyal]\nShort Bio:I am a Senior
  Research Fellow in computer science\, currently working at the Indian Sta
 tistical Institute\, Kolkata under the supervision of Dr. Sourav Chakrabor
 ty and Dr. Arijit Ghosh\, on Fourier analysis of Boolean functions. I have
  done my bachelors and masters from St. Xavier's college\, Kolkata and Ind
 ian Institute of Science\, Bangalore respectively\, in mathematics.\n \n
  \n \n \n \n \n \n \n \n \n \n \n \nPage 2 of 2.\n
URL:https://www.tcs.tifr.res.in/web/events/1622
DTSTART;TZID=Asia/Kolkata:20251211T160000
DTEND;TZID=Asia/Kolkata:20251211T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR