An upper bound for the relative influence of variables on Boolean functions

DOI10.1134/S0001434617010175MaRDI QIDQ2396403zbMATH OpenOpenAlexFDO

Authors Ivan V. Gribushin

Publication date 8 June 2017

Published in Mathematical Notes (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0001434617010175

zbMATH Keywords

threshold function{\(\tau\)}-regular Boolean functioninfluence of variables on a Boolean function

Mathematics Subject Classification ID

Boolean functions (06E30)

Recommendations

• Variable Influences in Conjunctive Normal Forms
• The influence of variables in product spaces
• On the influences of variables on Boolean functions in product spaces
• Half-spaces with influential variable
• Spectral properties of threshold functions

Cites work

• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• Modeling non-branching programs with conditional stopping on a universal Turing machine

Cited in

(6)

• Influence of a Set of Variables on a Boolean Function
• An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function
• Improved upper bound for the relative distance between a Boolean function and the set of \(k\)-dimensional functions
• Variable Influences in Conjunctive Normal Forms
• Symmetric approximations of pseudo-Boolean functions with applications to influence indexes
• Half-spaces with influential variable

This page was built for publication: An upper bound for the relative influence of variables on Boolean functions

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