Simple hard instances for low-depth algebraic proofs
File(s)cdIPS-lowerbounds.pdf (1 MB)
Submitted version
Author(s)
Govindasamy, Nashlen
Hakoniemi, Tuomas
Tzameret, Iddo
Type
Conference Paper
Abstract
We prove super-polynomial lower bounds on the size of propositional proof systems operating with constant-depth algebraic circuits over fields of zero characteristic. Specifically, we show that the subset-sum variant ∑i,j,k,ℓ∈[n]Zi′Jkℓxixjxkxℓ−β=0, for Boolean variables, does not have polynomial-size IPS refutations where the refutations are multilinear and written as constant-depth circuits. Andrews and Forbes (STOC’22) established recently a constant-depth IPS lower bound, but their hard instance does not have itself small constant-depth circuits, while our instance is computable already with small depth-2 circuits. Our argument relies on extending the recent breakthrough lower bounds against constant-depth algebraic circuits by Limaye, Srinivasan and Tavenas (FOCS’21) to the functional lower bound framework of Forbes, Shpilka, Tzameret and Wigderson (ToC’21), and may be of independent interest. Specifically, we construct a polynomial f computable with small-size constant-depth circuits, such that the multilinear polynomial computing 1/f over Boolean values and its appropriate set-multilinear projection are hard for constant-depth circuits.
Date Issued
2022-12-02
Date Acceptance
2022-10-01
Citation
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), 2022, pp.188-199
ISSN
0272-5428
Publisher
IEEE Computer Society
Start Page
188
End Page
199
Journal / Book Title
2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
Copyright Statement
Copyright © 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.
Identifier
https://www.webofscience.com/api/gateway?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000909382900018&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=a2bf6146997ec60c407a63945d4e92bb
Source
63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS)
Subjects
algebraic circuit complexity
algebraic proof systems
ARITHMETIC CIRCUITS
Computer Science
Computer Science, Theory & Methods
constant depth
IPS
lower bounds
LOWER BOUNDS
Mathematics
Mathematics, Applied
NULLSTELLENSATZ
Physical Sciences
POLYNOMIAL CALCULUS
Proof complexity
Science & Technology
SYSTEMS
Technology
Publication Status
Published
Start Date
2022-10-31
Finish Date
2022-11-03
Coverage Spatial
CO, Denver