Boolean Function Monotonicity Testing Requires (Almost) n

Xi Chen, Anindya De, Rocco A. Servedio, Li-Yang Tan

Browse the full STOC paper archive.