Sensitivity Versus Certificate Complexity of Boolean Functions

DOI10.1007/978-3-319-34171-2_2zbMath1475.68135arXiv1503.07691OpenAlexW1576228534MaRDI QIDQ5740174

Jevgēnijs Vihrovs, Krišjānis Prūsis, Andris Ambainis

Publication date: 25 July 2016

Published in: Computer Science – Theory and Applications (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Boolean functions (06E30)

Related Items (7)

Alternation, sparsity and sensitivity: bounds and exponential gaps ⋮ Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma ⋮ Sensitivity Versus Certificate Complexity of Boolean Functions ⋮ A tighter relation between sensitivity complexity and certificate complexity ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms ⋮ New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity ⋮ Rainbow Coloring Hardness via Low Sensitivity Polymorphisms

Cites Work

• Unnamed Item
• Complexity measures and decision tree complexity: a survey.
• Sensitivity, block sensitivity, and \(\ell\)-block sensitivity of Boolean functions
• Sensitivity vs. block sensitivity of Boolean functions
• Sensitivity versus block sensitivity of Boolean functions
• Smooth Boolean Functions are Easy
• Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Tighter Relations between Sensitivity and Other Complexity Measures
• Quantum lower bounds by polynomials
• Sensitivity Versus Certificate Complexity of Boolean Functions

This page was built for publication: Sensitivity Versus Certificate Complexity of Boolean Functions