Questions tagged [algebraic-complexity]
The algebraic-complexity tag has no usage guidance.
70
questions
1
vote
0answers
97 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}=...
6
votes
0answers
153 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,\...
1
vote
0answers
18 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 ...
5
votes
1answer
116 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 ...
7
votes
0answers
56 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,...
6
votes
0answers
144 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,...
1
vote
0answers
64 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,...
2
votes
2answers
99 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:
...
1
vote
0answers
83 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 ...
2
votes
0answers
97 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
vote
1answer
149 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 ...
3
votes
0answers
44 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 ...
9
votes
0answers
283 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 ...
7
votes
1answer
405 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 ...
14
votes
1answer
539 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 ...
8
votes
0answers
253 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 ...
7
votes
0answers
143 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 ...
5
votes
1answer
165 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 ...
5
votes
0answers
203 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 ...
7
votes
1answer
197 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 ...
2
votes
0answers
119 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 ...
8
votes
0answers
174 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, +, ...
10
votes
2answers
764 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 ...
11
votes
2answers
242 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 ...
1
vote
1answer
112 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}-...
7
votes
1answer
305 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
votes
2answers
904 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 $...
5
votes
1answer
468 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 ...
14
votes
1answer
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 ...
9
votes
1answer
187 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 ...
6
votes
1answer
143 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 ...
12
votes
1answer
673 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 ...
5
votes
1answer
169 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 ...
3
votes
0answers
148 views
Time or space hierarchy in (uniform) algebraic models of computation
The Time Hierarchy Theorem is a basic result in computational complexity, stating that Turing Machines that can run for longer time (i.e., $f(n)$) are able to decide more languages than Turing ...
7
votes
1answer
329 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 ...
3
votes
1answer
347 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(...
5
votes
1answer
298 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?
14
votes
0answers
293 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 ...
3
votes
1answer
210 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?
19
votes
0answers
560 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
vote
1answer
147 views
Morgenstern's Theorem
Morgenstern proves a $\Omega(n\log n)$ lower bound for Fourier transform in the bounded coefficient model.
Let $x=[x_1,x_2,\ldots,x_n]'$ be given vector and $F$ be Fourier transform matrix.
It is ...
5
votes
2answers
259 views
Commutative matrix multiplication algorithms
What is known about commutative algorithms like Winograd algorithm and its variants for Matrix Multiplication? Why is there not much study on them? Can they be asymptotically as efficient as Non-...
11
votes
2answers
1k views
Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size
I am trying to understand the relation between algorithmic complexity and circuit complexity of Determinants and Matrix Multiplication.
It is known that the determinant of an $n\times n$ matrix can ...
9
votes
2answers
620 views
Cancellation and determinant
Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. The algorithm implicitly uses cancellation. Is cancellation ...
9
votes
3answers
576 views
Find the remainder of a large fixed polynomial when divided by a small unknown polynomial
Assume we operate in a finite field. We are given a large fixed polynomial p(x) (of, say, degree 1000) over this field. This polynomial is known beforehand and we are allowed to do computation using a ...
9
votes
1answer
421 views
(Cryptographic) problems solvable in a polynomial number of arithmetic steps
In the paper from Adi Shamir [1] from 1979 he shows, that factoring can be done in a polynomial number of arithmetic steps. This fact was restated, and thus came to my attention, in the recent paper ...
12
votes
1answer
548 views
automorphism in Cai-Furer-Immerman gadgets
In the famous counter example for graph isomorphism via Weisfeiler-Lehman (WL) method the following gadget was constructed in this paper by Cai, Furer and Immerman.
They construct a graph $X_k = (V_k, ...
23
votes
2answers
1k 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?
...
5
votes
2answers
360 views
Complexity of algorithm to test if a graph is asymmetric
Counting the order of automorphism group of a graph is polynomial-time equivalent to graph isomorphism problem. But if we just want to know if the order is greater than 1, what is the complexity of ...
13
votes
1answer
735 views
Smallest known formula for the determinant
The smallest known formula for the determinant has size $n^{\mathcal O(\log n)}$ according to the folklore (or to Ran Raz in its paper Multi-Linear Formulas for Permanent and Determinant are of Super-...
