NDLI: The Proof Complexity of Polynomial Identities

Content Provider	IEEE Xplore Digital Library
Author	Hrubes, P. Tzameret, I.
Copyright Year	2009
Abstract	Devising an efficient deterministic -- or even a non-deterministic sub-exponential time -- algorithm for testing polynomial identities is a fundamental problem in algebraic complexity and complexity at large. Motivated by this problem, as well as by results from proof complexity, we investigate the complexity of _proving_ polynomial identities. To this end, we study a class of equational proof systems, of varying strength, operating with polynomial identities written as arithmetic formulas over a given ring. A proof in these systems establishes that two arithmetic formulas compute the same polynomial, and consists of a sequence of equations between polynomials, written as arithmetic formulas, where each equation in the sequence is derived from previous equations by means of the polynomial-ring axioms. We establish the first non-trivial upper and lower bounds on the size of equational proofs of polynomial identities, as follows: 1. Polynomial-size upper bounds on equational proofs of identities involving symmetric polynomials and interpolation-based identities. In particular, we show that basic properties of the elementary symmetric polynomials are efficiently provable already in equational proofs operating with depth-4 formulas, over infinite fields. This also yields polynomial-size depth-4 proofs of the Newton identities, providing a positive answer to a question posed by Grigoriev and Hirsch [GH03]. 2. Exponential-size lower bounds on (full, unrestricted) equational proofs of identities over certain specific rings. 3. Exponential-size lower bounds on analytic proofs operating with depth-3 formulas, under a certain regularity condition. The ``analytic'' requirement is, roughly, a condition that forbids introducing arbitrary formulas in a proof and the regularity condition is an additional structural restriction. 4. Exponential-size lower bounds on one-way proofs (of unrestricted depth) over infinite fields. Here, one-way proofs are analytic proofs, in which one is also not allowed to introduce arbitrary constants. Furthermore, we determine basic structural characterizations of equational proofs, and consider relations with polynomial identity testing procedures. Specifically, we show that equational proofs efficiently simulate the polynomial identity testing algorithm provided by Dvir and Shpilka [DS04].
Starting Page	41
Ending Page	51
File Size	382763
Page Count	11
File Format	PDF
ISBN	9780769537177
ISSN	10930159
DOI	10.1109/CCC.2009.9
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-07-15
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Polynomials Equations Arithmetic Testing Computational complexity Mathematics USA Councils Upper bound Algebra Geometry symmetric polynomials Proof complexity polynomial identity testing arithmetic circuits equational systems lower bounds
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Libarray of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

An Almost Optimal Rank Bound for Depth-3 Identities

Polynomial identity testing for depth 3 circuits

Fixed-Polynomial Size Circuit Bounds

The proof complexity of polynomial identities (preliminary full version).

Recent Progress on Lower Bounds for Arithmetic Circuits

Marginal hitting sets imply super-polynomial lower bounds for permanent

Complexity Lower Bounds through Balanced Graph Properties

Tensor Rank: Some Lower and Upper Bounds

Arithmetic Circuits: A Chasm at Depth Four

The Proof Complexity of Polynomial Identities

Similar Documents

An Almost Optimal Rank Bound for Depth-3 Identities

Polynomial identity testing for depth 3 circuits

Fixed-Polynomial Size Circuit Bounds

The proof complexity of polynomial identities (preliminary full version).

Recent Progress on Lower Bounds for Arithmetic Circuits

Marginal hitting sets imply super-polynomial lower bounds for permanent

Complexity Lower Bounds through Balanced Graph Properties

Tensor Rank: Some Lower and Upper Bounds

Arithmetic Circuits: A Chasm at Depth Four

The Proof Complexity of Polynomial Identities