On separation between the degree of a Boolean function and the block sensitivity

DOI10.1007/978-3-030-79416-3_25MaRDI QIDQ2117108zbMATH OpenOpenAlexFDO

Authors N. V. Proskurin

Publication date 21 March 2022

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

zbMATH Keywords

approximate degreeblock sensitivitydegree of a Boolean function

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Comparison of Uniform Approximations on an Interval and a Finite Subset Thereof
• Automata, Languages and Programming
• Boolean function complexity. Advances and frontiers.
• Complexity measures and decision tree complexity: a survey.
• scientific article; zbMATH DE number 826245 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• Induced subgraphs of hypercubes and a proof of the sensitivity conjecture
• On the degree of Boolean functions as real polynomials
• Perceptrons, PP, and the polynomial hierarchy
• Polynomials with two values
• Properties and applications of Boolean function composition
• Schwankung von Polynomen zwischen Gitterpunkten. (Oscillations of polynomials between lattice points)

This page was built for publication: On separation between the degree of a Boolean function and the block sensitivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2117108)