Marcos Villagra
Reputation
Next privilege 200 Rep.
 Nov 22 awarded Popular Question Jun 18 awarded Popular Question Oct 8 comment Decomposition of order-3 tensors over the complex numbers I see, the "w.l.o.g." is the important part for me right now. Oct 8 comment Decomposition of order-3 tensors over the complex numbers @suvrit, regarding 3, that's exactly my question. Oct 8 asked Decomposition of order-3 tensors over the complex numbers Aug 19 awarded Enthusiast Aug 13 comment Most 'obvious' open problems in complexity theory my interpretation of obvious is "your intuition and experience says something but there is no proof for that" Aug 13 answered Most 'obvious' open problems in complexity theory Aug 12 comment Is there a syntactic characterization for BPP, BQP, or QMA? 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. Aug 10 revised Practical use of probability amplification for randomized algorithms deleted 16 characters in body Aug 10 accepted Practical use of probability amplification for randomized algorithms Aug 10 comment Practical use of probability amplification for randomized algorithms yes, I'm misusing the notation, but you completely understood my question. Thanks for the reply, know is crystal clear. Aug 10 comment Practical use of probability amplification for randomized algorithms 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. Aug 10 revised Practical use of probability amplification for randomized algorithms added 17 characters in body; added 24 characters in body Aug 10 comment Practical use of probability amplification for randomized algorithms actually, it doesn't say that we can replace an inverse polynomial by an inverse exponential. Aug 10 revised Practical use of probability amplification for randomized algorithms edited body Aug 10 comment Practical use of probability amplification for randomized algorithms 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. Aug 10 asked Practical use of probability amplification for randomized algorithms Aug 8 revised A language complete for NP intersection co-NP added 343 characters in body; added 4 characters in body Aug 8 comment A language complete for NP intersection co-NP @Ryan: also, what would be the consequences of having complete problems for $NP\cap coNP$?