2012/02/16 by Pooya Hatami, Hatami, Pooya
Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1202.3479
openalex publication_date 2012/02/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of testing whether a Boolean function has Fourier degree ≤ k or it is ε-far from any Boolean function with Fourier degree ≤ k. We improve the known lower bound of Ω(k) \citeBBM11,CGM10, to Ω(k/√ε). The lower bound uses the recently discovered connections between property testing and communication complexity by Blais et. al. \citeBBM11