bio | website | wonder2.naist.jp/~villagra-m |
---|---|---|
location | Nara, Japan | |
age | 32 | |
visits | member for | 4 years |
seen | Oct 17 '13 at 1:57 | |
stats | profile views | 360 |
I'm a graduate student at Nara Institute of Science and Technology studying theoretical computer science. My main interests are in computational complexity theory and quantum computing.
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$? |
Aug 8 |
comment |
A language complete for NP intersection co-NP
@Ryan: OK, I understand. Then, what do we need to proof collapsing in the polynomial hierarchy in general? |
Aug 8 |
comment |
A language complete for NP intersection co-NP
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. |