Computer Science

« first day (1814 days earlier) ← previous day next day → last day (2631 days later) »

donald

4:15 PM

does anyone know a reference for the first line of cstheory.stackexchange.com/questions/22328/… ?

"It is well known that the complexity of distinguishing an[...]"

1 hour later…

Computer Science Meta

5:43 PM

Q: Are questions on blockchains on topic?

Just wondering if questions regarding blockchain technology are on topic? From the help link: This site covers theoretical and applied computer science at any level.. I'd categorise blockchains as applied computer science, and there are a few questions on it already, so I'd say questions a...

Auberon

@D.W. That makes sense. Thanks

D.W.

6:47 PM

@donald I don't know a reference, but you can derive it yourself by calculating the mean and variance of the number of heads, after n tosses of a coin with heads probability p. Now we want to distinguish that distribution for p = (1+\epsilon)/2 from that distribution for p = 1/2. For them to be distinguishable, you need the difference between their means to be some constant multiple of their standard deviations. Work through the calculation, and you can re-derive the result.

Maybe try doing the calculation, and then if you get stuck, ask a question here on CS.SE showing how far you got?

Actually, looking through my answer there, I see that I actually gave the derivation. Look at the stuff after the horizontal line, plug in p = 1/2, and follow the derivation I showed there.

Bounty!

7:41 PM

Q: Ranked alphabet issue

Ranked alphabet is very often used in Ranked Trees definition, like here for instance. In that example for given set $\Sigma=\{a,b,c\}$ ranks assigned by arity function $ar : \Sigma\rightarrow\mathcal{N}$ as: $ar(a)=2, ar(b)=2, ar(c)=1$. And Ranked Tree over $\Sigma$ is defined as: $T_{\Sigma_...