Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma

DOI10.1007/978-3-319-17142-5_12zbMath1352.05180arXiv1406.0073OpenAlexW3101072755MaRDI QIDQ2948459

Jevgēnijs Vihrovs, Andris Ambainis

Publication date: 30 September 2015

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

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

Mathematics Subject Classification ID

Extremal set theory (05D05)

Related Items (5)

Low-Sensitivity Functions from Unambiguous Certificates. ⋮ Sensitivity Versus Certificate Complexity of Boolean Functions ⋮ A tighter relation between sensitivity complexity and certificate complexity ⋮ Tight bounds on sensitivity and block sensitivity of some classes of transitive functions ⋮ Does Looking Inside a Circuit Help

Cites Work

• Unnamed Item
• On the degree of Boolean functions as real polynomials
• 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
• Boolean functions with small spectral norm
• CREW PRAM<scp>s</scp> and Decision Trees
• 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: Size of Sets with Small Sensitivity: A Generalization of Simon’s Lemma