17

The paper called Multiplication by a constant is sublinear (PDF) gives an algorithm for $\mathcal{O}\left(\frac{n}{\log n}\right)$ shift/addition operations, where $n$ is the size of the constant. Essentially, it works by looking for the $1$-bits in the constant, shifting and adding the number to be multiplied only for those $1$ bits in the constant (like ...


16

The answer is “yes” if $t=n^{O(1)}$. More generally, a threshold $\{+,\cdot\}$-circuit of size $s$ with threshold $t$ can be simulated by a $\{\lor,\land\}$-circuit of size $O(t^2s)$. First, observe that it is enough to evaluate the circuit in $\{0,\dots,t\}$ with truncated addition and multiplication: in particular, if $a,a'\ge t$, then $a+b,a'+b\ge t$, ...


15

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 is no such thing as “the generalized Riemann hypothesis” or “the extended Riemann hypothesis”. Both of these terms are used more-or-less interchangeably in the ...


15

The basic idea is that summing over all Boolean strings (VNP) is like counting the solutions to an NP problem. Even from this perspective, one sees that VNP is more like #P than NP. This is also true as permanent is complete for both VNP and #P. Indeed, the Boolean part of VNP is essentially just #P/poly (it contains #P/poly and is contained in $\mathsf{FP}^{...


13

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(n)$. As $f$ has more monomials, for some we need a longer program. In fact this argument gives a monomial $m$ for which $L(m)=\widetilde\Omega(L^2(f))$.


12

The satisfiability problem for these circuits (i.e., given a circuit $C$ and $u\in[0,1]$, decide whether there is an input $x$ such that $C(x)\ge u$) is in NP, and therefore NP-complete by Neal Young’s comment and Peter Shor’s answer. We can construct a nondeterministic reduction of the problem to linear programming in the following way. Let $\{a_i:i<m\}...


12

For arithmetic circuits over $\mathbb{Z}$ your argument is exactly right. The same argument works for arithmetic circuits over $\mathbb{Q}$ which don't use any fractions $a/b$ where $b$ is even. However, the argument no longer works if you talk about arithmetic circuits over other rings, such as: general arithmetic circuits over $\mathbb{Q}$ (i.e. without ...


11

It is very possible that the determinant is, in a way, harder than the permanent. They are both polynomials, the Waring Rank(sums of n powers of linear forms) of the permanent is roughly 4^n, Chow Rank(sums of products of linear forms) is roughly 2^n. Clearly, Waring Rank \leq 2^{n-1} Chow Rank. For the determinant, those numbers are just lower bounds. On ...


11

Permanent is complete for VNP under p-projections over any field not of characteristic 2. This provides a positive answer to your second question. If this reduction were linear, it would give a positive answer to your first question, but I believe that remains open. In more detail: there is some polynomial $q(n)$ such that $det_n(X)$ is a projection of $...


11

Yes, cancellations are needed and there are lower bounds for monotone and for non-commutative models where cancellations are impossible. See discussion in Monotone arithmetic circuits. A survey of aritmetic circuit complexity can be found in http://www.cs.technion.ac.il/~shpilka/publications/SY10.pdf


11

It's not really needed, so much as it is a matter of convention and utility. Of course, depending on your aims and your specific problem, it is completely reasonable to consider arithmetic circuits of polynomial size regardless of degree. This class is often denoted $\mathsf{VP}_{nb}$ (for "Non-degree-Bounded"), or sometimes "algebraic $\mathsf{P/poly}$ or $\...


10

Blum, Shub and Smale created their model based on known algebraic models of computations, to unify (as much as possible) complexity theory and numerical analysis (cf. [1]). They wanted to give solid theoretical foundations to numerical analysis, and they wanted uniformity since the algorithms used in real life are uniform. Also, their model is a ...


9

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 a sequential automaton, provided that $n$ is written in reversed binary notation (that is, Least Significant Bit First). The number of states of the automaton ...


9

The following is a proof over any ring of characteristic zero that the Hamiltonian cycle polynomial is not a polynomial-size monotone projection of the permanent. The basic idea is that monotone projections of polynomials with nonnegative coefficients lead to the Newton polytope of one being an extended formulation of the Newton polytope of the other, and ...


9

We now understand that for any fixed bound $k \in \mathbb{N}$ on the treewidth, we can convert any Boolean circuit of treewidth less than $k$ to a so-called d-SDNNF circuit, in linear time and with the dependency on $k$ being singly exponential. The so-called d-SDNNFs are circuits satisfying conditions on the use of negation (only at the leaves), ...


9

This is essentially the problem that motivated Valiant to introduce matrix rigidity into complexity (as far as I understand the history). A linear circuit is an algebraic circuit whose only gates are two-input linear combination gates. Every linear transformation (matrix) can be computed by a linear circuit of quadratic size, and the question is when can ...


9

The permanent would seem to qualify, at least conditionally (that is, assuming $\mathsf{VP}^0 \neq \mathsf{VNP}^0$). Note that the Boolean version of the permanent is just to decide whether a given bipartite graph has a perfect matching, which has poly-size circuits. [Summarizing the comments below:] Despite this example being conditional, nothing more than ...


9

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 be shown using Theorem 1 above. See here for details. So, BPP $\subseteq$ P/poly holds also for tropical circuits and, hence, also for "pure" dynamic ...


9

Unfortunately, the best known depth reductions for Boolean circuits only work for very restricted classes of circuits. Valiant (Valiant; Viola) proved that a circuit of size $O(n)$ and depth $O(\log{n})$ can be computed by a depth-3 circuit of size $2^{O(n/\log\log{n})}$. Also, Valiant showed a similar depth reduction for linear size series-parallel circuits ...


8

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 are definitely others about algebraic algorithms), but doesn't do much of PIT. The surveys of Chen-Kayal-Wigderson (freely available from Wigderon's webpage) ...


