User marcos villagra - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T03:09:22Z http://mathoverflow.net/feeds/user/7692 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/34469/complete-problems-for-randomized-complexity-classes Complete problems for randomized complexity classes Marcos Villagra 2010-08-04T02:51:43Z 2013-02-04T14:38:42Z <p>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 <a href="http://mathoverflow.net/questions/27572/are-there-complexity-classes-with-provably-no-complete-problems" rel="nofollow">post</a> 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.</p> http://mathoverflow.net/questions/77528/decomposition-of-order-3-tensors-over-the-complex-numbers Decomposition of order-3 tensors over the complex numbers Marcos Villagra 2011-10-08T12:50:22Z 2011-10-08T12:50:22Z <p>This is a question about decomposition of order-3 tensors. The survey <a href="http://csmr.ca.sandia.gov/~tgkolda/pubs/bibtgkfiles/TensorReview.pdf" rel="nofollow">Tensor Decompositions and Applications</a> give a good account of recent developments in this area.</p> <p>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.</p> <p>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).</p> <p>My questions are:</p> <ol> <li><p>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}$?</p></li> <li><p>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?</p></li> <li><p>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.</p></li> </ol> <p>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.</p> http://mathoverflow.net/questions/35422/most-obvious-open-problems-in-complexity-theory/35424#35424 Answer by Marcos Villagra for Most 'obvious' open problems in complexity theory Marcos Villagra 2010-08-13T02:23:44Z 2010-08-13T02:23:44Z <p>$BQP\subseteq ?PH$</p> <p>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.</p> http://mathoverflow.net/questions/35090/practical-use-of-probability-amplification-for-randomized-algorithms Practical use of probability amplification for randomized algorithms Marcos Villagra 2010-08-10T08:07:04Z 2010-08-10T22:52:02Z <p>Normally a 2-sided error randomized algorithm will have some constant error $\varepsilon &lt; 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.</p> <p>My question is:</p> <p>(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$.</p> <p>(2) What about an exponentially faster decreasing error? Here it seems that we don't need to repeat the algorithm at all.</p> <p>The same questions apply for 1-sided and 0-sided errors.</p> http://mathoverflow.net/questions/34889/a-language-complete-for-np-intersection-co-np/34892#34892 Answer by Marcos Villagra for A language complete for NP intersection co-NP Marcos Villagra 2010-08-08T05:48:12Z 2010-08-08T06:39:59Z <p>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.</p> <p><strong>Update:</strong> take a look at <a href="http://kintali.wordpress.com/2010/06/06/np-intersect-conp/" rel="nofollow">link</a> talking about this kind of problems. Also, the book by <a href="http://www.cs.princeton.edu/theory/complexity/" rel="nofollow">Arora and Barak</a> is a good reference.</p> <p><strong>Update:</strong> The claim above "unless the polynomial hierarchy collapses" is too strong. There is no evidence of such consequence.</p> <p>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.</p> http://mathoverflow.net/questions/34487/what-are-the-most-important-results-and-papers-in-complexity-theory-that-every/34618#34618 Answer by Marcos Villagra for What are the most important results (and papers) in complexity theory that every one should know? Marcos Villagra 2010-08-05T12:48:49Z 2010-08-05T12:48:49Z <p>I think you should add as a recent result the proof for QIP=IP=PSPACE</p> http://mathoverflow.net/questions/33046/arent-oracle-machines-unsound-concepts/33064#33064 Answer by Marcos Villagra for Aren't "oracle machines" unsound concepts? Marcos Villagra 2010-07-23T08:06:50Z 2010-07-23T08:29:37Z <p>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 <a href="http://www.cs.princeton.edu/theory/complexity/" rel="nofollow">draft</a>). A beautiful paper about oracles in complexity theory was written by <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.6652" rel="nofollow">Fortnow</a>.</p> <p>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.</p> http://mathoverflow.net/questions/32761/number-of-subset-sums Number of subset sums Marcos Villagra 2010-07-21T08:31:27Z 2010-07-21T10:06:49Z <p>Let $\mathbb{F}_q$ be a finite field with characteristic $p$ and $p &lt; 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 <code>$\{x_1,\dots,x_k\} \subseteq D$</code> 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.</p> <p>What I cannot understand is how do you count the number of solutions for a given $s$. In this <a href="http://arxiv.org/abs/0708.2456" rel="nofollow">paper</a>, in page 2 it says </p> <blockquote> <p>heuristically should be approximately $\frac{1}{q}\binom{n}{k}$.</p> </blockquote> <p>A more concrete questions is, given $s$ how many summands does it have given that we select $D$ randomly from $\mathbb{F}_q$?</p> http://mathoverflow.net/questions/31821/problems-known-to-be-in-both-np-and-conp-but-not-known-to-be-in-p/32758#32758 Answer by Marcos Villagra for Problems known to be in both NP and coNP, but not known to be in P Marcos Villagra 2010-07-21T07:39:11Z 2010-07-21T07:39:11Z <p>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 <a href="http://portal.acm.org/citation.cfm?id=639541" rel="nofollow">paper</a>. In fact, this problem is in TFNP (defined by <a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6V1G-45GMT3B-2K&amp;_user=3304344&amp;_coverDate=04/30/1991&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_searchStrId=1406950278&amp;_rerunOrigin=google&amp;_acct=C000050802&amp;_version=1&amp;_urlVersion=0&amp;_userid=3304344&amp;md5=4c25392989c40cd15e22655cff593dc3" rel="nofollow">Meggido and Papadimitriou</a>). Still no polynomial-time algorithms exists for this class of problems.</p> http://mathoverflow.net/questions/77528/decomposition-of-order-3-tensors-over-the-complex-numbers Comment by Marcos Villagra Marcos Villagra 2011-10-08T13:43:34Z 2011-10-08T13:43:34Z I see, the &quot;w.l.o.g.&quot; is the important part for me right now. http://mathoverflow.net/questions/77528/decomposition-of-order-3-tensors-over-the-complex-numbers Comment by Marcos Villagra Marcos Villagra 2011-10-08T13:22:46Z 2011-10-08T13:22:46Z @suvrit, regarding 3, that's exactly my question. http://mathoverflow.net/questions/35422/most-obvious-open-problems-in-complexity-theory Comment by Marcos Villagra Marcos Villagra 2010-08-13T03:07:42Z 2010-08-13T03:07:42Z my interpretation of obvious is &quot;your intuition and experience says something but there is no proof for that&quot; http://mathoverflow.net/questions/35236/is-there-a-syntactic-characterization-for-bpp-bqp-or-qma/35300#35300 Comment by Marcos Villagra Marcos Villagra 2010-08-12T01:38:39Z 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, &quot;vacuous promise&quot; which means &quot;decision problem&quot;. So, it is not expected that a complete decision problem exists for any semantic class. http://mathoverflow.net/questions/35090/practical-use-of-probability-amplification-for-randomized-algorithms/35119#35119 Comment by Marcos Villagra Marcos Villagra 2010-08-10T22:51:09Z 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. http://mathoverflow.net/questions/35090/practical-use-of-probability-amplification-for-randomized-algorithms Comment by Marcos Villagra Marcos Villagra 2010-08-10T22:49:20Z 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. http://mathoverflow.net/questions/35090/practical-use-of-probability-amplification-for-randomized-algorithms/35091#35091 Comment by Marcos Villagra Marcos Villagra 2010-08-10T10:36:46Z 2010-08-10T10:36:46Z actually, it doesn't say that we can replace an inverse polynomial by an inverse exponential. http://mathoverflow.net/questions/35090/practical-use-of-probability-amplification-for-randomized-algorithms/35091#35091 Comment by Marcos Villagra Marcos Villagra 2010-08-10T09:01:19Z 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&gt;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. http://mathoverflow.net/questions/34889/a-language-complete-for-np-intersection-co-np/34892#34892 Comment by Marcos Villagra Marcos Villagra 2010-08-08T06:27:37Z 2010-08-08T06:27:37Z @Ryan: also, what would be the consequences of having complete problems for $NP\cap coNP$? http://mathoverflow.net/questions/34889/a-language-complete-for-np-intersection-co-np/34892#34892 Comment by Marcos Villagra Marcos Villagra 2010-08-08T06:26:09Z 2010-08-08T06:26:09Z @Ryan: OK, I understand. Then, what do we need to proof collapsing in the polynomial hierarchy in general? http://mathoverflow.net/questions/34889/a-language-complete-for-np-intersection-co-np/34892#34892 Comment by Marcos Villagra Marcos Villagra 2010-08-08T06:05:10Z 2010-08-08T06:05:10Z in the draft version, chapter 5, the polynomial hierarchy and alternations, page 5.2(92), where it says &quot;Note that $\sum_2^p contains both the classes NP and coNP&quot;. There is no proof, but this implies that a complete problem collapses the hierarchy to the second level. http://mathoverflow.net/questions/34487/what-are-the-most-important-results-and-papers-in-complexity-theory-that-every/34618#34618 Comment by Marcos Villagra Marcos Villagra 2010-08-06T02:22:19Z 2010-08-06T02:22:19Z Thanks for the info. But what I wanted to point out is that for the &quot;lower&quot; 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. http://mathoverflow.net/questions/34487/what-are-the-most-important-results-and-papers-in-complexity-theory-that-every/34618#34618 Comment by Marcos Villagra Marcos Villagra 2010-08-05T23:29:07Z 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. http://mathoverflow.net/questions/34469/complete-problems-for-randomized-complexity-classes/34473#34473 Comment by Marcos Villagra Marcos Villagra 2010-08-04T04:27:31Z 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. http://mathoverflow.net/questions/34469/complete-problems-for-randomized-complexity-classes/34472#34472 Comment by Marcos Villagra Marcos Villagra 2010-08-04T04:26:08Z 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?