Relations between monotone complexity measures based on decision tree complexity
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 with AND function as the inner gadget. One of the main tools in this result was the relationship between monotone analogue...
Bewaard in:
| Hoofdauteurs: | , , , |
|---|---|
| Formaat: | Artikel |
| Gepubliceerd in: |
2024
|
| Onderwerpen: | |
| Online toegang: | https://arxiv.org/abs/2406.07859 http://arxiv.org/abs/2406.07859 |
| Tags: |
Geen labels, Wees de eerste die dit record labelt!
|