Relations between monotone complexity measures based on decision tree complexity

Farzan Byramji, Vatsal Jha, Chandrima Kayal +1

In a recent result, Knop, Lovett, McGuire and Yuan (STOC 2021) proved the log-rank conjecture for communication complexity, up to log n factor, for any Boolean function composed wi…