Manmatha Roy

2 accepted papers

2026

Implicit Sensing for Fourier Sparse Boolean Functions

Arijit Ghosh, Subhamoy Maitra, Manmatha Roy

ICLR 2026poster

Boolean functions constitute a fundamental object of study in machine learning and, more broadly, in theoretical computer science. Among their various complexity measures, Fourier sparsity, defined as the number of nonzero Fourier coefficients in a Boolean function’s Fourier expansion, serves as a k…

Cited by 0 Source ↗Scholar ↗

2025

Price of Parsimony: Complexity of Fourier Sparsity Testing

Arijit Ghosh, Manmatha Roy

NeurIPS 2025poster

A function \( f : \mathbb{F}_2^n \to \mathbb{R} \) is said to be \( s \)-Fourier sparse if its Fourier expansion contains at most \( s \) nonzero coefficients. In general, the existence of a sparse representation in the Fourier basis serves as a key enabler for the design of efficient learning algor…

Cited by 0 Source ↗Scholar ↗