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 consider the class \( \sum^{k}_{3} \) of unbounded fan-in depth three Boolean circuits, for which the bottom fan-in is limited by k and the top gate is an OR. It is known that the smallest such circuit computing the parity function has \( \Omega(2^{\varepsilon n/k}) \) gates (for k = O(n1/2)) for some \( \varepsilon > 0 \), and this was the best lower bound known for explicit (P-time computable) functions. In this paper, for k = 2, we exhibit functions in uniform NC1 that require \( 2^{n-o(n)} \) size depth 3 circuits. The main tool is a theorem that shows that any \( \sum {2\over3} \) circuit on n variables that accepts a inputs and has size s must be constant on a projection (subset defined by equations of the form xi = 0, xi = 1, xi = xj or xi = \( \bar{x}_i \)) of dimension at least log(a/s)log n.

Exponential lower bounds for depth 3 Boolean circuits