The tag has no usage guidance.

learn more… | top users | synonyms

0
votes
0answers
38 views

Computing factorial using ring operations

Given $n,m\in\Bbb N$, is it known that computing $n!\bmod m$ with only ring operations needs $\Omega((\log n)^{1+\epsilon})$ ring operations where $\epsilon>0$?
-4
votes
0answers
47 views

Bit operations in polynomial complexity

Supposing you have degree $N$ polynomials in $\Bbb Z[X]$. Using FFT techniques we can multiply both polynomials in $O(n\log n)$ multiplications. Now assume each coefficient is of size $m$ bits each. ...
2
votes
0answers
65 views

Complexity of a particular determinant

Suppose we have an $n\times n$ matrix $A$ with non-negative integer entries such that $\mathsf{Tr}(A^i)=0$ at every $i\in\{1,2,\dots,n-2,n-1\}$ and $\mathsf{Tr}(A^n)\neq0$, then from Trace-Determinant ...
8
votes
0answers
154 views

Speed-up of Boolean over Algebraic computation

I would like to know what is the maximum speed-up of algebraic computation when we work in the word RAM model. This question is motivated by this theorem from Ryan's paper: Theorem 1.2 Let $(R, ...
6
votes
2answers
612 views

Implications of Riemann Hypothesis variants in TCS

The over ~1½ century old Riemann Hypothesis has deep implications in mathematics and a large edifice of math theory is now proved conditionally on it and numerous variants. I recently came across a ...
10
votes
2answers
186 views

Straight line complexity of monomials

Let $k$ be some field. As usual, for an $f\in k[x_{1},x_{2},\ldots,x_{n}]$ we define $L(f)$ to be the straight-line complexity of $f$ over $k$. Let $F$ be the set of monomials of $f$, namely the ...
1
vote
1answer
94 views

Hitting set of very restricted linear forms

We say that $f\in\mathbb{Z}[x_{1},\dots,x_{n}]$ is a {-1,0,1}-linear form if $f=\sum_{i\in S}x_{i}-\sum_{i\in T}x_{i}$ where $S,T\subseteq[n]$. A hitting set $H\subseteq\mathbb{Z}^{n}$ for ...
4
votes
0answers
202 views

$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$

Stephen Smale claims in Mathematical Problems for the Next Century that $$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}.$$ Can someone sketch the argument or provide a ...
3
votes
2answers
238 views

Complexity of the inverse modulo a composite number

Supposing $M$ is a composite number and supposing $a$ is an integer such that $a^{-1}\mod M$ exists, can we compute $a^{-1} \bmod M$ by using $O(\log^{b}(M))$ ring operations in the RAM model, where ...
4
votes
1answer
271 views

Lower bounds for Polynomials computing the boolean functions

Expressing a boolean function $f$ $:\{ 0,1 \}^{n} \rightarrow \{0,1 \}$ using a polynomial $P(x_{1},...,x_{n})$, where $x_{1},...,x_{n}$ may be integer, finite fields, or other fields. One of the ...
12
votes
1answer
721 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 ...
9
votes
1answer
162 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 ...
5
votes
1answer
101 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 ...
11
votes
1answer
400 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 ...
5
votes
1answer
148 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 ...
3
votes
0answers
91 views

Time or space hierarchy in (uniform) algebraic models of computation

The Time Hierarchy Theorem is a basic result in computational complexity, stating that Turing Machines that can run for longer time (i.e., $f(n)$) are able to decide more languages than Turing ...
6
votes
1answer
182 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 ...
2
votes
1answer
139 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 ...
5
votes
1answer
176 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?
14
votes
0answers
227 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 ...
3
votes
1answer
155 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?
16
votes
0answers
395 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 ...
1
vote
1answer
136 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 ...
5
votes
2answers
223 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 ...
11
votes
2answers
618 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 ...
9
votes
2answers
429 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
454 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
1answer
405 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 ...
12
votes
1answer
387 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, ...
20
votes
2answers
590 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? ...
5
votes
2answers
281 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 ...
13
votes
1answer
522 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 ...
13
votes
2answers
606 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 ...
15
votes
2answers
476 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 ...
13
votes
1answer
285 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
188 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
408 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
842 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
376 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 ...
34
votes
2answers
2k 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 ...
8
votes
1answer
499 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
444 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
358 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 ...
12
votes
1answer
237 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
466 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 ...
32
votes
5answers
1k views

Integer multiplication when one integer is fixed

Update: How do you prevent bounty going to a bad answer? It looks like the system will autoaward bounty for even bad answers (that does not even touch topic of interest even superficially) created ...
9
votes
1answer
702 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 ...
17
votes
3answers
556 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 ...
13
votes
3answers
436 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
385 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 ...