Low-depth arithmetic circuit lower bounds: bypassing set-multilinearization

DOI10.4230/LIPICS.ICALP.2023.12MaRDI QIDQ6638003zbMATH OpenFDO

Authors Prashanth Amireddy, Ankit Garg, Neeraj Kayal, Chandan Saha, Bhargav Thankey

Publication date 14 November 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2023.12

zbMATH Keywords

arithmetic circuitslow-depth circuitslower boundsshifted partials

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cited in

(4)

• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• Low-depth algebraic circuit lower bounds over any field
• NP-hardness of testing equivalence to sparse polynomials and to constant-support polynomials
• Monotone bounded-depth complexity of homomorphism polynomials

This page was built for publication: Low-depth arithmetic circuit lower bounds: bypassing set-multilinearization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6638003)