201 citations · 235 across the 24 of their papers we have counts for
5 papers · 1 filter
Algorithmic regularity for polynomials and applications
Arnab Bhattacharyya, Pooya Hatami, Madhur Tulsiani
In analogy with the regularity lemma of Szemerédi, regularity lemmas for polynomials shown by Green and Tao (Contrib. Discrete Math. 2009) and by Kaufman and Lovett (FOCS 2008) mod…
Limits of Boolean Functions on F_p^n
Hamed Hatami, Pooya Hatami, James Hirst
We study sequences of functions of the form F_p^n -> {0,1} for varying n, and define a notion of convergence based on the induced distributions from restricting the functions to a…
Distance-Sensitive Property Testing Lower Bounds
Joshua Brody, Pooya Hatami
In this paper, we consider several property testing problems and ask how the query complexity depends on the distance parameter $\eps$. We achieve new lower bounds in this setting…
An Arithmetic Analogue of Fox's Triangle Removal Argument
Pooya Hatami, Sushant Sachdeva, Madhur Tulsiani
We give an arithmetic version of the recent proof of the triangle removal lemma by Fox [Fox11], for the group . A triangle in is a triple …
Every locally characterized affine-invariant property is testable
Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami +2
Let F = F_p for any fixed prime p >= 2. An affine-invariant property is a property of functions on F^n that is closed under taking affine transformations of the domain. We prove th…