150 reputation
17
bio website wonder2.naist.jp/~villagra-m
location Nara, Japan
age 32
visits member for 4 years
seen Oct 17 '13 at 1:57
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.