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

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 monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We prove super-polynomial lower bounds on the size of propositional proofsystems operating with constant-depth algebraic circuits over fields of zerocharacteristic. Specifically, we show that the subset-sum variant$\sum_{i,j,k,\ell\in[n]} z_{ijk\ell}x_ix_j x_k x_\ell - \beta=0$, for Booleanvariables, does not have polynomial-size IPS refutations where the refutationsare multilinear and written as constant-depth circuits.  Andrews and Forbes (STOC'22) established recently a constant-depth IPS lowerbound, but their hard instance does not have itself small constant-depthcircuits, while our instance is computable already with small depth-2 circuits.  Our argument relies on extending the recent breakthrough lower bounds againstconstant-depth algebraic circuits by Limaye, Srinivasan and Tavenas (FOCS'21)to the functional lower bound framework of Forbes, Shpilka, Tzameret andWigderson (ToC'21), and may be of independent interest. Specifically, weconstruct a polynomial $f$ computable with small-size constant-depth circuits,such that the multilinear polynomial computing $1/f$ over Boolean values andits appropriate set-multilinear projection are hard for constant-depthcircuits.

Simple Hard Instances for Low-Depth Algebraic Proofs