Reputation
Next privilege 200 Rep.
See reduced ads
Badges
1 9
Impact
~12k people reached

  • 0 posts edited
  • 0 helpful flags
  • 37 votes cast
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$?