Information theory and the complexity of boolean functions

DOI10.1007/BF01683269MaRDI QIDQ4141101zbMATH OpenFDO

Authors Nicholas Pippenger

Publication date 1977

Published in Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01683269

Mathematics Subject Classification ID

Information theory (general) (94A15)

Cites work

• A Mathematical Theory of Communication
• Fast multiplication of large numbers
• scientific article; zbMATH DE number 3172224 (Why is no real title available?)
• On the complexity of inexact computations
• Two combinatorial covering theorems

Cited in

(7)

• Random problems
• Optimal bounds for the approximation of Boolean functions and some applications
• Systematic mistakes are likely in bounded optimal decision-making systems
• On the Complexity of Breaking Pseudoentropy
• Quantum query complexity of almost all functions with fixed on-set size
• \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem
• scientific article; zbMATH DE number 7561759 (Why is no real title available?)

This page was built for publication: Information theory and the complexity of boolean functions

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