English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We give improved separations for the query complexity analogue of thelog-approximate-rank conjecture i.e. we show that there are a plethora of totalBoolean functions on $n$ input bits, each of which has approximate Fouriersparsity at most $O(n^3)$ and randomized parity decision tree complexity$\Theta(n)$. This improves upon the recent work of Chattopadhyay, Mande andSherif (JACM '20) both qualitatively (in terms of designing a large number ofexamples) and quantitatively (improving the gap from quartic to cubic). Weleave open the problem of proving a randomized communication complexity lowerbound for XOR compositions of our examples. A linear lower bound would lead tonew and improved refutations of the log-approximate-rank conjecture. Moreover,if any of these compositions had even a sub-linear cost randomizedcommunication protocol, it would demonstrate that randomized parity decisiontree complexity does not lift to randomized communication complexity in general(with the XOR gadget).

Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture