Questions tagged [algebraic-complexity]
The algebraic-complexity tag has no usage guidance.
94
questions
15
votes
1
answer
2k
views
A course for learning algebraic complexity
I want to learn about algebraic algorithms and complexity thoery. In particular, I am interested in PIT.
Is there a set of lecture notes, books, papers and surveys for students who have read standard ...
- 211
9
votes
1
answer
236
views
Checking if a polynomial factors into linear factors
Let $f\in\mathbb{Q}[x_{1},x_{2},\ldots,x_{n}]$ be a polynomial given
by an arithmetic circuit $C$ of size $s$. Given $C$ as the input,
is there a deterministic algorithm to check whether all the ...
- 727
6
votes
1
answer
171
views
Where does randomness help when deciding algebraic geometry over $\mathbb{C}$?
If we have a single straight line program expressing a multivariate polynomial equation with integer coefficients, the Schwartz-Zippel lemma gives a simple randomized algorithm for deciding whether ...
- 3,253
12
votes
1
answer
823
views
Expressing Determinant as Permanent
One major problem in TCS is the problem of expressing a permanent as a determinant. I was reading Agrawal's paper Determinant Versus Permanent and in one paragraph he claims the reverse problem is ...
- 131
5
votes
1
answer
178
views
Size of Formulas with no negative sign for Matrix Permanent
What is the best lower bound for algebraic formulas for Permanent of a matrix given that the formulas have no negative sign? Is there an exponential lower bound known for such formulas and what would ...
- 12.9k
8
votes
1
answer
487
views
Uniformity vs. nonuniformity in algebraic complexity theory
I understand that the study of Boolean circuits and nonuniform complexity classes was introduced to (hopefully) prove separation of uniform complexity classes. In this sense, nonuniform computational ...
- 895
7
votes
1
answer
932
views
Factoring with LLL when the form of the factors is given
Given a degree $2k$ reducible polynomial
$$f(x)=\sum_{i=0}^{2k}a_ix^i\in\Bbb Z[x]$$
with
$$\text{gcd}(a_{2k},\dots,a_0)=1$$ that is known to be of the form $f_1(x)f_2(x)$ with $\text{deg}\big(...
- 12.9k
6
votes
1
answer
456
views
Degree restriction for polynomials in $\mathsf{VP}$
why do we need the restriction on the degree for a polynomial to be in VP due to which $(\prod_{i=0}^{n} x_i)^{2^n}$ $\notin$ VP even though it has a poly-size circuit?
- 327
14
votes
0
answers
305
views
Exponential-time factorization of polynomials
Let an explicit field be a field for which equality is decidable (in some standard model of computation). I am interested in the factorization of univariate polynomials over an explicit field.
It is ...
- 4,504
3
votes
1
answer
257
views
Convolution without FFT
What is the best upper and lower bound known for convolution without FFT?
Is FFT proven to be essential for time complexity reduction?
Is cancellation essential as well?
- 12.9k
20
votes
0
answers
637
views
Identifying Reducible/Irreducible polynomials over $Z[x]$
It is well known LLL algorithm provides a fully polynomial algorithm to factor a reducible primitive polynomial over $\mathbb{Z}[x]$.
Say one only seeks to identify whether a given polynomial over $\...
- 12.9k
1
vote
1
answer
157
views
Morgenstern's Theorem
Morgenstern proves a $\Omega(n\log n)$ lower bound for Fourier transform in the bounded coefficient model.
Let $x=[x_1,x_2,\ldots,x_n]'$ be given vector and $F$ be Fourier transform matrix.
It is ...
- 12.9k
5
votes
2
answers
316
views
Commutative matrix multiplication algorithms
What is known about commutative algorithms like Winograd algorithm and its variants for Matrix Multiplication? Why is there not much study on them? Can they be asymptotically as efficient as Non-...
- 12.9k
11
votes
2
answers
1k
views
Determinants and Matrix Multiplication - Similarity and differences in algorithmic complexity and arithmetic circuit size
I am trying to understand the relation between algorithmic complexity and circuit complexity of Determinants and Matrix Multiplication.
It is known that the determinant of an $n\times n$ matrix can ...
- 12.9k
10
votes
2
answers
815
views
Cancellation and determinant
Berkowitz algorithm provides a polynomial size circuit with logarithmic depth for determinant of a square matrix using matrix powers. The algorithm implicitly uses cancellation. Is cancellation ...
- 12.9k
9
votes
3
answers
607
views
Find the remainder of a large fixed polynomial when divided by a small unknown polynomial
Assume we operate in a finite field. We are given a large fixed polynomial p(x) (of, say, degree 1000) over this field. This polynomial is known beforehand and we are allowed to do computation using a ...
- 91
9
votes
1
answer
454
views
(Cryptographic) problems solvable in a polynomial number of arithmetic steps
In the paper from Adi Shamir [1] from 1979 he shows, that factoring can be done in a polynomial number of arithmetic steps. This fact was restated, and thus came to my attention, in the recent paper ...
- 615
12
votes
1
answer
748
views
automorphism in Cai-Furer-Immerman gadgets
In the famous counter example for graph isomorphism via Weisfeiler-Lehman (WL) method the following gadget was constructed in this paper by Cai, Furer and Immerman.
They construct a graph $X_k = (V_k, ...
- 1,281
25
votes
2
answers
2k
views
Sum-of-squares proof system
Recently I have seen several articles on arxiv that refer to a proof system called sum-of-squares.
Can someone explain what is a sum-of-squares proof and why such proofs are important/interesting?
...
- 4,041
6
votes
2
answers
411
views
Complexity of algorithm to test if a graph is asymmetric
Counting the order of automorphism group of a graph is polynomial-time equivalent to graph isomorphism problem. But if we just want to know if the order is greater than 1, what is the complexity of ...
- 1,281
13
votes
1
answer
937
views
Smallest known formula for the determinant
The smallest known formula for the determinant has size $n^{\mathcal O(\log n)}$ according to the folklore (or to Ran Raz in its paper Multi-Linear Formulas for Permanent and Determinant are of Super-...
- 4,504
14
votes
2
answers
1k
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 ...
- 1,281
18
votes
2
answers
2k
views
Is there a theory that combines category theory/abstract algebra and computational complexity?
Category theory and abstract algebra deal with the way functions can be combined with other functions. Complexity theory deals with how hard a function is to compute. It's weird to me that I haven't ...
- 1,073
13
votes
1
answer
472
views
Capacity of Uniquely Solvable Puzzle (USP)
In their seminal paper Group-theoretic algorithms for matrix multiplications, Cohn, Kleinberg, Szegedy and Umans introduce the concept of uniquely solvable puzzle (defined below) and USP capacity. ...
- 14.5k
8
votes
1
answer
252
views
Is tensor rank is in VNP?
Is it known if tensor rank of three dimensional tensors lies in VNP (non deterministic valiant class)? If yes, what is known about high dimensional tensor rank?
In fact I am interested in much more ...
- 903
5
votes
1
answer
444
views
Classical Matrix-Vector multiplication Complexity of standard matrices
Why are standard unitary transforms such as the Fourier and the Hadamard transforms believed to have a multiplicative complexity (number of multiplications) of $O(n^{1+\delta_{m}})$ and an additive ...
- 12.9k
10
votes
2
answers
1k
views
Determinant of a generalized Vandermonde matrix
Moore matrix is similar to Vandermonde matrix but has a slightly modified definition.
http://en.wikipedia.org/wiki/Moore_matrix
What is the complexity of computing the determinant of a given $n \...
- 12.9k
8
votes
1
answer
520
views
Conditional results implying difficulty of improving upper/lower bounds for permanent
Let $A$ be a given square matrix.
Is there any evidence that beating quadratic lower bounds for $B$
such that $\text{det}(B) = \text{per}(A)$ could be hard?
Is there any plausible conjecture which ...
- 2,208
39
votes
2
answers
3k
views
Mulmuley's GCT program
It is sometimes claimed that Ketan Mulmuley's Geometric Complexity Theory is the only plausible program for settling the open questions of complexity theory like P vs. NP question. There has been ...
- 4,041
9
votes
1
answer
620
views
Permanent of a $3 \times 3$ and $4 \times 4$ matrix from determinants
Let $A$ be a $3 \times 3$ or a $4 \times 4$ matrix with entries $a_{ij}$. Can someone provide me a matrix $B$ so that $\operatorname{per}(A) = \det(B)$? What is the smallest explicit $B$ that is known ...
- 2,208
5
votes
1
answer
603
views
Permanent as projection of determinant and another permanent
I am looking for explicit examples where permanent of a given matrix $A$ is given by a determinant of a larger matrix $B$ (projection in the sense of Valiant). Is there any reference where I can find ...
- 2,208
6
votes
2
answers
561
views
Iterative algorithms in algebraic complexity (Blum-Shub-Smale-Model)
I know the Blum-Shub-Smale model. It is claimed to provide a theoretical framework for algorithms in real and complex algebra and analysis.
A very general question:
Most algorithms compromise of
...
- 1,165
12
votes
1
answer
287
views
Explicit polynomials in 1 variable with superlogarithmic circuit complexity lower bounds?
By counting arguments, one can show that there exist polynomials of degree n in 1 variable (i.e., something of the form $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0)$ which have circuit complexity n. ...
- 969
15
votes
4
answers
633
views
Are there known to exist functions with the following direct-sum property?
This question can be asked either in the framework of circuit complexity of Boolean circuits, or in the framework of algebraic complexity theory, or probably in lots of other settings. It is easy to ...
- 969
37
votes
5
answers
2k
views
Integer multiplication when one integer is fixed
$n$ is a parameter in the problem.
For every $n$ we pick a random integer $a_n\in\{2^{n-1},2^{n-1}+1,\dots,2^n-1\}$ where $n\in\{1,2,\dots\}$.
Problem: Given $n$ what is the complexity of ...
- 12.9k
5
votes
0
answers
137
views
Integer multiplication where regular Fourier Transform approach would fail to provide best upper bound
I have a problem where multiplication of integers via regular Fourier Transform based multiplication technique would fail to provide best upper bound since the sequences of bits in both integers are ...
- 12.9k
2
votes
0
answers
10
views
Complexity of a special matrix
Let $x$, $y$, $z$ $\in \mathbb C$ with $|x| = |y| = |z| = 1$.
Has the following matrix (call it $S$) been studied before?
\begin{bmatrix}
1 &x &xy &xyz \newline
\bar{x} &1 &y &...
- 12.9k
9
votes
1
answer
1k
views
True Bit Complexity of matrix multiplication is $O(n^{4})$
Matrix multiplication using regular (row - column inner product) technique takes $O(n^{3})$ multiplucations and $O(n^{3})$ additions. However assuming equal sized entries (number of bits in each entry ...
- 12.9k
2
votes
0
answers
82
views
Algorithmic Number Theory Problem - related to Matrix Multiplication Complexity
Let $F(x) = \displaystyle\sum_{i=0}^{n-1}a_{i}x^{i}$, $G(x,y) = \displaystyle\sum_{i=0}^{n_{x}-1}\sum_{j=0}^{n_{y}-1}a_{ij}x^{i}y^{j} \in \mathbb Z[x,y]$ with $a_{i},a_{ij} \in [0,p-1]$ for some prime ...
- 12.9k
17
votes
3
answers
671
views
Formal representation of rings in computations
While reading a paper about using algebraic methods to detect some induced subgraphs, it appears that edge ideal is an important tool connecting commutative algebra and graph theory. Since I'm not ...
- 7,648
16
votes
3
answers
737
views
Hardness Guarantees for AES
Many public-key cryptosystems have some kind of provable security. For example, the Rabin cryptosystem is provably as hard as factoring.
I wonder whether such kind of provable security exists for ...
- 16.5k
10
votes
2
answers
438
views
Lower bounds for linear satisfiability problem
In SODA 1995, Jeff Erickson showed lower bounds for linear satisfiability (checking if a some $r$-subset of $n$ real numbers satisfies a linear equation on $r$ variables). The proof method uses ...
- 1,955
39
votes
3
answers
4k
views
Does $VP \neq VNP$ imply $P \neq NP$?
As far as I understand, the geometric complexity theory program attempts to separate $VP \neq VNP$ by proving that the permament of a complex-valued matrix is much harder to compute than the ...
- 393
36
votes
5
answers
2k
views
Complexity of testing for a value versus computing a function
In general we know that the complexity of testing whether a function takes a particular value at a given input is easier than evaluating the function at that input. For example:
Evaluating the ...
- 37.3k