# Questions tagged [algebraic-complexity]

The tag has no usage guidance.

94 questions
Filter by
Sorted by
Tagged with
205 views

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 ... 125 views

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 ...
679 views

362 views

257 views

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, +, ... 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 ... 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 ... 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}-... 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 ... 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$...
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 ...