Questions tagged [algebraic-complexity]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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)...
Jason Zheng's user avatar
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 ...
Nick Chen's user avatar
  • 151
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 ...
Nick Chen's user avatar
  • 151
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}(...
Nick Chen's user avatar
  • 151
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 ${\...
Nick Chen's user avatar
  • 151
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 ...
Nick Chen's user avatar
  • 151
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 ...
Varun Ramanathan's user avatar
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? ...
manmatha.roy's user avatar
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 ...
Jins's user avatar
  • 151
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}$, ...
Eric_'s user avatar
  • 141
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 ...
Turbo's user avatar
  • 13.7k
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 $...
Itamar hadas's user avatar
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 ...
Hunter Spink's user avatar
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 ...
VS.'s user avatar
  • 1,816
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$ ...
Mark S's user avatar
  • 2,143
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 ...
Matt Groff's user avatar
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 ...
Turbo's user avatar
  • 13.7k
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 ...
Vesselin Dimitrov's user avatar
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?
user avatar
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 ...
Boaz Tsaban's user avatar
  • 3,104
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 ...
user avatar
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$ ...
Turbo's user avatar
  • 13.7k
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 ...
dschaehi's user avatar
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 ...
DurgaDatta's user avatar
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 ...
Klim Efremenko's user avatar