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

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}^{...


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 ...


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))$.


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

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^{-...


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

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

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 ...


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

(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

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 ...


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


6

One challenge is that if you remove the "monotone" restriction, we do know how to compute such things efficiently. You can compute the value of all $S_0^n,\dots,S_n^n$ (evaluate all $n+1$ elementary symmetric polynomials) in $O(n \log^2 n)$ time, using FFT-based polynomial multiplication. So, proving a $\Omega(nk)$ lower bound in the monotone circuit model ...


6

There are deterministic and randomized algorithm running in time $\mathrm{poly}(n,d,k)$, where $n$ is the number of variables, $d$ is the degree and $k$ is the sparsity. AFAIK, the results are stated for characteristic zero fields but work over any field large enough (again, polynomially large in the parameters). This paper of Kaltofen and Yagati discusses ...


6

There are deterministic algorithms that can do it even in time polynomial in $n$, $k$, $\log d$, and $L$ ($n$ numbers of variables, $k$ sparsity, and $d$ the degree, $L$ the bit length of the coefficients), see e.g. Garg and Schost, Interpolation of polynomials given by straight-line programs. Theor. Comput. Sci. 410(27-29): 2659-2662 (2009) or Bläser and ...


5

First, super-linear lower bounds on multiplying two integers are not known: for all we know, there may be an $O(n)$-time algorithm for multiplying two $n$-bit integers. So even if your "proof by Taylor series" idea worked, it wouldn't yield anything nontrivial a $\Omega(n \log n)$ lower bound, all it would yield is a lower bound of $\Omega(M(n))$ where $M(n)$...


5

The place from which I had read the proof was Completeness and Reduction in Algebraic Complexity Theory by Peter Bürgisser (.ps). As for the determinental complexity of the permanent, the best lower bound known so far is $\Omega(n^2)$ by Mignon and Ressayre.


4

See Eric Allender's survey of "recent" breakthroughs (circa more than a decade ago) in the complexity of division. The bottom line is that Division is complete for DLOGTIME-uniform $\mathsf{TC}^0$ so in particular there is a poly-sized circuit (of constant depth) that takes $x$ and $y$ as input and produces $x/y$. Notice that this circuit doesn't even ...


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