A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity

DOI10.1007/978-3-662-44465-8_4zbMath1426.68110arXiv1402.5078OpenAlexW1591655681MaRDI QIDQ2922593

Krišjānis Prūsis, Andris Ambainis

Publication date: 14 October 2014

Published in: Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1402.5078

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (3)

Low-Sensitivity Functions from Unambiguous Certificates. ⋮ A tighter relation between sensitivity complexity and certificate complexity ⋮ New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

This page was built for publication: A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity