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 continue to study the notion of cancellation-free linear circuits. We showthat every matrix can be computed by a cancellation- free circuit, and almostall of these are at most a constant factor larger than the optimum linearcircuit that computes the matrix. It appears to be easier to prove statementsabout the structure of cancellation-free linear circuits than for linearcircuits in general. We prove two nontrivial superlinear lower bounds. We showthat a cancellation-free linear circuit computing the $n\times n$ Sierpinskigasket matrix must use at least 1/2 n logn gates, and that this is tight. Thissupports a conjecture by Aaronson. Furthermore we show that a proof strategyfor proving lower bounds on monotone circuits can be almost directly convertedto prove lower bounds on cancellation-free linear circuits. We use thistogether with a result from extremal graph theory due to Andreev to prove alower bound of {\Omega}(n^(2- \epsilon)) for infinitely many $n \times n$matrices for every $\epsilon > 0$ for. These lower bounds for concrete matricesare almost optimal since all matrices can be computed with $O(n^2/\log n)$gates.

Cancellation-free circuits: An approach for proving superlinear lower bounds for linear Boolean operators