# Questions tagged [algebraic-complexity]

The tag has no usage guidance.

25 questions
Filter by
Sorted by
Tagged with
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)...
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 ...
• 151
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 ...
• 151
94 views

• 151
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 ...
• 151
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 ...
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? ...
• 111
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 ...
• 207
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}$, ...
• 141
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 ...
• 13.7k
1 vote