Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [algebraic-complexity]

The tag has no usage guidance.

95 questions
Filter by
Sorted by
Tagged with
76 views

### Reference request: finite field computation over the Word-RAM model

Let $q = p^\ell$ be a positive integer power of a prime $p$, of size $q = \text{poly}(n)$. Over the Word-RAM model (with words of size $O(\log n)$), how quickly can we perform addition and ...
• 686
167 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 ...
50 views

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}... 3 votes 0 answers 216 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)(... • 149 5 votes 1 answer 158 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 ... 0 votes 0 answers 75 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 f(x_1,,,,.x_n) = f_1(y_1)\cdot f_2(y_2) \... 3 votes 0 answers 101 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 ... 5 votes 1 answer 129 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 ... 0 votes 1 answer 80 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 ... 4 votes 0 answers 78 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)}  [... 0 votes 0 answers 66 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 ... 0 votes 0 answers 66 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 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,479 3 votes 1 answer 988 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 \... • 201 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.4k 5 votes 1 answer 400 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 ... • 920 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 ... • 12.9k 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 141 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 ... • 686 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 7 votes 1 answer 390 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,765 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 5 votes 1 answer 205 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.9k 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,... 6 votes 1 answer 274 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 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,079 2 votes 2 answers 129 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 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 ... • 1,079 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 ... • 1,079 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)... • 12.9k 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 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,125 7 votes 1 answer 640 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 835 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 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 269 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 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 ... • 561 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 ... • 12.9k 5 votes 0 answers 255 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 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 ... 2 votes 0 answers 131 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 ... 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)... • 12.9k 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, +, ... • 1,130 9 votes 2 answers 888 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 ... • 11k 11 votes 2 answers 303 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 ... • 727 1 vote 1 answer 114 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,130 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 ...
• 4,041
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 \$...