Analysis of Boolean functions

<p>In <a href="/facts/Mathematics/pxTouaz4">mathematics</a> and <a href="/facts/Theoretical_computer_science/jSkGGuvy">theoretical computer science</a>, analysis of Boolean functions is the study of real-valued functions on 
  
    
      
        {
        0
        ,
        1
        
          }
          
            n
          
        
      
    
    {\displaystyle \{0,1\}^{n}}
  
 or 
  
    
      
        {
        −
        1
        ,
        1
        
          }
          
            n
          
        
      
    
    {\displaystyle \{-1,1\}^{n}}
  
 (such functions are sometimes known as <a href="/facts/Pseudo-Boolean_function/U0zWqAL8">pseudo-Boolean functions</a>) from a spectral perspective. The functions studied are often, but not always, Boolean-valued, making them <a href="/facts/Boolean_function/uT7E8pqC">Boolean functions</a>. The area has found many applications in <a href="/facts/Combinatorics/k14xUoKT">combinatorics</a>, <a href="/facts/Social_choice_theory/ztMqy1bM">social choice theory</a>, <a href="/facts/Random_graph/gfQhq1Sz">random graphs</a>, and theoretical computer science, especially in <a href="/facts/Hardness_of_approximation/YNKqhcej">hardness of approximation</a>, <a href="/facts/Property_testing/Upgej2So">property testing</a>, and <a href="/facts/Probably_approximately_correct_learning/vBQlvDV1">PAC learning</a>.
</p>

Analysis of Boolean functions open-in-new

Analysis of Boolean functions