Impact
~10k
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$? |