BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1792
DTSTAMP:20261021T084129Z
SUMMARY:Explicit Nonlinear Functions beyond the Fourier bound
DESCRIPTION:Speaker: Shanthanu  Suresh Rai (TIFR)\n\nAbstract: \nIn this ta
 lk\, we will look at the problem of constructing highly nonlinear vectoria
 l maps $F: F_2^n \\to F_2^m$. Concretely\, we want an $F$ and an $A = A(m\
 ,n) > 0$ as small as possible\, so that for every affine map $L : F_2^n \\
 to F_2^m$ (of the form $L(x)=Mx+b$) we have:\n\\[ agree(F\, L) := | {x \\i
 n F_2^n | F(x) = L(x)} | ≤ A. \\]\nSuch questions have been studied by N
 yberg (1991\,1993)\, Carlet and Ding (2004\,2007)\, Liu\, Mesnager and Che
 n (2017)\, Nagy (2025)\, and Biryukov\, Turecek\, and Udovenko (2026).Ther
 e is a classical method of constructing such functions from bent-functions
  and Fourier analytic ideas\; the best bound achievable by this method is:
  \n\\[ A(m\,n) = \\Theta( 2^{n−m} + 2^{n/2} )\, \\]\nand in particular\
 , is never smaller than 2^{n/2}.\nIn the talk\, we will see how to constru
 ct highly nonlinear functions beyond this Fourier bound. Concretely\, we w
 ill see how to construct for every $\\gamma > 0$\, a function $F : F^n_2 \
 \to F^m_2$ with $m = O_\\gamma(n)$\, achieving\n\\[ A(m\,n) \\leq (1+\\gam
 ma)^n. \\]\nOur methods are based on a new connection to classical results
  on counting solutions to systems of polynomial equations via algebraic me
 thods. This connection brings us to basic questions in combinatorics\, abo
 ut graphs and hypergraphs with simultaneously a small number of edges and 
 independent sets. \nThis is joint work with Swastik Kopparty and Rishabh 
 Kothary.\nPaper link: https://arxiv.org/abs/2610.06362\n \n
URL:https://www.tcs.tifr.res.in/web/events/1792
DTSTART;TZID=Asia/Kolkata:20261023T160000
DTEND;TZID=Asia/Kolkata:20261023T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR