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 show that there is a randomized algorithm that, when given a smallconstant-depth Boolean circuit $C$ made up of gates that computeconstant-degree Polynomial Threshold functions or PTFs (i.e., Boolean functionsthat compute signs of constant-degree polynomials), counts the number ofsatisfying assignments to $C$ in significantly better than brute-force time.  Formally, for any constants $d,k$, there is an $\epsilon > 0$ such that thealgorithm counts the number of satisfying assignments to a given depth-$d$circuit $C$ made up of $k$-PTF gates such that $C$ has size at most$n^{1+\epsilon}$. The algorithm runs in time $2^{n-n^{\Omega(\epsilon)}}$.  Before our result, no algorithm for beating brute-force search was known evenfor a single degree-$2$ PTF (which is a depth-$1$ circuit of linear size).  The main new tool is the use of a learning algorithm for learning degree-$1$PTFs (or Linear Threshold Functions) using comparison queries due to Kane,Lovett, Moran and Zhang (FOCS 2017). We show that their ideas fit nicely into amemoization approach that yields the #SAT algorithms.

A #SAT Algorithm for Small Constant-Depth Circuits with PTF gates