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

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

$ \newcommand{\cclass}[1]{{\normalfont\textsf{##1}}} $We show average-caselower bounds for explicit Boolean functions against bounded-depth thresholdcircuits with a superlinear number of wires. We show that for each integer $d >1$, there is a constant $\varepsilon_d > 0$ such that the Parity function on$n$ bits has correlation at most $n^{-\varepsilon_d}$ with depth-$d$ thresholdcircuits which have at most $n^{1+\varepsilon_d}$ wires, and the GeneralizedAndreev function on $n$ bits has correlation at most$\exp(-{n^{\varepsilon_d}})$ with depth-$d$ threshold circuits which have atmost $n^{1+\varepsilon_d}$ wires. Previously, only worst-case lower bounds inthis setting were known (Impagliazzo, Paturi, and Saks (SICOMP 1997)).  We use our ideas to make progress on several related questions. We givesatisfiability algorithms beating brute force search for depth-$d$ thresholdcircuits with a superlinear number of wires. These are the first suchalgorithms for depth greater than 2. We also show that Parity on $n$ bitscannot be computed by polynomial-size $\textsf{AC}^0$ circuits with $n^{o(1)}$general threshold gates. Previously no lower bound for Parity in this settingcould handle more than $\log(n)$ gates. This result also impliessubexponential-time learning algorithms for $\textsf{AC}^0$ with $n^{o(1)}$threshold gates under the uniform distribution. In addition, we give almostoptimal bounds for the number of gates in a depth-$d$ threshold circuitcomputing Parity on average, and show average-case lower bounds for thresholdformulas of any depth.  Our techniques include adaptive random restrictions, anti-concentration andthe structural theory of linear threshold functions, and bounded-read Chernoffbounds.

Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits