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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We prove a lower bound of Î©(n1/3) for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function f:{0,1}nâ {0,1} is monotone versus far from monotone. This improves the recent lower bound of Î©(n1/4) for the same problem by Belovs and Blais (STOCâ16). Our result builds on a new family of random Boolean functions that can be viewed as a two-level extension of Talagrandâs random DNFs. Beyond monotonicity we prove a lower bound of Î©(ân) for two-sided, adaptive algorithms and a lower bound of Î©(n) for one-sided, non-adaptive algorithms for testing unateness, a natural generalization of monotonicity. The latter matches the linear upper bounds by Khot and Shinkar (RANDOMâ16) and by Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova, and Seshadhri (2017).

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness