Smooth Boolean Functions are Easy
From MaRDI portal
Publication:2800553
DOI10.1145/2840728.2840738zbMath1334.68068arXiv1508.02420OpenAlexW1900614497MaRDI QIDQ2800553
Avi Wigderson, Parikshit Gopalan, Noam Nisan, Kunal Talwar, Rocco A. Servedio
Publication date: 15 April 2016
Published in: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1508.02420
Related Items
Low-Sensitivity Functions from Unambiguous Certificates. ⋮ Unnamed Item ⋮ Sensitivity Versus Certificate Complexity of Boolean Functions ⋮ A tighter relation between sensitivity complexity and certificate complexity ⋮ Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
