Information theory and the complexity of boolean functions

DOI10.1007/BF01683269zbMath0364.94031MaRDI QIDQ4141101

Nicholas J. Pippenger

Publication date: 1977

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

Mathematics Subject Classification ID

Related Items (7)

Quantum query complexity of almost all functions with fixed on-set size ⋮ Random problems ⋮ Optimal bounds for the approximation of Boolean functions and some applications ⋮ On the Complexity of Breaking Pseudoentropy ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Systematic mistakes are likely in bounded optimal decision-making systems

Cites Work

• Unnamed Item
• A Mathematical Theory of Communication
• On the complexity of inexact computations
• Two combinatorial covering theorems
• Fast multiplication of large numbers

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