19
The basic sum-of-squares proof system, introduced under the name of Positivstellensatz refutations by Grigoriev and Vorobjov, is a “static” proof system for showing that a set of polynomial equations and inequations
$$S=\{f_1=0,\dots,f_k=0,h_1\ge0,\dots,h_m\ge0\},$$
where $f_1,\dots,f_k,h_1,\dots,h_m\in\mathbb R[x_1,\dots,x_n]$, has no common solution in $\...
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 ...
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))$.
12
SOS can be considered as a proof system where lines are of the form $p(\vec{x}) \geq 0$ where $p(\vec{x})$ is a polynomial in variables $\vec{x}$.
The inference rules are:
$\over x^2-x \geq 0$
$\over x-x^2 \geq 0$
$\over p(\vec{x})^2\geq 0$
$p(\vec{x}) \geq 0 \over p(\vec{x})x \geq 0$
$p(\vec{x}) \geq 0 \over p(\vec{x})(1-x) \geq 0$
$p_1(\vec{x}) \geq 0, \...
12
[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 would have brought out the
connection already?
Wild speculation.
Let me entertain the reader with thoughts about why a categorical rendering 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
Yes, assuming you want both $f_1(x)$ and $f_2(x)$ with integer coefficients.
One of the reasons why LLL is so popular is precisely because it gives a polynomial time algorithm to factor polynomials with integer coefficients.
For an excellent introduction, I recommend C. Yap's "Fundamental Problems in Algorithmic Algebra" (available online, for free), ...
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 ...
8
I think this may have been a typo in Agrawal's paper. The best I know is how to write an $n \times n$ determinant as a projection of an $O(n^3)$-sized permanent, by writing the determinant as an algebraic branching program (and I think this is currently the best known). See the comments on this answer.
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
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 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 inequality that rules out an inclusion of complexity classes, and/or (b) seriously consider multiplicities in the coordinate ring of the orbit closure of the ...
7
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 matrix multiplication (I am assuming, here, that all algorithms are algebraic, in the sense of algebraic circuits). This is because any algebraic circuit ...
7
For the question of when does $p=0 \Rightarrow q=0$, randomness can indeed help, as follows. First, factor $p$ (uses randomness when $p$ is given as a straight-line program; doesn't need randomness if $p$ is given as a coefficient vector). Let $\tilde{p}$ denote the square-free version of $p$ - that is, if $p=p_1^{k_1} p_2^{k_2} \dotsb p_\ell^{k_\ell}$ then $...
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
Snir has proved a tight lower bound on the size of monotone formulas representing the permanent of an $n\times n$ matrix. The lower bound is $2^{2n - 0.25\log^2 n}$, and he notes that a formula of size $2^{2n - 0.25\log^2 n + O(\log n)}$ exists (Theorem 3.1. and comment after the proof).
The survey by Shpilka, and Yehudayoff is a good resource. Also, a ...
6
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 constants by small discrete constants. Here GRH comes into play, since it ensures the existence of enough primes with certain properties.
5
Commutative algorithms
are not studied that much, because you cannot use them
recursively by cutting larger matrices into smaller blocks like you do in Strassen's algorithm.
Since every noncommutative algorithm is a commutative one, commutative algorithms can be trivially as efficient as noncommutative ones.
5
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 going to have to specify more precisely which operations you can perform on the RAM, because to compute it needs to be able to do more than just arithmetic. Memory ...
5
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 [0, \gamma]$ such that $x^2 \cong \alpha \mod \beta$ (the input here is the triple $(\alpha,\beta,\gamma)$) is NP-complete, which is only one variable and degree ...
5
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 bit more of an open question.
If you mean GCT generally as applying algebraic geometry to complexity theory, or perhaps even slightly more specifically using ...
4
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 the other hand, Boolean NP-languages are computable in $\mathrm{NP}_\mathbb C$, hence
$$\mathrm{NP}_\mathbb C=\mathrm P_\mathbb C\implies\mathrm{NP}\subseteq\...
4
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 using only ring operations in the integers: any function that can be computed using only ring operations is a polynomial of its inputs, so if the Remainder ...
4
Of course if you show a lower bound of $\Omega(n \log n)$ for your question, it would imply the same lower bound for the unrestricted model, which is not known.
On the other hand, you are asking whether it is possible to compute the Fourier transform where each $x_i$ is known within $b$ bits of precision using $\ll n \log n$ arithmetic operations. If true, ...
4
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 $\times$ gates unary gates multiplying the input by $x_i^p$ for $i < k$, $p > 0$.
$X_1$-circuits are monotone circuits with all reciprocal inputs, and $X_{n+1}$-...
Only top voted, non community-wiki answers of a minimum length are eligible
