New answers tagged


Being a web developer, I am sure you realize that most large scale websites contain at least one of databases, high availability server, front end design, an algorithm of some sort, etc. Each of these areas has an active research community. Database researchers mostly study data structures and algorithms that speed up database operations. UI/UX researchers ...


This is called "output entropy". Suppose you have a communications channel that takes a string and then outputs a random string within a relative $\delta$ radius of it. If you use the input distribution $X$ for communicating over this channel, the entropy of the output distribution would be the quantity you are after.


Suppose Alice always sends exactly $k$ bits to Bob during the protocol. On average, how many possible candidates for her $n$-bit string are consistent with the communication transcript? What does that tell you about the probability that Bob guesses which one of those candidates is the correct one?


For a fixed alphabet $\Sigma$, the blow-up is at most polynomial. First, given a regular expression $r$, it is straightforward to construct an expression $\tilde r$ using the operators $a\in\Sigma$, $+$, $\cdot$, $(-)^+$, and $\let\nul\varnothing\nul$ such that $$L(\tilde r)=L(r)\let\bez\smallsetminus\bez\{\let\ep\varepsilon\ep\}$$ recursively, by putting $\...

Top 50 recent answers are included