Log-rank conjecture
In theoretical computer science, the log-rank conjecture states that the deterministic communication complexity of a two-party Boolean function is polynomially related to the logarithm of the rank of its input matrix.Let 
  
    
      
        D
        (
        f
        )
      
    
    {\displaystyle D(f)}
   denote the deterministic communication complexity of a function, and let 
  
    
      
        rank
        ⁡
        (
        f
        )
      
    
    {\displaystyle \operatorname {rank} (f)}
   denote the rank of its input matrix 
  
    
      
        
          M
          
            f
          
        
      
    
    {\displaystyle M_{f}}
   (over the reals). Since every protocol using up to 
  
    
      
        c
      
    
    {\displaystyle c}
   bits partitions 
  
    
      
        
          M
          
            f
          
        
      
    
    {\displaystyle M_{f}}
   into at most 
  
    
      
        
          2
          
            c
          
        
      
    
    {\displaystyle 2^{c}}
   monochromatic rectangles, and each of these has rank at most 1,

  
    
      
        D
        (
        f
        )
        ≥
        
          log
          
            2
          
        
        ⁡
        rank
        ⁡
        (
        f
        )
        . {\displaystyle D(f)\geq \log _{2}\operatorname {rank} (f).} The log-rank conjecture states that 
  
    
      
        D
        (
        f
        )
      
    
    {\displaystyle D(f)}
   is also upper-bounded by a polynomial in the log-rank: for some constant 
  
    
      
        C
      
    
    {\displaystyle C}
  ,

  
    
      
        D
        (
        f
        )
        =
        O
        (
        (
        log
        ⁡
        rank
        ⁡
        (
        f
        )
        
          )
          
            C
          
        
        )
        . {\displaystyle D(f)=O((\log \operatorname {rank} (f))^{C}).}