User marcos villagra - MathOverflow

Complete problems for randomized complexity classes

2010-08-04T02:51:43Z

It is believed that $BPP$ has no complete problems. Even for $BPP^O$ for a suitable oracle $O$ it is believed not to have complete problems, unless P=BPP. I wonder if the class MA (the randomized version of NP) has complete problems. For example, IP has complete problems (given that it is equal to PSPACE). There is a similar post asking about complexity classes with no complete problems. Here, I'm interested specifically on complete problems for MA. If the answer is positive, can you give some examples? I've tried google and the complexity zoo, but with no success.

Decomposition of order-3 tensors over the complex numbers

2011-10-08T12:50:22Z

This is a question about decomposition of order-3 tensors. The survey Tensor Decompositions and Applications give a good account of recent developments in this area.

Let $T$ be an order-3 tensor, i.e., the number of indices for each entry is 3. For instance, an order-3 tensor can be defined as an operator $T:[n_1]\times [n_2] \times [n_3]\to \mathbb{C}$, where $[n_i]={1,\dots,n_i}$. I'm particularly interested in tensors with entries defined over the complex numbers.

There are several ways to decompose a tensor. Two of the most popular are the CP decomposition and Tucker decomposition (see sections 3 and 4 in the paper above).

My questions are:

The paper above define its tensors with entries in $\mathbb{R}$. Does the CP and Tucker decompositions work the same for tensors with entries in $\mathbb{C}$?
In the paper above, page 475 about the Tucker decomposition, it reads "Most fitting algorithms assume that the factor matrices are columwise orthonormal....". Orthonormal in what sense? $\ell_1$ norm, $\ell_2$ norm? If the entries of the tensor are in $\mathbb{C}$, is it correct to assume that the Tucker decomposition always decomposes in 3 unitary matrices?
The same as in question 2, but with the CP decomposition. If your tensor decomposes in matrices $A,B,C$, in page 464 in the paper above, reads "It is often useful to assume that the columns of $A,B,C$ are normalized to length 1 with the weights absorbed in the vector $\lambda\in\mathbb{R}^R$ so that $T=\sum_{r=1}^R \lambda_r (a_r \otimes b_r \otimes c_r)$, where $R$ is the rank of $T$, $\otimes$ is the outer product, and $a_r,b_r,c_r$ are the $r$-th columns of $A,B,C$ respectively. Can we assume w.l.o.g. that $A,B,C$ are always unitary?2.

One important thing to note is that the rank can be different if the tensor is over $\mathbb{R}$ or $\mathbb{C}$. Also, if the number of terms in the summation of both decompositions is the rank, then the decompositions are exact.

Answer by Marcos Villagra for Most 'obvious' open problems in complexity theory

2010-08-13T02:23:44Z

$BQP\subseteq ?PH$

We know that simulating quantum mechanics requires polynomial space, but still is open if wether there are problems that only quantum computers can solve efficiently.

Practical use of probability amplification for randomized algorithms

2010-08-10T08:07:04Z

Normally a 2-sided error randomized algorithm will have some constant error $\varepsilon < 1/2$. We know that we can replace the error term for any inverse polynomial. And the inverse polynomial can be replaced for an inverse exponential. Say that we have an algorithm $A$ with $\varepsilon_A=1/p(n)$ for some polynomial $p$ that runs in $T(n)$ steps, and by repeating the algorithm $O(\log \frac{1}{\varepsilon})$ times we obtain and algorithm $B$ with success probability close to 1 but with a logarithmic overhead.

My question is:

(1) If the error decreases polynomially faster, for practical purposes, do we still need to repeat the algorithm several times? Because if we do so we get a logarithmic term (which is not desired), but leaving it as it is, the algorithm will still have a success probability close to 1 for sufficiently large $n$.

(2) What about an exponentially faster decreasing error? Here it seems that we don't need to repeat the algorithm at all.

The same questions apply for 1-sided and 0-sided errors.

Answer by Marcos Villagra for A language complete for NP intersection co-NP

2010-08-08T05:48:12Z

There are no complete problems for $NP\cap coNP$, unless the polynomial hierarchy collapses. You'll find that phrase in several textbooks on complexity theory.

Update: take a look at link talking about this kind of problems. Also, the book by Arora and Barak is a good reference.

Update: The claim above "unless the polynomial hierarchy collapses" is too strong. There is no evidence of such consequence.

A better way to put it would be, there are no problems known to be complete for $NP\cap coNP$. It seems that non-relativizing techniques are required to proof the existence or non-existence of complete sets.

Answer by Marcos Villagra for What are the most important results (and papers) in complexity theory that every one should know?

2010-08-05T12:48:49Z

I think you should add as a recent result the proof for QIP=IP=PSPACE

Answer by Marcos Villagra for Aren't "oracle machines" unsound concepts?

2010-07-23T08:06:50Z

Oracles are used in complexity theory for lower and upper bounds in the decision tree model. Using oracles you can tell if the proof for certain problems (like P vs NP) relativizes or not. If it relativizes then you cannot use a proof based solely on diagonalization (like the halting problem) to solve it. Can also tell you about bad approaches to the problem. A good book to read about this is chapter 3 of Computational Complexity: A Modern Approach (here is the draft). A beautiful paper about oracles in complexity theory was written by Fortnow.

