Questions tagged [algebraic-complexity]
The algebraic-complexity tag has no usage guidance.
94
questions
2
votes
1
answer
134
views
Polynomial Identity Testing for $\prod \sum \prod$
I am reading a survey on polynomial identity testing by Saxena. On page 6 he writes that PIT for depth-3 circuits of the form $\prod \sum \prod$ is trivial. He gives no citation and as such I believe ...
- 783
4
votes
0
answers
48
views
Complexity of solving random underdetermined polynomial equations over finite fields
Consider a random system of degree-$d$ polynomials, with $n$ variables and $m$ equations, over some finite field $\mathbb{F}_q:$
$$\begin{align}\sum_{\substack{(\alpha_1,\dots,\alpha_n) \in \mathbb{Z}...
- 41
7
votes
1
answer
387
views
Can reciprocal inputs speed up monotone computations?
A $(+,\times,1/x_i)$ circuit is a standard monotone arithmetic $(+,\times)$ circuit with the only difference that now besides the input variables $x_1,\ldots,x_n$, also their reciprocals $1/x_1,\...
- 9,269
14
votes
1
answer
828
views
VC dimension of polynomials over tropical semirings?
As in this question, I am interested the $\mathbf{BPP}$ vs. $\mathbf{P}$/$\mathrm{poly}$ problem for tropical $(\max,+)$ and $(\min,+)$ circuits. This question reduces to showing upper bounds for the ...
- 6,765
5
votes
1
answer
157
views
Arithmetic Circuit Hierarchy?
The answers to the following question -
Hierarchy theorem for circuit size
give a "circuit hierarchy theorem" for boolean circuits. Does there exist a similar hierarchy theorem for ...
- 632
3
votes
0
answers
214
views
Is the Fueter-Polya Conjecture proven
The Fueter–Pólya conjecture states that if $\pi$ is a polynomial function and a bijection from $\mathbb{N}^2$ to $\mathbb{N}$ then $\pi$ must be the Cantor pairing function ($(x,y) \mapsto 1/2(x + y)(...
- 13.9k
14
votes
2
answers
1k
views
Gaussian Elimination in terms of Group Action
Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to ...
CommunityBot
- 1
0
votes
0
answers
71
views
Can every reducible multivariate polynomial be partitioned into product of univariate polynomials of algebraically independent elements?
Lets say we define a reducible multivariate $f \in \mathbb{F}[x_1,...,x_n]$ to be partionable by $y_1,...,y_r \in \mathbb{F}[x_1,...,x_n]$ iff
\begin{equation}
f(x_1,,,,.x_n) = f_1(y_1)\cdot f_2(y_2) \...
37
votes
5
answers
2k
views
Integer multiplication when one integer is fixed
$n$ is a parameter in the problem.
For every $n$ we pick a random integer $a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$ where $n\in\{1,2,\dots\}$.
Problem: Given $n$ what is the complexity of ...
- 12.9k
3
votes
0
answers
99
views
Complexity of checking if a given prime number can be computed using at most $s$ addition/multiplication operations?
Given are a prime number $p$ and a parameter $s\in\mathbb{N}$.
What is the computational complexity of the problem of determining whether $p$ is computable by a series of at most $s$ steps, each being ...
CommunityBot
- 1
5
votes
1
answer
128
views
DET is $VQP-complete$ and also $DET\in VP$ Does that mean $VP=VQP$
We know that $DET$ is in $VP$. And also from https://conferences.mpi-inf.mpg.de/adfocs-17/material/MB_LN.pdf I came to know that $DET$ is $VQP-complete$. Now certainly $VP\subseteq VQP$. That implies $...
- 2,174
0
votes
1
answer
79
views
In depth reduction of arithmetic formula why we get a $v$ st $\frac{s}3\leq |\Phi_v|\leq \frac{2s}{3}$
I am reading Depth Reduction of Arithmetic Formula form the survey of Ramprasad Saptharishi. Now in the proof of depth reduction due to Brent, 74 that
Let $f$ be an n-variate degree d polynomial ...
- 2,174
4
votes
0
answers
77
views
How to learn the intuition behind probabilistic arguments in Algebraic Complexity lower bounds
I was reading the lower bounds of arithmetic circuits. There in the proof of the theorem
Over field $\mathbb{F}_q$, determinant, permanent requires depth-3 circuits of size $2^{\Omega(n)} $ [...
- 280
0
votes
0
answers
65
views
Any arithmetic circuit of size $s$ and depth $\Delta$ can be converted to a formula of size $s' \leq s^{\Delta}$
I was reading Ramprasad Saptharishi's survey on Arithmetic Circuits.
There in section 2.1.1 fact 2.3 it has
Any arithmetic circuit of of depth $\Delta$ and size $s$, can be
simulated by an arithmetic ...
- 280
0
votes
0
answers
64
views
Polynomial GCD exact complexity in terms of degree and number of variables
https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Proof_that_GCD_exists_for_multivariate_polynomials states multivariate polynomial GCDs may be defined over $\mathbb F_p[x_1,x_2,\dots,...
- 12.9k
0
votes
1
answer
41
views
Decomposing outer product or general rank factorization over $\Bbb F_q$
Given matrix $M\in\Bbb F_q^{n\times n}$ with the promise that there are two matrices $A\in\Bbb F_q^{n\times 1}$ and $B\in\Bbb F_q^{1\times n}$ such that $AB=M$ is there a deterministic $O((n\log q)^c)$...
CommunityBot
- 1
3
votes
1
answer
913
views
Complexity of matrix diagonalization
I'm probably missing a trivial answer, but somehow I can't find it.
Given symmetric matrix $A \in \mathbb R^{n \times n}$, what's the complexity of diagonalizing the matrix, i.e. finding diagonal $\...
- 3,253
3
votes
0
answers
144
views
Nested dissection for singular matrices
Let $F$ be a field. Define $S_G(F)$ be the set of matrices $A$ in $F^{n\times n}$, such that if we replace all non-zero elements in $A$ with $1$, then we obtain the adjacency matrix of $G$ (the ...
- 4,459
8
votes
0
answers
201
views
"Addition function" that works for both perm and det simultaneously?
For $f = (f_n)$ a family of polynomials where $f_n$ is a polynomial in $n^2$ variables (which we can think of as the entries of an $n \times n$ matrix), say a function $S(A,B)$ is an addition function ...
- 37.3k
7
votes
1
answer
932
views
Factoring with LLL when the form of the factors is given
Given a degree $2k$ reducible polynomial
$$f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$$
with
$$\text{gcd}(a_{2k},\dots,a_0)=1$$ that is known to be of the form $f_1(x)f_2(x)$ with $\text{deg}\big(...
- 101
6
votes
1
answer
270
views
VNP is closed under taking coefficients using Valiant's criterion
We consider the family of polynomials
$$\{f_n(x_1,\dots,x_n,y_1,\dots,y_n)\}\in\mathsf{VNP}$$
We want to show that the family
$$\{h_n(x_1,\dots,x_n)\}$$
is in $\mathsf{VNP}$. Where $h_n(x_1,\dots,...
- 11
5
votes
1
answer
394
views
Questions about P vs NP and geometric complexity theory
Reading through various papers on geometric complexity theory (GCT), there is one thing, which pops up, while claimed in various places, that it is an approach to P vs NP, all the results seems to ...
- 37.3k
4
votes
1
answer
224
views
Is $GCT$ necessarily a negative result program?
$GCT$ is a candidate program to separate permanent and determinant through symmetries. If indeed permanent and determinant can be handled in similar complexity class would $GCT$ be a program which can ...
- 37.3k
1
vote
0
answers
1k
views
How can I understand the Coppersmith–Winograd algorithm?
I want to do research on matrix multiplication algorithms. I glanced at the Coppersmith-Winograd algorithm paper, but I didn't understand anything. How can I complete the background to read this paper?...
- 113
2
votes
0
answers
140
views
Matrix multiplication when one matrix is fixed
Let $A$ be a fixed positive entried integer matrix of size $a\times n$ with $\ell$ bits per entry
One is allowed to pre-process this matrix as appropriate.
Given another positive integer entried $B$...
- 12.9k
9
votes
0
answers
169
views
What are some examples of algorithmic applications of noncommutative rational identity testing?
The problem of polynomial identity testing (PIT) is known to be in $\mathsf{RP}$, but not known to be in $\mathsf{P}$.
The related problem of noncommutative rational identity testing (NCIT) is known ...
- 606
1
vote
0
answers
103
views
Complexity of planted root of a system of quadratic homogeneous polynomials?
Given homogeneous degree $2$ randomly chosen polynomials $f_1,\dots,f_{m}$ in $\mathbb Z[x_1,\dots,x_n,y_1,\dots,y_n]$ each with only monomials $x_iy_j$ with condition that the system $f_1=\dots=f_{m}=...
- 12.9k
1
vote
0
answers
26
views
Worst case polynomial in elimination theory under rank conditions?
Given $n$ polynomials $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})\in\mathbb Z[x_1,\dots,x_{2n}]$ where each of $h_1(x_1,\dots,x_{2n}),\dots,h_{2n}(x_1,\dots,x_{2n})$ is homogeneous of degree ...
- 12.9k
20
votes
0
answers
637
views
Identifying Reducible/Irreducible polynomials over $Z[x]$
It is well known LLL algorithm provides a fully polynomial algorithm to factor a reducible primitive polynomial over $\mathbb{Z}[x]$.
Say one only seeks to identify whether a given polynomial over $\...
- 1,132
5
votes
1
answer
203
views
Complexity of counting integer roots of multivariate polynomials in a polyhedron?
Deciding integer roots of multivariate polyomials is undecidable. However what is known about counting integer roots of multivariate polynomials in $\mathbb Z[x_1,\dots,x_m]$ with both $m$ and total ...
- 37.3k
7
votes
0
answers
61
views
Complexity of deciding whether subspaces of Z_2^n cover every point 3*x times
When studying the complexity of checking identities in certain finite algebras, I came across the following decision problem:
Input: A positive integer $n \in N$ and a set of affine subspaces $H_1,...
CommunityBot
- 1
1
vote
0
answers
100
views
What is the relation between computational complexity of algebraic number and computational complexity to find the solution to algebraic equation?
Suppose $\alpha$ is algebraic number, and we have the algorithm with lowest computational complexity to output it, and $f(x)=0$ is algebraic polynomial with $\alpha$ as a root.
If an algorithm which ...
- 359
1
vote
0
answers
71
views
Relating classes of computational complexity to finding solution to classes of algebraic equations [closed]
Having related classes of computational complexity to finding solution to classes of algebraic equations, we may relate classes of computational complexity to algebraic geometry or complex geometry,...
- 1,070
2
votes
2
answers
128
views
IPS upper bound for subset sum axiom
I am reading the following paper
Michael A. Forbes, Amir Shpilka, Iddo Tzameret, Avi Wigderson ,"Proof Complexity Lower Bounds from Algebraic Circuit Complexity", 2016.
IPS is defined as follows:
...
- 37.3k
2
votes
0
answers
134
views
On $\Sigma \Pi \Sigma \Pi(2,r)$-circuits
As I understand from the survey "Progress on Polynomial Identity Testing - II"
a polynomial-time algorithm for solving PIT for $\Sigma \Pi \Sigma \Pi (2, r)$ is unknown.
However, there exists paper ...
- 2,003
1
vote
1
answer
188
views
What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$
What is the complexity of the following problem? (e.g. best-known running time, space, best upper bound in terms of complexity classes, etc.)
Input: A multivariate polynomial $f$ with coefficients ...
CommunityBot
- 1
9
votes
0
answers
304
views
What does a private coin $\mathsf{IP}$ protocol for Hilbert's Nullstellensatz look like?
$\mathsf{GNI}$ Private Coin
In [GMW85], the authors provided the famous interactive proof $\mathsf{IP}$ of Graph Non Isomorphism $\mathsf{GNI}$.
The $\mathsf{GNI}$ protocol entails a verifier ...
- 1,083
3
votes
0
answers
47
views
Equal degree factoring of homogeneous polynomials over $\Bbb Q[x_1,\dots,x_n]$?
Given $f(x_1,\dots,x_n)\in\Bbb Q[x_1,\dots,x_n]$ of form $\prod_{i=1}^df_i(x_1,\dots,x_n)$ where each of $f,f_i$ are homogeneous and each $f_i$ is irreducible what is the best technique to factor such ...
- 12.9k
7
votes
1
answer
638
views
Riemann Hypothesis and Complexity Theory
It is known that "Assuming the generalized Riemann hypothesis (GRH) if VP = VNP then PH collapses to second level". Why would one think of a relation between VP,VNP and the Riemann hypothesis. Where ...
- 2,938
7
votes
1
answer
241
views
Sorting using ring operations
Sorting is in $\mathsf{NP}$. Given a sorted list, it is trivial to check sortedness in linear time.
Is there any evidence sorting of elements from an ordered gcd domain(eg: $\Bbb Z$) cannot be done ...
CommunityBot
- 1
1
vote
0
answers
29
views
A question about a claim in "No occurrence obstructions in geometric complexity theory"
It the new preprint
Peter Bürgisser, Christian Ikenmeyer, Greta Panova, "No occurrence obstructions in geometric complexity theory", 2016
it is stated that
1.3. Conjecture (Mulmuley and Sohoni ...
- 12.9k
9
votes
0
answers
268
views
Checking whether two quadratic equations have a common zero
Given two quadratic equations (with integer coefficients):
$x^T A_1 x+ b^T_1 x + c_1=0$ and $x^T A_2 x+ b^T_2 x + c_2=0$
The problem is to decide whether they have a common zero. Here $x$ is a ...
CommunityBot
- 1
7
votes
0
answers
169
views
Recognition of a primitive root
Adleman and McCurley published a paper in 1994 called "Open problems in number theoretic complexity, II" (http://ww.cstheory.com/papers/open.ps.gz)
Problem 18 of this list of open problems is about ...
- 4,630
5
votes
1
answer
201
views
Implications of a recent negative result to geometric complexity
A paper was posted in arxiv http://arxiv.org/pdf/1512.03798.pdf titled 'Rectangular Kronecker coefficients and plethysms in geometric
complexity theory' by Christian Ikenmeyer and Greta Panova with ...
- 37.3k
25
votes
2
answers
2k
views
Sum-of-squares proof system
Recently I have seen several articles on arxiv that refer to a proof system called sum-of-squares.
Can someone explain what is a sum-of-squares proof and why such proofs are important/interesting?
...
- 4,041
7
votes
1
answer
322
views
$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$
Stephen Smale claims in Mathematical Problems for the Next Century that
$$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}.$$
Can someone sketch the argument or provide a ...
- 17.5k
8
votes
1
answer
520
views
Conditional results implying difficulty of improving upper/lower bounds for permanent
Let $A$ be a given square matrix.
Is there any evidence that beating quadratic lower bounds for $B$
such that $\text{det}(B) = \text{per}(A)$ could be hard?
Is there any plausible conjecture which ...
CommunityBot
- 1
5
votes
0
answers
254
views
What is the status of Determinantal Complexity of Permanent
Recently Landsberg and Ressayre announced an exponential lower bound for permanent's determinantal complexity assuming certain symmetry conditions.
What is the status of the problem of Permanent's ...
CommunityBot
- 1
2
votes
0
answers
129
views
Complexity of a particular determinant
Suppose we have an $n\times n$ matrix $A$ with non-negative integer entries such that $\mathsf{Tr}(A^i)=0$ at every $i\in\{1,2,\dots,n-2,n-1\}$ and $\mathsf{Tr}(A^n)\neq0$, then from Trace-Determinant ...
CommunityBot
- 1
18
votes
2
answers
2k
views
Is there a theory that combines category theory/abstract algebra and computational complexity?
Category theory and abstract algebra deal with the way functions can be combined with other functions. Complexity theory deals with how hard a function is to compute. It's weird to me that I haven't ...
CommunityBot
- 1