Tighter Relations between Sensitivity and Other Complexity Measures

DOI10.1007/978-3-662-43948-7_9zbMath1410.68150arXiv1411.3419OpenAlexW2139540988MaRDI QIDQ5167734

Xiaoming Sun, Yihan Gao, Mohammad Bavarian, Jieming Mao, Song Zuo, Andris Ambainis

Publication date: 1 July 2014

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Related Items (9)

Low-Sensitivity Functions from Unambiguous Certificates. ⋮ Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma ⋮ Unnamed Item ⋮ Conflict complexity is lower bounded by block sensitivity ⋮ Sensitivity Versus Certificate Complexity of Boolean Functions ⋮ A tighter relation between sensitivity complexity and certificate complexity ⋮ On the modulo degree complexity of Boolean functions ⋮ Tight bounds on sensitivity and block sensitivity of some classes of transitive functions ⋮ New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

This page was built for publication: Tighter Relations between Sensitivity and Other Complexity Measures