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
One way is described in Berkowitz, On computing the determinant in small parallel time using a small number of processors (see also Soltys, Berkowitz's algorithm and clow sequences). Another way is described in Hrubeš and Tzameret, Short proofs for the determinant identities.
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
[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 ...
12
In the case of determinant, Gaussian elimination can indeed be seen as equivalent to the idea that the determinant has a large symmetry group (of a particular form) and is characterized by that symmetry group (meaning any other homogeneous degree $n$ polynomial in $n^2$ variables with those symmetries must be a scalar multiple of the determinant). (And, as ...
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, \...
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 collection of tensors of a given rank, or even of tensors with rank at most $k$ is not a (Zariski-)closed set, so it cannot be described as the vanishing locus of any set of polynomials, regardless of their complexity. (However, over finite fields tensor-rank is $NP$-complete and over $\mathbb{Q}$ it is $NP$-hard but not known to be in $NP$. But these ...
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
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
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
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
There are cases where the symmetries of a problem ( seem to ) characterize its complexity. One very interesting example is constraint satisfaction problems (CSPs).
Definition of CSP
A CSP is given by a domain $U$, and a constraint language $\Gamma$ ($k$-ary functions from $U^k$ to $\{0, 1\}$). A constraint satisfaction instance is given by a set of ...
7
Like many other questions, the answer to this one can be found in Stothers' thesis. A local USP is a CWP in which the only way in which a 1-piece, a 2-piece and a 3-piece can fit together is if their union is in $S$. Clearly a local USP is a USP, and a construction from [CKSU] shows that the USP capacity is achieved by local USPs (we are going to show that ...
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
You're missing the emptyset $\emptyset$ which is connected to all $b$'s. To get an automorphism, you select a subset $T\subseteq \{1,...,k\}$ of even cardinality and then swaps $a_i$ with $b_i$ for each $i\in T$ and then adjusts the sets in the middle. In your example the graph is $$(a_1,\{12\}),(a_2,\{12\}),(b_1,\emptyset),(b_2,\emptyset).$$
Still in your ...
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 ...
Only top voted, non community-wiki answers of a minimum length are eligible
