The algebraic-complexity tag has no wiki summary.
10
votes
2answers
203 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 ...
7
votes
2answers
309 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 ...
9
votes
3answers
231 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 ...
9
votes
0answers
142 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 ...
8
votes
1answer
184 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, ...
3
votes
0answers
110 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 ...
12
votes
1answer
361 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 ...
12
votes
2answers
488 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 ...
5
votes
0answers
188 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 ...
10
votes
1answer
210 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. ...
8
votes
1answer
165 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 ...
5
votes
1answer
336 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 ...
9
votes
2answers
581 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 ...
4
votes
1answer
342 views
Is beating the quadratic bound or improving the upper bound hard for permanents?
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?
By this I mean are there any hints such ...
8
votes
1answer
436 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 ...
5
votes
1answer
318 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 ...
6
votes
2answers
284 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
...
11
votes
1answer
209 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. ...
15
votes
4answers
421 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 ...
9
votes
1answer
561 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 ...
16
votes
3answers
521 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 ...
12
votes
3answers
390 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 ...
10
votes
2answers
363 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 ...
22
votes
3answers
1k 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 ...
32
votes
5answers
1k 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 ...
