Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > ALGEBRAIC CIRCUIT COMPLEXITY:
Reports tagged with algebraic circuit complexity:
TR14-052 | 14th April 2014
Joshua Grochow, Toniann Pitassi

Circuit complexity, proof complexity, and polynomial identity testing

We introduce a new and very natural algebraic proof system, which has tight connections to (algebraic) circuit complexity. In particular, we show that any super-polynomial lower bound on any Boolean tautology in our proof system implies that the permanent does not have polynomial-size algebraic circuits ($VNP \neq VP$). As a ... more >>>


TR17-007 | 19th January 2017
Michael Forbes, Amir Shpilka, Ben Lee Volk

Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds

Revisions: 1

We formalize a framework of algebraically natural lower bounds for algebraic circuits. Just as with the natural proofs notion of Razborov and Rudich for boolean circuit lower bounds, our notion of algebraically natural lower bounds captures nearly all lower bound techniques known. However, unlike the boolean setting, there has been ... more >>>


TR17-009 | 19th January 2017
Joshua Grochow, Mrinal Kumar, Michael Saks, Shubhangi Saraf

Towards an algebraic natural proofs barrier via polynomial identity testing

We observe that a certain kind of algebraic proof - which covers essentially all known algebraic circuit lower bounds to date - cannot be used to prove lower bounds against VP if and only if what we call succinct hitting sets exist for VP. This is analogous to the Razborov-Rudich ... more >>>


TR18-135 | 31st July 2018
Prasad Chaugule, Nutan Limaye, Aditya Varre

Variants of Homomorphism Polynomials Complete for Algebraic Complexity Classes

Revisions: 1

We present polynomial families complete for the well-studied algebraic complexity classes VF, VBP, VP, and VNP. The polynomial families are based on the homomorphism polynomials studied in the recent works of Durand et al. (2014) and Mahajan et al. (2016). We consider three different variants of graph homomorphisms, namely injective ... more >>>


TR18-184 | 5th November 2018
Iddo Tzameret, Stephen Cook

Uniform, Integral and Feasible Proofs for the Determinant Identities

Revisions: 1

Aiming to provide weak as possible axiomatic assumptions in which one can develop basic linear algebra, we give a uniform and integral version of the short propositional proofs for the determinant identities demonstrated over $GF(2)$ in Hrubes-Tzameret [SICOMP'15]. Specifically, we show that the multiplicativity of the determinant function and the ... more >>>


TR19-142 | 23rd October 2019
Yaroslav Alekseev, Dima Grigoriev, Edward Hirsch, Iddo Tzameret

Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?

Revisions: 1

We introduce the `binary value principle' which is a simple subset-sum instance expressing that a natural number written in binary cannot be negative, relating it to central problems in proof and algebraic complexity. We prove conditional superpolynomial lower bounds on the Ideal Proof System (IPS) refutation size of this instance, ... more >>>


TR20-189 | 24th December 2020
Pavel Hrubes, Amir Yehudayoff

Shadows of Newton polytopes

We define the shadow complexity of a polytope P as the maximum number of vertices in a linear projection of $P$ to the plane. We describe connections to algebraic complexity and to parametrized optimization. We also provide several basic examples and constructions, and develop tools for bounding shadow complexity.

more >>>

TR21-037 | 1st March 2021
Prerona Chatterjee

Separating ABPs and Some Structured Formulas in the Non-Commutative Setting

The motivating question for this work is a long standing open problem, posed by Nisan (1991), regarding the relative powers of algebraic branching programs (ABPs) and formulas in the non-commutative setting. Even though the general question continues to remain open, we make some progress towards its resolution. To that effect, ... more >>>


TR21-138 | 23rd September 2021
Rahul Santhanam, Iddo Tzameret

Iterated Lower Bound Formulas: A Diagonalization-Based Approach to Proof Complexity

We propose a diagonalization-based approach to several important questions in proof complexity. We illustrate this approach in the context of the algebraic proof system IPS and in the context of propositional proof systems more generally.

We give an explicit sequence of CNF formulas $\{\phi_n\}$ such that VNP$\neq$VP iff there are ... more >>>


TR22-055 | 23rd April 2022
Nashlen Govindasamy, Tuomas Hakoniemi, Iddo Tzameret

Simple Hard Instances for Low-Depth Algebraic Proofs

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 $\sum_{i,j,k,l\in[n]} z_{ijkl}x_ix_jx_kx_l-\beta = 0$, for Boolean variables, does not have polynomial-size IPS refutations where the refutations are multilinear and written as ... more >>>


TR22-064 | 2nd May 2022
Deepanshu Kush, Shubhangi Saraf

Improved Low-Depth Set-Multilinear Circuit Lower Bounds

In this paper, we prove strengthened lower bounds for constant-depth set-multilinear formulas. More precisely, we show that over any field, there is an explicit polynomial $f$ in VNP defined over $n^2$ variables, and of degree $n$, such that any product-depth $\Delta$ set-multilinear formula computing $f$ has size at least $n^{\Omega ... more >>>


TR22-071 | 13th May 2022
Arkadev Chattopadhyay, Utsab Ghosal, Partha Mukhopadhyay

Robustly Separating the Arithmetic Monotone Hierarchy Via Graph Inner-Product

We establish an $\epsilon$-sensitive hierarchy separation for monotone arithmetic computations. The notion of $\epsilon$-sensitive monotone lower bounds was recently introduced by Hrubes [Computational Complexity'20]. We show the following:

(1) There exists a monotone polynomial over $n$ variables in VNP that cannot be computed by $2^{o(n)}$ size monotone ... more >>>


TR24-079 | 20th April 2024
Tuomas Hakoniemi , Nutan Limaye, Iddo Tzameret

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers

Strong algebraic proof systems such as IPS (Ideal Proof System; Grochow-Pitassi JACM 2018) offer a general model for
deriving polynomials in an ideal and refuting unsatisfiable propositional formulas, subsuming most standard propositional proof systems. A major approach for lower bounding the size of IPS refutations is the Functional Lower Bound ... more >>>




ISSN 1433-8092 | Imprint