Questions tagged [algebraic-complexity]
The algebraic-complexity tag has no summary.
27 questions
1 vote
0 answers
56 views
Computing all roots of a function with square-root terms
Given $3n$ positive numbers $a_1, \ldots, a_n$, $b_1, \ldots, b_n$, and $x_1, \ldots, x_n$, we are given a function $$f(x) = \sum_{i = 1}^n \frac{a_i}{\sqrt{(x - x_i)^2 + b_i}}.$$ Can we find all the ...
- 11
2 votes
0 answers
134 views
How are moduli spaces related to geometric complexity theory?
I am interested in understanding the relationship between moduli spaces and geometric complexity theory (GCT). Relation between moduli spaces and GCT: How are moduli spaces related to geometric ...
- 147
0 votes
2 answers
281 views
Asymptotic bound of a simple alternating binomial sum
I'm a rather inexperienced researcher, I've been stuck on a question for a while. I would like to find the largest $N = f(n)$ that satisfies the following inequality: $$\sum_{j = 0} ^ n p^{n - j} (-1)...
3 votes
1 answer
160 views
What is the best known bound for the bilinear complexity of $4\times 4$ matrices product
Assume we work on the complex field $\mathbb{C}$. And we use $\langle p,q,r\rangle$ to denote the bilinear complexity of product of a $p\times q$ matrix and a $q\times r$. Recently I read a paper on ...
- 181
5 votes
1 answer
225 views
What is expected (border) rank of the knonecker product of 3-tensors
Given two three order tensors $T$ and $S$ in $F^{m\times n\times p}$ and $F^{a\times b\times c}$. Clearly $\operatorname{rk}(T\otimes S)\le \operatorname{rk}(T)\operatorname{rk}(S)$. Does the equality ...
- 181
0 votes
1 answer
156 views
How far is the slice rank of a tensor from its CP rank
Assume we work on any infinite field and 3-ordered tensor. Clearly for any tensor $T$, we have $\operatorname{srk}(T)\le \operatorname{rk}(T)$. Here, $\operatorname{srk}(T)$ (resp. $\operatorname{rk}(...
- 181
7 votes
1 answer
324 views
Is the matrix multiplication exponent $\omega$ independent from the choice of the base field
The matrix multiplication exponent, usually denoted by $\omega_{F}$, is the smallest real number for which any two $n\times n$ matrices over a field $F$ can be multiplied together using ${\...
- 181
3 votes
0 answers
130 views
Is 'weak' Strassen Conjecture true?
$\newcommand{\rank}{\mathop{\mathrm{rank}}}$Strassen conjectured for two tensors $T_{1}$ and $T_{2}$, $\rank(T_{1}\oplus T_{2})=\rank(T_{1})+\rank(T_{2})$. This is not generally true according to ...
- 181
4 votes
0 answers
142 views
Which projections maintain irreducibility of the polynomial $x_0x_1 + x_2x_3 + \dots + x_{2m-2}x_{2m-1}$?
Let $q = x_0x_1 + x_2x_3 + \dots + x_{2m-2}x_{2m-1} \in \Bbb{C}[x_0, \dots, x_{2m-1}]$. The ambient space is $\Bbb{C}^{2m}$. Which are the polynomials $p \in \Bbb{C}[x_0, \dots, x_{2m-1}]$ such that ...
0 votes
0 answers
128 views
Permutation of low circuit complexity
Let $\mathcal P$ be the set of permutations in $F_2^n$. I am interested in the circuit complexity of such functions in $AC^k[2]$ setup. What are the relevant upper and lower bounds in this context? ...
- 111
3 votes
1 answer
312 views
Algorithm to find a minimal normal subgroup of given group $G$ by matrix group representation
Given a matrix group $G$ by its generators i.e. $G =\langle A_1,A_2,...,A_k \rangle \leq GL_n(q)$, where each $A_i$'s are matrix in $GL_n(q)$ Q. Does there exist a polynomial time (polynomial in ...
- 227
3 votes
1 answer
620 views
Fastest way for certain rectangle matrix multiplication
I have $2$ matrices over $\mathbb{N}$, from the size $n \times \sqrt{n}$ and $\sqrt{n} \times n$. I would like to find an efficient way to multiply them. By efficient, I mean better than $n^{2.5}$, ...
- 141
3 votes
1 answer
202 views
Is factorial computation known to be in a class smaller than $FEXP$?
Functional version of the counting hierarchy is $FCH$. It is an open problem whether there a sequence of $poly(log(n))$ number of $+,\times$ operations utilizing the assistance of $O(1)$ number of ...
- 1
1 vote
0 answers
76 views
complexity of the closure of the image of a morphism of algebraic sets
Let $F$ be a field. Define the complexity of an algebraic set $X$ over $F$ in $\mathbb{A}^m$ to be the smallest integer $n>m$ s.t $X$ is the zero set of at most $n$ polynomials with degree at most $...
- 11
10 votes
1 answer
745 views
Definable constructions in o-minimal geometry
Recently I've been working with o-minimal expansions of $(\mathbb{R},\times,+)$, and I want to work "internally" to the language of o-minimal sets instead of working with "definable ...
- 793
1 vote
0 answers
41 views
Modified straightline complexity of almost square of sums
Assume every linear operation (such as inner product with constant vector) can be performed in one step and multiplication by variables (quadratic operation) can be performed in one step. We know the ...
- 1,846
2 votes
0 answers
298 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$ ...
- 2,235
1 vote
0 answers
123 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 ...
- 221
2 votes
0 answers
511 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 ...
- 1
13 votes
0 answers
349 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 ...
- 13.9k
2 votes
1 answer
459 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?
user76098
4 votes
0 answers
222 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 ...
- 3,154
4 votes
0 answers
258 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 on ...
user5810
2 votes
0 answers
184 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$ ...
- 1
5 votes
1 answer
752 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 ...
- 53
3 votes
0 answers
473 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 ...
- 245
19 votes
2 answers
3k 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 ...
- 2,229