15
votes
Accepted
Implications of Riemann Hypothesis variants in TCS
First, I’m not aware of any CS application of Riemann’s hypothesis as such. There are various applications of generalizations of RH.
Second, a terminological note: contrary to popular belief, there ...
- 14.8k
13
votes
Accepted
Straight line complexity of monomials
If $$f=(\Sigma_{i=1}^n x_i)^{2^n}$$
then it has ${2^n+n-1\choose n-1} \approx 2^{n^2}$ monomials and $L(f)=O(n)$.
By a counting argument, there are $2^{O(n\log n)}$ straight-line programs of length $O(...
- 13.5k
12
votes
Is there a theory that combines category theory/abstract algebra and computational complexity?
[Computational complexity and category theory] seem like such natural pairs.
Given the prominence of computational complexity as a research field, if they were such natural bedfellows, maybe somebody ...
- 10.3k
9
votes
Accepted
VC dimension of polynomials over tropical semirings?
I've realized that the answer to my question is - yes: the VC dimension of degree $\leq d$ polynomials on $n$ variables over any tropical semiring is at most a constant times $n^2\log(n+d)$. This can ...
- 6,605
9
votes
Integer multiplication when one integer is fixed
I am not sure whether this is directly relevant to the question, but the following elementary result might be of interest. Given a fixed natural number $k$, the operation $n \to kn$ can be realized by ...
- 4,721
8
votes
A course for learning algebraic complexity
The massive tome of Burgisser-Clausen-Shokrollahi is the standard reference for algebraic complexity theory (and I'm not really sure there are others from the complexity point of view, though there ...
- 35.7k
8
votes
Accepted
Checking if a polynomial factors into linear factors
As far as I know, the best algorithm we have currently to check if $f$ (given by an arithmetic circuit) can be factorized into linear factors is via the randomized algorithm of Kaltofen (PDF) which ...
- 2,447
8
votes
Straight line complexity of monomials
Note: This is an expansion of a previous comment, since the OP explicitely asked for weaker upper bounds.
The total degree of polynomial $f$ is bounded by $2^{L(f)}$ since each operation can at most ...
- 4,400
8
votes
Accepted
Implications of a recent negative result to geometric complexity
It means that to separate permanent from determinant (a la GCT) one must either (a) use actual differences in multiplicities (and not merely their vanishing or non-vanishing) in order to get an ...
- 35.7k
7
votes
Implications of Riemann Hypothesis variants in TCS
Assuming an extended Riemann Hypothesis, L. M. Adleman and H. W. Lenstra gave a polynomial time algorithm to find an irreducible polynomial of a desired degree over a finite field:
http://www.math....
- 71
7
votes
Accepted
Commutative matrix multiplication algorithms
In answer to the "Update": yes, for any $c$, the existence of an $O(n^c)$ non-commutative algorithm for matrix multiplication is equivalent to the existence of an $O(n^c)$ commutative algorithm for ...
- 35.7k
6
votes
Riemann Hypothesis and Complexity Theory
Valiant's classes are defined over some field. They can use arbitrary constants from that field. To draw some conclusion about Boolean complexity classes, one needs to replace these arbitrary ...
- 2,828
5
votes
Accepted
Complexity of counting integer roots of multivariate polynomials in a polyhedron?
The decision version of this problem is obviously in $\mathsf{NP}$, and Manders & Adleman showed that a specific case is NP-complete. Namely, even deciding whether there exists an integer $x \in [...
- 35.7k
5
votes
Accepted
Is $GCT$ necessarily a negative result program?
It depends a little what you mean exactly by "GCT". If you mean it more generally, the answer is certainly yes. If you mean it more specifically about multiplicity obstructions, this is a ...
- 35.7k
5
votes
Accepted
Complexity of the inverse modulo a composite number
Let us call the function which takes $(a,b)$ to $r$ such that $a = bq + r$ with $r < b$ (and all of $a,b,q,r$ nonnegative integers) the Remainder function. This function cannot be computed at all ...
- 35.7k
5
votes
Sorting using ring operations
This is more a comment than an answer, but the space in the comment box was too short. Or if it's an answer, it's one in the other direction: evidence that linear time is possible.
I think you're ...
- 50.2k
4
votes
Accepted
$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$
As proved in [1], Boolean languages computable in $\mathrm P_\mathbb C$ are in $\mathrm{BPP}$. (They state it for $\mathrm P_\mathbb R$ without inequality tests, which amounts to the same thing.) On ...
- 14.8k
4
votes
Accepted
Can reciprocal inputs speed up monotone computations?
I believe the answer to the Question 1 is negative.
We introduce an auxiliary circuit type: $X_k$-circuits have inputs $x_1, \dots, x_n$ and $1/x_k,\dots,1/x_n$ and have in addition to $+$ and $\...
- 565
3
votes
Accepted
Questions about P vs NP and geometric complexity theory
The short answer is no these are not known, though they are certainly not out of the question. There are no direct implications known to P vs NP, and we do not even have a conjecture (let alone ...
- 35.7k
3
votes
IPS upper bound for subset sum axiom
First, Kaveh is correct that the verification for IPS is randomized, so all it would show is $\mathsf{NP} \subseteq \mathsf{coAM}$ (not $\mathsf{NP} = \mathsf{coNP}$). However, this alone would still ...
- 35.7k
3
votes
Accepted
Hitting set of very restricted linear forms
There is a tight lower bound of size $\Omega(n/ \log n)$ by simple counting argument.
Suppose there is a hitting set $H=\{\alpha_{1},\dots,\alpha_{k}\}$
of size $k$. We will show that there is always ...
- 1,120
2
votes
Is there a theory that combines category theory/abstract algebra and computational complexity?
This answer about isomorphisms between formal languages combines algebraic results from the theory of codes with notions from category theory to investigate possible notions of equivalence and ...
2
votes
Lower bounds for Polynomials computing the boolean functions
Regarding Question C: Number of monomials is essentially the same thing as circuit size of depth-2 algebraic circuits (unless the polynomial is a product of linear polynomials, in which case one could ...
- 35.7k
2
votes
IPS upper bound for subset sum axiom
I think what you are missing is probably the complexity of the proof verification algorithm for IPS.
It is generally true that if we have a Cook-Reckhow proof system and have short proofs for a coNP-...
- 21.3k
2
votes
Accepted
What is the computational complexity of solutions over $\mathbb{Q}$ of polynomial equation with coeffiecents over $\mathbb{Z}$
As already pointed out by Emil Jeřábek in the comments, this is Hilbert's Tenth Problem over the rationals, whose computability is a notorious open question.
In this case, note that the Boolean ...
- 35.7k
2
votes
Decomposing outer product or general rank factorization over $\Bbb F_q$
There might be faster algorithms, but it is easy to compute such a factorization (for any $r$) from the reduced row-echelon form of $M$: set $M_2$ to be the RREF with zero rows removed, and $M_1$ to ...
- 1,419
1
vote
Accepted
Complexity of matrix diagonalization
Reducing to a tridiagonal matrix takes $O(n^3)$ independent of $\epsilon$. I believe the fastest algorithm after that is divide and conquer, which I believe is $O(n^2 \log(1/\epsilon))$, for a total ...
- 3,221
1
vote
VNP is closed under taking coefficients using Valiant's criterion
Here is a related statement which can be proven "algebraically" (as opposed to going to the boolean world of #P/poly).
Suppose $f(x_1,\ldots,x_n,y_1,\ldots,y_m) \in \text{VNP}$ for $m = \...
- 11
1
vote
Complexity of the inverse modulo a composite number
If a reverse of a modulo $M$ exists, it means that $\gcd(a,M)=1$, so you can just use the extended Euclidean algorithm to find $x$ and $y$ that satisfy $ax+My=1$. From here $x$ will be the reverse ...
- 11
Only top scored, non community-wiki answers of a minimum length are eligible