Questions tagged [algebraic-complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
0 answers
205 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)(...
ULechine's user avatar
  • 149
5 votes
1 answer
154 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 ...
ramseysdream111's user avatar
0 votes
0 answers
67 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) \...
Rishabh Kothary's user avatar
0 votes
0 answers
22 views

Why $rank(C|_V)\geq rank(C)$ for $r$-rank preserving subspace for depth 3 circuits

I was reading Deterministic Black Box PIT Testing for Generalized Depth 3 Arithmetic Circuits - Karnin and Shpilka In the Theorem 3.4 they told $rank(C|_V)\geq rank(C)$ We have $C|_V$ which is ...
Soham Chatterjee's user avatar
0 votes
0 answers
40 views

Why $Rank(C)< R(k,d)$ for Depth 3 Balckbox PIT Algorithm implies $C$ is zero

I was reading the Survey on Polynomial Identity Testing by Nitin Saxena. In the Depth 3 Blackbox PIT Algorithm he first finds $O(k^2d^2+2^k)$ many subspaces of the linear forms of the $\sum\prod\sum(...
Soham Chatterjee's user avatar
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 ...
user avatar
5 votes
1 answer
127 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 $...
Soham Chatterjee's user avatar
0 votes
1 answer
75 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 ...
Soham Chatterjee's user avatar
4 votes
0 answers
76 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)} $ [...
Soham Chatterjee's user avatar
0 votes
0 answers
61 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 ...
Soham Chatterjee's user avatar
0 votes
0 answers
60 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,...
Turbo's user avatar
  • 12.8k
3 votes
0 answers
139 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 ...
Chao Xu's user avatar
  • 4,367
3 votes
1 answer
684 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 $\...
Dmitry's user avatar
  • 201
8 votes
0 answers
189 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 ...
Joshua Grochow's user avatar
5 votes
1 answer
360 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 ...
Ilk's user avatar
  • 900
4 votes
1 answer
217 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 ...
Turbo's user avatar
  • 12.8k
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?...
Huseyin Okan Demir's user avatar
2 votes
0 answers
136 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$...
Turbo's user avatar
  • 12.8k
9 votes
0 answers
168 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 ...
Naysh's user avatar
  • 576
1 vote
0 answers
102 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}=...
Turbo's user avatar
  • 12.8k
7 votes
1 answer
362 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,\...
Stasys's user avatar
  • 6,685
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 ...
Turbo's user avatar
  • 12.8k
5 votes
1 answer
194 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 ...
Turbo's user avatar
  • 12.8k
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,...
user50712's user avatar
6 votes
1 answer
257 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,...
user554578's user avatar
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,...
XL _At_Here_There's user avatar
2 votes
2 answers
125 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: ...
Chetan Gupta's user avatar
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 ...
XL _At_Here_There's user avatar
2 votes
0 answers
133 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 ...
Alexey Milovanov's user avatar
1 vote
1 answer
185 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 ...
XL _At_Here_There's user avatar
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)$...
Turbo's user avatar
  • 12.8k
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 ...
Turbo's user avatar
  • 12.8k
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 ...
Mark S's user avatar
  • 1,063
7 votes
1 answer
623 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 ...
kala's user avatar
  • 71
14 votes
1 answer
803 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 ...
Stasys's user avatar
  • 6,685
1 vote
0 answers
27 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 ...
Turbo's user avatar
  • 12.8k
9 votes
0 answers
266 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 ...
maomao's user avatar
  • 1,345
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 ...
ricardorr's user avatar
  • 541
5 votes
1 answer
197 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 ...
Turbo's user avatar
  • 12.8k
5 votes
0 answers
250 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 ...
user avatar
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 ...
user avatar
2 votes
0 answers
127 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 ...
user avatar
6 votes
0 answers
107 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)...
Turbo's user avatar
  • 12.8k
8 votes
0 answers
185 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, +, ...
Thatchaphol's user avatar
  • 1,130
9 votes
2 answers
880 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 ...
vzn's user avatar
  • 11k
11 votes
2 answers
299 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 ...
Gorav Jindal's user avatar
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}-...
Thatchaphol's user avatar
  • 1,130
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 ...
Anonymous's user avatar
  • 4,001
4 votes
2 answers
2k 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 $...
Turbo's user avatar
  • 12.8k
6 votes
1 answer
673 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 ...
shen's user avatar
  • 211