Reputation
893
Top tag
Next privilege 1,000 Rep.
Create tags
Badges
11 23
Impact
~27k people reached

Mar
12
awarded  Notable Question
Feb
11
comment Solve by induction: $n!>(n/e)^n$
Related question: math.stackexchange.com/q/144176/2420
Dec
20
awarded  Constituent
Dec
9
awarded  Caucus
Dec
1
awarded  Altruist
Nov
30
comment Understanding the complexity class $P^O$ for randomized oracles
Oh, I see. Thanks for the magical explanation, it's now crystal clear :)
Nov
30
comment Understanding the complexity class $P^O$ for randomized oracles
I believe $M$ cannot simply return the answer of the $BPP$ oracle. For the oracle, it is acceptable if it decides the language membership with probability better than (say) 2/3. However, the deterministic machine $M$ should "perfectly" decide the membership: It should output 1 if and only if the input belongs to some language.
Nov
30
comment Understanding the complexity class $P^O$ for randomized oracles
Please clarify this point: $M^O$ is a deterministic machine if $M$ is a deterministic machine. So, shouldn't $P^{BPP}$ be a deterministic complexity class?
Nov
26
awarded  Investor
Oct
11
awarded  Yearling
Jul
2
awarded  Curious
May
24
answered what is the relationship between the complexity class E(and EXP) and NP?
May
7
awarded  Notable Question
Feb
16
awarded  Good Question
Nov
16
awarded  Popular Question
Nov
3
awarded  Nice Question
Oct
11
awarded  Yearling
Sep
23
asked A tight lower bound for the entropy of the XOR of two random variables
Sep
8
awarded  Popular Question
Aug
27
accepted A simpler proof for an equality regarding sums of absolute values