Questions tagged [algebraic-complexity]
The algebraic-complexity tag has no usage guidance.
25
questions
0
votes
2
answers
126
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
60
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 ...
5
votes
1
answer
169
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 ...
0
votes
1
answer
92
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}(...
5
votes
0
answers
152
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 ${\...
2
votes
0
answers
82
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 ...
4
votes
0
answers
119
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
96
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?
...
3
votes
1
answer
179
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 ...
3
votes
1
answer
393
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}$, ...
3
votes
1
answer
159
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
vote
0
answers
59
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 $...
10
votes
1
answer
448
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 ...
1
vote
0
answers
28
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 ...
2
votes
0
answers
265
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
0
answers
94
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
0
answers
434
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
0
answers
307
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
1
answer
376
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
0
answers
192
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
0
answers
190
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
0
answers
165
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$ ...
5
votes
1
answer
613
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
0
answers
440
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 ...
17
votes
2
answers
2k
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 ...