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 a $2^{\tilde{O}(\sqrt{n}/\epsilon)}$-time algorithm for properlylearning monotone Boolean functions under the uniform distribution over$\{0,1\}^n$. Our algorithm is robust to adversarial label noise and has arunning time nearly matching that of the state-of-the-art improper learningalgorithm of Bshouty and Tamon (JACM '96) and an information-theoretic lowerbound of Blais et al (RANDOM '15). Prior to this work, no proper learningalgorithm with running time smaller than $2^{\Omega(n)}$ was known to exist.  The core of our proper learner is a \emph{local computation algorithm} forsorting binary labels on a poset. Our algorithm is built on a body of work ondistributed greedy graph algorithms; specifically we rely on a recent work ofGhaffari (FOCS'22), which gives an efficient algorithm for computing maximalmatchings in a graph in the LCA model of Rubinfeld et al and Alon et al(ICS'11, SODA'12). The applications of our local sorting algorithm extendbeyond learning on the Boolean cube: we also give a tolerant tester for Booleanfunctions over general posets that distinguishes functions that are$\epsilon/3$-close to monotone from those that are $\epsilon$-far.  Previous tolerant testers for the Boolean cube only distinguished between$\epsilon/\Omega(\sqrt{n})$-close and $\epsilon$-far.

Properly learning monotone functions via local reconstruction