This is a few days late, but I thought it too good not to share: Automatic Proof of Reimann’s Hypothesis?
Since it’s past April fools, I’m comfortable giving the punchline away, but I’ll admit that I was totally suckered in till I read the comments.
I recently got nerdsniped by the following question: Let 
It’s not true. Here’s a counterexample: Consider the dihedral group 
Let 
On the other hand, observe that, by the same analysis, 
Thanks to Tanay for the clarifying discussion!
This term, I’m attending Madhu Sudan’s delightful course on Algebra and Computation. It’s truly a treat — the last time he taught this course was back in ’05! Algebra seems to offer some really high quality tools (perfected over hundreds of years!) to attack many problems in TCS these days. Indeed, Michael Forbes remarked to me recently that he views these days as “the second coming of algebra to theoretical computer science” (the first being the flurry of algebraic algorithms in the 70′s). Well, if that’s the case, then all ye non-believers, you had better study up!
Madhu is also introducing the web 2.0, social media paradigm to the course, by maintaining a class blog. Add it to your feeds! So far, Madhu has solicited us for “an algorithm that surprises us most.” Check out what people find surprising, and why. As for myself, after agonizing for quite some time I eventually settled on the Moser-Tardos algorithm for the Constructive Lovász Local Lemma. My explanation/ramblings are reproduced below:
The Constructive Lovász Local Lemma, and Why I Like It
One of the most potent tools in combinatorics and theoretical computer science is the probabilistic method, where objects can be proven to exist “simply” by arguing that they probably exist. Some prominent applications of the probabilistic method include Shannon’s Noisy Coding Theorem, pseudorandomness, and circuit complexity (e.g. there exist functions with high circuit complexity). One of the main techniques of the probabilistic method works as follows: to show that an object with property 
The last time I introduced one way functions (OWFs), and today we’ll see actually how they can be put to use. I’m going to talk about the famous Goldreich-Levin theorem, which shows how a particular class of OWFs called one way permutations (OWPs) may be used to generate a large range of pseudorandom numbers from a small (truly) random seed.
Generating random-looking numbers
Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin. – John von Neumann.
First, let’s talk about pseudorandom generators (PRGs) a little bit. Randomness is crucial to modern cryptography; without it, nothing could ever be secure! Why is that? If you only had deterministic means of encryption and key generation, then what’s to prevent a powerful adversary to run the exact same procedure as you, and either a) pretend to be you or b) read your messages. On the other hand, where can we actually get our hands on true randomness? Genuine, high quality randomness might be scarce or hard to obtain. A lot of sources of “randomness” that are used in software today are not truly random; for example, using the keystrokes of the user as a source of randomness (which some applications do) is not a good idea, because people tend to type messages with some information content in them (though you wouldn’t know it from observing the internet).
The role of a pseudorandom generator in cryptography and complexity theory is to take a small truly random seed and “stretch” it, in a deterministic fashion, into a larger number so that, to any outside observer, it looks as if you had access to a larger source of randomness to begin with. Suppose you were able to acquire 100-bit strings uniformly at random, but generating an encryption key required 2000 bits of randomness. You could use a PRG that stretches 100 bits to 2000 bits of pseudorandomness to do this key generation. To the key generating program, it would look like you had access to a source of 2000-bit strings, uniformly at random. Crucially, we have to assume that the key generator is limited in the amount of computation it can perform – usually we assume that the outside observer can only perform polynomial time computations. Otherwise, given unlimited time, the key generator could check, via brute force, whether a given 2000-bit “random” string y was the output of the PRG. However, this requires the key generator to check about 2100 strings, which would take quite a while. A crucial component of a PRG is that it be efficiently computable. Generating pseudorandom numbers is of no use if it takes several billion years to compute. Continue reading
One of the smoother pebbles I’d like to share today is the concept of a one way function, and the Goldreich-Levin Theorem. These two concepts are central to complexity theory and foundations of cryptography, subjects that have been on my mind a lot recently.
Modern cryptography is mainly concerned with the idea that we should come up with ways to communicate secrets that are as secure as possible against any adversary, provided that they only have access to the encrypted messages, and not your encryption keys. Your adversary may have legions of supercomputers at their disposal (cough NSA cough) and full knowledge of the algorithms you’re using — but your secret will stay a secret long after the last stars in the universe have winked out. Of course, we’re ignoring the (very practical) possibility that the adversary with such powers can just as easily send goons to your house and strong arm the encryption key from you, but that’s outside the idealized models used in cryptography 
. The oft-used analogy is that a secure cryptosystem should be like a safe that’s impervious to anybody who doesn’t know the safe combination, even if that person has the safe blueprints, tons of time, and the best power tools in the universe. But if you have knowledge of just a few numbers, the safe will easily and gladly swing open to reveal the treasures inside. Continue reading
The title of this blog, of course, refers to one of Newton’s immortalized quotes:
I do not know what I may appear to the world, but to myself I seem to have been only like a boy playing on the sea-shore, and diverting myself in now and then finding a smoother pebble or a prettier shell than ordinary, whilst the great ocean of truth lay all undiscovered before me.
His perspective on the process of discovery is one also shared by my former adviser at USC, Len Adleman, who said that, with respect to research, we’re all just ants who crawl around with little to no sense of the greater world beyond us, finding a speck of sugar here and there. Of course, some ants – Gauss, Newton – were luckier than others, but ultimately they’re just ants. The best we can do is skitter around this strange, enormous universe, find some sugar pieces here and there, and maybe even discern a faint pattern connecting them.
It seems appropriate that I start a new blog; transitioning from high school to college merited a restart, and I think now is a good time to launch version 3. Over time, I hope to share with you a few gems, or a smoother pebble that I find in my wanderings.
