Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [algebraic-complexity]

The tag has no usage guidance.

2
votes
0answers
213 views

Can the Nullstellensatz over $\mathbb{C}^n$ be certified by repeatedly guessing witnesses in $\mathbb{Z}^n$?

In Hilbert's Nullstellensatz is in the Polynomial Hierarchy, P. Koiran showed that, given a system of $S$ of $m$ polynomials on $n$ variables of maximum degree $d$, along with a number $x_0$ ...
1
vote
0answers
65 views

How quickly can we mutliply Cayley-Dickson hypercomplexes?

Assuming that all of the coordinates of two Cayley-Dickson Hypercomplex numbers are non-negative integers less than a prime $p$, how quickly can we multiply these numbers? I'm also interested in what ...
2
votes
0answers
254 views

Bit complexity versus arithmetic complexity of polynomial multiplication

Given degree $d_1$ and $d_2$ polynomials in $\Bbb Z[x]$ with coefficient sizes of bits $b_1$ and $b_2$ respectively (1) what is the bit complexity of multiplying the two polynomials? (2) What is ...
12
votes
0answers
259 views

$p$-Adic or arithmetic variants of Khovanskii's “low complexity $\Rightarrow$ tame topology” theory

This question is prompted by a remark I made in a comment to Is every polynomial a factor of a trinomial?, which was that Descartes's observation (cf. his rule of signs, etc.), that the number of real ...
2
votes
1answer
256 views

Can we define a height function for a variety over a finite field?

That is, is there a way to measure the complexity of a point over a finite field the same way we do it over number fields?
4
votes
0answers
183 views

What is the complexity of intersecting two matrix algebras over a finite field?

The following question arose in a joint project with Arkadius Kalka and Adi Ben-Zvi. Let $\mathbb{F}$ be a finite field, and $M_n(\mathbb{F})$ be the $n\times n$ matrices over $\mathbb{F}$. For a ...
4
votes
0answers
165 views

How large do algebraic representations need to be for packing circles in squares?

(This question is inspired by Erich's Packing Center. I'm just asking about circles in squares to keep things simple, since I suspect any answer would apply just-as-well to the rest of the problems ...
2
votes
0answers
158 views

Consequences failure of $\tau$ conjecture

A question Bounds for constructing $n!$ with additions, subtractions, and multiplications starting from $1$ was asked on constructing $ak!$ with ring operations. $\tau$ conjecture states if $\exists$ ...
4
votes
1answer
363 views

The existential theory of the reals

Some definitions of the existential theory of the reals (ETR) allow a real closed field and some definitions allow only rational numbers as coefficients of polynomials. Which one is correct? Will the ...
3
votes
0answers
385 views

Gaussian Elimination in terms of Group Action

Gaussian elimination makes determinant of a matrix polynomial-time computable. The reduction of complexity in computing the determinant, which is otherwise sum of exponential terms, is due to presence ...
14
votes
2answers
490 views

What is the largest tensor rank of $n \times n \times n$ tensor?

The tensor rank of a three dimensional array $M[i,j,k], i,j,k\in [1,\ldots,n]$ is the minimal number of vectors $x_i,y_i,z_i$, such that $M=\sum_{i=1}^d x_i\otimes y_i\otimes z_i$. From dimension ...