A tighter relation between sensitivity complexity and certificate complexity

DOI10.1007/978-3-319-62389-4_22zbMath1434.68197OpenAlexW2728446156MaRDI QIDQ5920152

Qian Li, Kun He, Xiaoming Sun

Publication date: 23 October 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-62389-4_22

zbMATH Keywords

sensitivityBoolean functionsblock sensitivitycertificate complexitysensitivity conjecture

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30)

Related Items (1)

On the resolution of the sensitivity conjecture

This page was built for publication: A tighter relation between sensitivity complexity and certificate complexity