Questions tagged [algebraic-complexity]
The algebraic-complexity tag has no usage guidance.
83
questions
3
votes
0
answers
126
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,256
3
votes
1
answer
159
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 $\...
- 191
8
votes
0
answers
166
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 ...
- 35.7k
5
votes
1
answer
263
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 ...
- 723
4
votes
1
answer
197
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 ...
- 12.5k
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?...
2
votes
0
answers
131
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.5k
9
votes
0
answers
151
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 ...
- 454
1
vote
0
answers
101
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.5k
7
votes
1
answer
346
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,\...
- 6,605
1
vote
0
answers
22
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.5k
5
votes
1
answer
170
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 ...
- 12.5k
7
votes
0
answers
57
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,...
- 71
6
votes
1
answer
212
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,...
- 161
1
vote
0
answers
68
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,009
2
votes
2
answers
116
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:
...
- 31
1
vote
0
answers
98
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 ...
- 1,009
2
votes
0
answers
117
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 ...
- 1,537
1
vote
1
answer
170
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 ...
- 1,009
0
votes
1
answer
34
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)$...
- 12.5k
3
votes
0
answers
46
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.5k
9
votes
0
answers
299
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 ...
- 822
7
votes
1
answer
542
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 ...
- 71
14
votes
1
answer
761
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,605
1
vote
0
answers
24
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.5k
9
votes
0
answers
264
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 ...
- 1,345
7
votes
0
answers
162
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 ...
- 521
5
votes
1
answer
186
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 ...
- 12.5k
5
votes
0
answers
239
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 ...
user34945
7
votes
1
answer
234
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 ...
user34945
2
votes
0
answers
125
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 ...
user34945
6
votes
0
answers
106
views
Polynomial decomposition complexity
Given $N(x)\in\Bbb Z_{\geq0}[x]$ with non-negative coefficients with promise that there exists $a(x),b(x),c(x),d(x)\in\Bbb Z_{\geq0}[x]$ with non-negative coefficients such that $N(x)=a(x)b(x)+c(x)d(x)...
- 12.5k
8
votes
0
answers
184
views
Speed-up of Boolean over Algebraic computation
I would like to know what is the maximum speed-up of algebraic computation when we work in the word RAM model.
This question is motivated by this theorem from Ryan's paper:
Theorem 1.2 Let $(R, +, ...
- 1,120
10
votes
2
answers
849
views
Implications of Riemann Hypothesis variants in TCS
The over ~1½ century old Riemann Hypothesis has deep implications in mathematics and a large edifice of math theory is now proved conditionally on it and numerous variants. I recently came across a ...
- 10.8k
11
votes
2
answers
285
views
Straight line complexity of monomials
Let $k$ be some field. As usual, for an $f\in k[x_{1},x_{2},\ldots,x_{n}]$
we define $L(f)$ to be the straight-line complexity of $f$ over
$k$. Let $F$ be the set of monomials of $f$, namely the ...
- 717
1
vote
1
answer
113
views
Hitting set of very restricted linear forms
We say that $f\in\mathbb{Z}[x_{1},\dots,x_{n}]$ is a {-1,0,1}-linear
form if $f=\sum_{i\in S}x_{i}-\sum_{i\in T}x_{i}$ where $S,T\subseteq[n]$.
A hitting set $H\subseteq\mathbb{Z}^{n}$ for {-1,0,1}-...
- 1,120
7
votes
1
answer
320
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 ...
- 3,993
4
votes
2
answers
1k
views
Complexity of the inverse modulo a composite number
Supposing $M$ is a composite number and supposing $a$ is an integer such that $a^{-1}\mod M$ exists, can we compute $a^{-1} \bmod M$ by using $O(\log^{b}(M))$ ring operations in the RAM model, where $...
- 12.5k
6
votes
1
answer
631
views
Lower bounds for Polynomials computing the boolean functions
Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x_{1},...,x_{n})$, where $x_{1},...,x_{n}$ may be integer, finite fields, or other fields.
One of the most ...
- 201
14
votes
1
answer
2k
views
A course for learning algebraic complexity
I want to learn about algebraic algorithms and complexity thoery. In particular, I am interested in PIT.
Is there a set of lecture notes, books, papers and surveys for students who have read standard ...
- 201
9
votes
1
answer
221
views
Checking if a polynomial factors into linear factors
Let $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ be a polynomial given
by an arithmetic circuit $C$ of size $s$. Given $C$ as the input,
is there a deterministic algorithm to check whether all the ...
- 717
6
votes
1
answer
157
views
Where does randomness help when deciding algebraic geometry over $\mathbb{C}$?
If we have a single straight line program expressing a multivariate polynomial equation with integer coefficients, the Schwartz-Zippel lemma gives a simple randomized algorithm for deciding whether ...
- 3,221
12
votes
1
answer
769
views
Expressing Determinant as Permanent
One major problem in TCS is the problem of expressing a permanent as a determinant. I was reading Agrawal's paper Determinant Versus Permanent and in one paragraph he claims the reverse problem is ...
- 131
5
votes
1
answer
175
views
Size of Formulas with no negative sign for Matrix Permanent
What is the best lower bound for algebraic formulas for Permanent of a matrix given that the formulas have no negative sign? Is there an exponential lower bound known for such formulas and what would ...
- 12.5k
7
votes
1
answer
394
views
Uniformity vs. nonuniformity in algebraic complexity theory
I understand that the study of Boolean circuits and nonuniform complexity classes was introduced to (hopefully) prove separation of uniform complexity classes. In this sense, nonuniform computational ...
- 875
7
votes
1
answer
700
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(...
- 12.5k
6
votes
1
answer
393
views
Degree restriction for polynomials in $\mathsf{VP}$
why do we need the restriction on the degree for a polynomial to be in VP due to which $(\prod_{i=0}^{n} x_i)^{2^n}$ $\notin$ VP even though it has a poly-size circuit?
- 193
14
votes
0
answers
299
views
Exponential-time factorization of polynomials
Let an explicit field be a field for which equality is decidable (in some standard model of computation). I am interested in the factorization of univariate polynomials over an explicit field.
It is ...
- 4,400
3
votes
1
answer
242
views
Convolution without FFT
What is the best upper and lower bound known for convolution without FFT?
Is FFT proven to be essential for time complexity reduction?
Is cancellation essential as well?
- 12.5k
20
votes
0
answers
616
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 $\...
- 12.5k