The law of excluded middle

When it comes to anonymity on the Internet, we may face with the situation where there’s no middle ground between complete anonymity and control.

We could have anonymity through trusted authority. For example, I may trust google, yahoo, microsoft, my ISP, my blog providers, and other entities not to expose my real identity. This kind of anonymity is easy to obtain, but the question is can we trust them?

In Thailand, there’s computer crime act law that forces ISPs and content distribution sites (e.g., sites providing web discussion boards) to keep access logs for 90 days. If you post something, the police can trace back to you. Unless you do something clever about the way you post.

Yes, you can trust the web sites, but they can’t help you in this case because they’ll also get fined. The site can host the content abroad, but if the site owners (or operators) is in Thailand, they’ll be charged as well. (And, the fine is not so small; also, the police could put them in jail.)

You can use sophisticated platforms, e.g., Tor network. In this case you trust the design of the system that even when intermediate parties try to disclose your identity, you’ll be safe. (However, if large fraction of the nodes in the network try to identify you, they probably can.)

In the case of (sort of) complete anonymity, we face a situation where one can use this “freedom” to attack others.

I can’t see the middle ground. Do you see some way to get around this? If not, which way do you like? Who can we trust? And, if there’s no one we can trust, how can we deal with the case of complete anonymity?



Yesterday I taught a bunch of smart high-school students at the national preparation camp for IOI.

I covered a bunch of topics, including a very nice proof of Sperner’s lemma.

At some point, we were talking about the k-th harmonic numer H_k, which can be defined as H_k = \frac{1}{1} + \frac{1}{2} + \cdots + \frac{1}{k}.

Most students know that it is about O(\log k), but they don’t know the proof.

The proof is, however, quite simple.

For simplicity, assume that k+1 is a power of two, i.e., k = 2^a - 1 for some positive integer a.

We group terms in the sum like this:

\left(\frac{1}{1}\right) + \left(\frac{1}{2} + \frac{1}{3}\right) + \left(\frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7}\right) + \cdots + \left(\frac{1}{2^{a-1}}+\cdots+ \frac{1}{2^a - 1}\right).

Note that each group in the sum is at most 1 and at least 1/2. And we have \log(k+1) groups.

Thus, this shows that \frac{1}{2}\cdot\log(k+1)\leq H_k\leq\log(k+1) when k=2^a - 1 for some positive integer a. Now, to get to general k should be an easy exercise.

A more accurate estimate for H_k is \ln k + \gamma where \gamma is the Euler-Mascheroni constant (see wikipedia article).