# Questions tagged [algebraic-complexity]

The algebraic-complexity tag has no usage guidance.

25
questions

0
votes

2
answers

129
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

63
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

171
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

94
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

159
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

84
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

120
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

192
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

425
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

161
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

60
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

468
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

267
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

95
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

436
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

310
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

377
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

192
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

621
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

441
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 ...