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 present a single, common tool to strictly subsume all known cases ofpolynomial time blackbox polynomial identity testing (PIT) that have beenhitherto solved using diverse tools and techniques. In particular, we show thatpolynomial time hitting-set generators for identity testing of the twoseemingly different and well studied models - depth-3 circuits with bounded topfanin, and constant-depth constant-read multilinear formulas - can beconstructed using one common algebraic-geometry theme: Jacobian capturesalgebraic independence. By exploiting the Jacobian, we design the firstefficient hitting-set generators for broad generalizations of theabove-mentioned models, namely:  (1) depth-3 (Sigma-Pi-Sigma) circuits with constant transcendence degree ofthe polynomials computed by the product gates (no bounded top faninrestriction), and (2) constant-depth constant-occur formulas (no multilinearrestriction).  Constant-occur of a variable, as we define it, is a much more general conceptthan constant-read. Also, earlier work on the latter model assumed that theformula is multilinear. Thus, our work goes further beyond the results obtainedby Saxena & Seshadhri (STOC 2011), Saraf & Volkovich (STOC 2011), Anderson etal. (CCC 2011), Beecken et al. (ICALP 2011) and Grenet et al. (FSTTCS 2011),and brings them under one unifying technique.  In addition, using the same Jacobian based approach, we prove exponentiallower bounds for the immanant (which includes permanent and determinant) on thesame depth-3 and depth-4 models for which we give efficient PIT algorithms. Ourresults reinforce the intimate connection between identity testing and lowerbounds by exhibiting a concrete mathematical tool - the Jacobian - that isequally effective in solving both the problems on certain interesting andpreviously well-investigated (but not well understood) models of computation.

Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits