Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ALGEBRAIC COMPLEXITY:
Reports tagged with algebraic complexity:
TR96-049 | 9th September 1996
Per Enflo, Meera Sitharam

#### Stable basis families and complexity lower bounds

--
Scalar product estimates have so far been used in
proving several unweighted threshold lower bounds.
We show that if a basis set of Boolean functions satisfies
certain weak stability conditions, then
scalar product estimates
yield lower bounds for the size of weighted thresholds
of these basis functions.
Stable ... more >>>

TR00-017 | 3rd March 2000
Valentin E. Brimkov, Stefan S. Dantchev

#### On the Algebraic Complexity of Integer Programming

In the framework of the Blum-Shub-Smale real number model \cite{BSS}, we study the {\em algebraic complexity} of the integer linear programming problem
(ILP$_{\bf R}$) : Given a matrix $A \in {\bf R}^{m \times n}$ and vectors
$b \in {\bf R}^m$, $d \in {\bf R}^n$, decide if there is $x ... more >>> TR03-067 | 14th August 2003 Ran Raz #### Multi-Linear Formulas for Permanent and Determinant are of Super-Polynomial Size An arithmetic formula is multi-linear if the polynomial computed by each of its sub-formulas is multi-linear. We prove that any multi-linear arithmetic formula for the permanent or the determinant of an$n \times n$matrix is of size super-polynomial in$n$. more >>> TR06-060 | 4th May 2006 Ran Raz, Amir Shpilka, Amir Yehudayoff #### A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits We construct an explicit polynomial$f(x_1,...,x_n)$, with coefficients in${0,1}$, such that the size of any syntactically multilinear arithmetic circuit computing$f$is at least$\Omega( n^{4/3} / log^2(n) )$. The lower bound holds over any field. more >>> TR06-113 | 25th August 2006 Peter Buergisser #### On defining integers in the counting hierarchy and proving lower bounds in algebraic complexity Let$\tau(n)$denote the minimum number of arithmetic operations sufficient to build the integer$n$from the constant~$1$. We prove that if there are arithmetic circuits for computing the permanent of$n$by$n$matrices having size polynomial in$n$, then$\tau(n!)$is polynomially bounded in$\log n$. Under the ... more >>> TR10-152 | 6th October 2010 Alexey Pospelov #### Faster Polynomial Multiplication via Discrete Fourier Transforms We study the complexity of polynomial multiplication over arbitrary fields. We present a unified approach that generalizes all known asymptotically fastest algorithms for this problem. In particular, the well-known algorithm for multiplication of polynomials over fields supporting DFTs of large smooth orders, Schönhage-Strassen's algorithm over arbitrary fields of characteristic different ... more >>> TR11-025 | 19th February 2011 Yang Li #### Monotone Rank and Separations in Computational Complexity Revisions: 1 , Comments: 1 In the paper, we introduce the concept of monotone rank, and using it as a powerful tool, we obtain several important and strong separation results in computational complexity. \begin{itemize} \item We show a super-exponential separation between monotone and non-monotone computation in the non-commutative model, and thus give the answer to ... more >>> TR11-134 | 9th October 2011 Zeev Dvir, Guillaume Malod, Sylvain Perifel, Amir Yehudayoff #### Separating multilinear branching programs and formulas This work deals with the power of linear algebra in the context of multilinear computation. By linear algebra we mean algebraic branching programs (ABPs) which are known to be computationally equivalent to two basic tools in linear algebra: iterated matrix multiplication and the determinant. We compare the computational power of ... more >>> TR11-168 | 9th December 2011 Joshua Grochow #### Lie algebra conjugacy We study the problem of matrix Lie algebra conjugacy. Lie algebras arise centrally in areas as diverse as differential equations, particle physics, group theory, and the Mulmuley--Sohoni Geometric Complexity Theory program. A matrix Lie algebra is a set$\mathcal{L}$of matrices such that$A,B \in \mathcal{L}$implies$AB - BA \in ... more >>>

TR11-174 | 30th December 2011
Pavel Hrubes, Iddo Tzameret

#### Short Proofs for the Determinant Identities

Revisions: 1

We study arithmetic proof systems $\mathbb{P}_c(\mathbb{F})$ and $\mathbb{P}_f(\mathbb{F})$ operating with arithmetic circuits and arithmetic formulas, respectively, that prove polynomial identities over a field $\mathbb{F}$. We establish a series of structural theorems about these proof systems, the main one stating that $\mathbb{P}_c(\mathbb{F})$ proofs can be balanced: if a polynomial identity of ... more >>>

TR13-011 | 10th January 2013

#### Multilinear Complexity is Equivalent to Optimal Tester Size

In this paper we first show that Tester for an $F$-algebra $A$
and multilinear forms (see Testers and their Applications ECCC 2012) is equivalent to multilinear
algorithm for the product of elements in $A$
(see Algebraic
complexity theory. vol. 315, Springer-Verlag). Our
result is constructive in deterministic polynomial time. ... more >>>

TR13-185 | 24th December 2013
Fu Li, Iddo Tzameret

#### Generating Matrix Identities and Proof Complexity Lower Bounds

Revisions: 3

Motivated by the fundamental lower bounds questions in proof complexity, we investigate the complexity of generating identities of matrix rings, and related problems. Specifically, for a field $\mathbb{F}$ let $A$ be a non-commutative (associative) $\mathbb{F}$-algebra (e.g., the algebra Mat$_d(\mathbb{F})\;$ of $d\times d$ matrices over $\mathbb{F}$). We say that a non-commutative ... more >>>

TR14-056 | 18th April 2014
Zeev Dvir, Rafael Mendes de Oliveira

#### Factors of Sparse Polynomials are Sparse

We show that if $f(x_1,\ldots,x_n)$ is a polynomial with $s$ monomials and $g(x_1,\ldots,x_n)$ divides $f$ then $g$
has at most $\max(s^{O(\log s \log\log s)},d^{O(\log d)})$ monomials, where $d$ is a bound on the individual degrees
of $f$. This answers a question of von zur Gathen and Kaltofen (JCSS ... more >>>

TR14-163 | 29th November 2014
Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh

#### Homomorphism polynomials complete for VP

The VP versus VNP question, introduced by Valiant, is probably the most important open question in algebraic complexity theory. Thanks to completeness results, a variant of this question, VBP versus VNP, can be succinctly restated as asking whether the permanent of a generic matrix can be written as a determinant ... more >>>

TR15-134 | 19th August 2015
Fu Li, Iddo Tzameret, Zhengyu Wang

#### Characterizing Propositional Proofs as Non-Commutative Formulas

Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional-calculus (i.e., Frege) proof is any proof starting from a set of axioms and deriving new Boolean formulas using a fixed set of sound derivation rules. Establishing any super-polynomial size lower bound on Frege proofs (in terms of the ... more >>>

TR15-201 | 10th December 2015
C Ramya, Raghavendra Rao B V

#### Limitations of sum of products of Read-Once Polynomials

Revisions: 1

We study limitations of polynomials computed by depth two circuits built over read-once polynomials (ROPs) and depth three syntactically multi-linear formulas.
We prove an exponential lower bound for the size of the $\Sigma\Pi^{[N^{1/30}]}$ arithmetic circuits built over syntactically multi-linear $\Sigma\Pi\Sigma^{[N^{8/15}]}$ arithmetic circuits computing a product of variable ... more >>>

TR16-101 | 1st July 2016
Toniann Pitassi, Iddo Tzameret

#### Algebraic Proof Complexity: Progress, Frontiers and Challenges

We survey recent progress in the proof complexity of strong proof systems and its connection to algebraic circuit complexity, showing how the synergy between the two gives rise to new approaches to fundamental open questions, solutions to old problems, and new directions of research. In particular, we focus on tight ... more >>>

TR19-140 | 7th October 2019
Ankit Garg, Visu Makam, Rafael Mendes de Oliveira, Avi Wigderson

#### Search problems in algebraic complexity, GCT, and hardness of generator for invariant rings.

Revisions: 1

We consider the problem of outputting succinct encodings of lists of generators for invariant rings. Mulmuley conjectured that there are always polynomial sized such encodings for all invariant rings. We provide simple examples that disprove this conjecture (under standard complexity assumptions).

more >>>

ISSN 1433-8092 | Imprint