8

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 actually produces blackboxes for all the irreducible factors of $f$, and works over any large enough field. In fact, this problem of polynomial factorization for ...


8

It’s not exactly clear to me what is the input of the problem and how do you enforce the restriction $p=2^{\Omega(n)}$, however, under any reasonable formulation the answer is no for multivariate polynomials unless NP = RP, due to the reduction below. Given a prime power $q$ in binary and a Boolean circuit $C$ (wlog using only $\land$ and $\neg$ gates), we ...


8

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 double the degree of the polynomial. Thus, for each $m\in M$, $\deg(m)\le 2^{L(f)}$. Now, for some variable $x$ and degree $d$, there is a SLP conputing $x^d$ ...


8

To my knowledge, such a reduction is in fact known: Hrubes and Wigderson ITCS 2014 show how division gates can be eliminated from non-commutative circuits and formulas which compute polynomials. They also provide exponential-size lower bounds for non-commutative formulas with division (not circuits) that compute any entry of the matrix inverse function $X^{-...


7

(I am posting my comments as an answer in response to the OP’s request.) As for Question 1, let fn: {0,1}n→ℕ be a family of functions whose arithmetic circuit requires exponential size. Then so does fn+1, but fn+1 is easy to decide by a trivial monotone arithmetic circuit. If you prefer to avoid constants in monotone arithmetic circuits, then let fn: {0,1}...


7

Note that proving that evaluation of $f$ takes at least as much time as integer multiplication only shows that it needs time $\Omega(M(n))$; while this is generally assumed to be at least $n\log n$, no superlinear bound has been proven. (However, I disagree that this wouldn’t yield anything nontrivial, as was formerly stated in Joshua Grochow’s answer. For ...


7

There was a subsequent extension by Grigoriev and Razborov (PS) that has a shorter exposition of proof.


7

I assume that you mean $P_n(x)= \sum_{i=0}^n \frac{x^i}{i!}$. Peter Bürgisser shows that if this problem is hard, then computing the permanent is hard (http://link.springer.com/article/10.1007/s00037-009-0260-x). To my best knowledge, your problem is open.


7

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.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf


7

If you do not allow subtraction, then you are in the semi-group/monotone setting and there are tight lower bounds known for many natural matrices $M$ that come from computational geometry. (The interest in computational geometry is that range counting can be encoded as matrix-vector multiplication.) For example, the following lower bounds on the size of ...


Only top voted, non community-wiki answers of a minimum length are eligible