MIT has a lunch for students and professors in the Theory of Computation group, where one can eat pizza and here other people’s casual open problems. Sometimes really cute problems and/or discussions fall out. Today (non-exhaustive):

• Alexandr Andoni asked — Consider the following Shifted Hamming (SH) distance on bit strings. The distance between two strings is defined as the Hamming distance after shifting (really rotating) one of the strings by an arbitrary amount (which produces the smallest Hamming distance). The questions are. Can we embed the SH metric into the Hamming metric with low distortion? If I am not mistaken, Alex knows a lower bound on the distortion of O(log n) using a Fourier argument. And, can we embed SH into (the squared Euclidean norm)? I believe no lower bound is known here and O(1) may be possible.
• Ron Rivest is working on an intentionally very simple election auditing system, which hinges on a pseudorandom function that can be computed on a handheld calculator in a few strokes. The detailed description of the procedure is on his website (I couldn’t find, but it is there!). Ron asked if there are any obvious attacks/problems with his design. His question brought up a somewhat simpler question that seems very curios to me: Pick a random integer between 1 and 1000, take its square root, and consider the first bit of its fractional part. How far is the distribution of that bit from uniform?