Some people like oracles and some don't. I particularly like them, because lower bounds are very hard to proof in a general Turing machine. Lower bounds in at least a restricted model is a step towards a real lower bound. I believe the best lower bounds we truly understand are AC0 circuits.

Number of subset sums

2010-07-21T08:31:27Z

Let $\mathbb{F}_q$ be a finite field with characteristic $p$ and $p < q$ (i.e. not a prime field). Let $D\subseteq \mathbb{F}_q$ be a some set with $|D|=n$. Find a non-empty subset $\{x_1,\dots,x_k\} \subseteq D$ such that $x_1+\cdots+x_k=s$ for some given $s\in\mathbb{F}_q$. This is the definition of the subset sum problem.

What I cannot understand is how do you count the number of solutions for a given $s$. In this paper, in page 2 it says

heuristically should be approximately $\frac{1}{q}\binom{n}{k}$.

A more concrete questions is, given $s$ how many summands does it have given that we select $D$ randomly from $\mathbb{F}_q$?

Answer by Marcos Villagra for Problems known to be in both NP and coNP, but not known to be in P

2010-07-21T07:39:11Z

A different nice example is a variant of the subset sum problem called Pigeonhole Subset Sum. Given $n$ positive integers with sum less than $2^n-1$, find two disjoint nonempty subsets whose sums are equal. See this paper. In fact, this problem is in TFNP (defined by Meggido and Papadimitriou). Still no polynomial-time algorithms exists for this class of problems.

Comment by Marcos Villagra

2011-10-08T13:43:34Z

I see, the "w.l.o.g." is the important part for me right now.

Comment by Marcos Villagra

2011-10-08T13:22:46Z

@suvrit, regarding 3, that's exactly my question.

Comment by Marcos Villagra

2010-08-13T03:07:42Z

my interpretation of obvious is "your intuition and experience says something but there is no proof for that"

Comment by Marcos Villagra

2010-08-12T01:38:39Z

well, local hamiltonian is complete for QMA, but it is a promise problem. Also, 5-QSAT is complete. As Watrous puts it, "vacuous promise" which means "decision problem". So, it is not expected that a complete decision problem exists for any semantic class.

Comment by Marcos Villagra

2010-08-10T22:51:09Z

yes, I'm misusing the notation, but you completely understood my question. Thanks for the reply, know is crystal clear.

Comment by Marcos Villagra

2010-08-10T22:49:20Z

In several papers they sometimes use amplification and sometimes don't. So I was intrigue on that. It wasn't clear for me when to use it.

Comment by Marcos Villagra

2010-08-10T10:36:46Z

actually, it doesn't say that we can replace an inverse polynomial by an inverse exponential.

Comment by Marcos Villagra

2010-08-10T09:01:19Z

In Arora and Barak, theorem 7.10 page 132 it says Let $L\subseteq\{0,1\}^*$ be a language and suppose there exists a polynomial-time PTM M s.t. for every $x\in \{0,1\}^*$, $Pr[M(x)=L(x)]\geq 1/2+n^{-c}$. Then for every constant $d>0$ there exists a polynomial-time PTM M' such that for every $x\in\{0,1\}^*$, $Pr[M'(x)=L(x)]\geq 1-2^{-n^d}$. Is my interpretation correct? Of course it's not saying anything about the running time.

Comment by Marcos Villagra

2010-08-08T06:27:37Z

@Ryan: also, what would be the consequences of having complete problems for $NP\cap coNP$?

Comment by Marcos Villagra

2010-08-08T06:26:09Z

@Ryan: OK, I understand. Then, what do we need to proof collapsing in the polynomial hierarchy in general?

Comment by Marcos Villagra

2010-08-08T06:05:10Z

in the draft version, chapter 5, the polynomial hierarchy and alternations, page 5.2(92), where it says "Note that $\sum_2^p contains both the classes NP and coNP". There is no proof, but this implies that a complete problem collapses the hierarchy to the second level.

Comment by Marcos Villagra

2010-08-06T02:22:19Z

Thanks for the info. But what I wanted to point out is that for the "lower" classical complexity classes (PSPACE and below) this is the best, is that correct? Although the NQP=coC_{=}P result seems to be at a really low level.

Comment by Marcos Villagra

2010-08-05T23:29:07Z

Well, I have a bias here to be honest but I propose this as a result for the 2005-2010 period. First, to my knowledge, this is the best relation we have between classical and quantum classes. There are other good results on upper bounds for BQP, but this is the only result where a quantum complexity class is completely characterized. Second, although I don't know the complete details, the proof seems to be non-relativizing. And that's important because we can try to learn from here and use it to proof other non-relativizing results. Although, other people already tried that.

Comment by Marcos Villagra

2010-08-04T04:27:31Z

Ryan, yes your right, it's not clear. I've edited the post. Also, thanks for the nice example on CAPP.

Comment by Marcos Villagra

2010-08-04T04:26:08Z

Peter, thanks for the answer. But in general, can we ask something like: Let A and B be a complexity classes of promise problems such that $B\subseteq A$, but not known to be strictly included. If we assume $A\neq B$ then there exists a promise language $L$ which is intermediate for $A$? In other words, is there a theorem like Ladner's but for any complexity class (including randomized and quantum) considering promise languages?