A puzzle courtesy of Mohan Paturi:
Monday, June 21, 2010
Posted by Mihai at 10:27 PM
Wednesday, June 9, 2010
There is a fraction of our community who is in love with the idea of publishing in journals, and would like to see our conferences go away or assume a radically different role. In many of the cases, it seems to me that the driving force behind this idea is nothing more than snobbery. Basically, the argument goes like this: (1) I think Mathematicians are cool; (2) Mathematicians publish in journals.
- The authors thought seriously about it and wrote down all the details. Regardless of what you think about journals, this should already be achieved at conference level. Yes, a conference is an announcement -- but I care when you announce "I've done this!" rather than "I'm reasonably sure I can do this." It is beyond my comprehension why conferences do not require full proofs (despite several successful attempts in the past).
- Interested people read it. Yesterday, Timothy Chan sent me a breakthrough paper. Between giving two talks, kayaking on the Charles, and driving back from STOC, I really couldn't read it. But today I read it, and flipped it upside down in my mind until I got it. The value of putting such a paper in a journal? (cdr '(a))
Posted by Mihai at 10:02 PM
Wednesday, June 2, 2010
On a binary computer, you can represent a vector of N decimal digits using ⌈N·log210⌉ bits, and support reading/writing any digit in constant time.Of course, this works for any alphabet Σ; decimal digits are just an example.
- I have two symbols from alphabet B+1. I need an output alphabet of B, so let's split them into a letter from B, and whatever is left (in particular, a letter from B+3).
- I have a letter from B+3. Can I combine it with another letter to make something close to a power of 2? Yes, I should use a letter from alphabet B-3, since (B+3)(B-3) is close to B2.
- How can I get a letter from B-3? Take the next two input symbols, and split them into a letter from B-3, and whatever is left (in particular, a letter from B+6).
Posted by Mihai at 3:14 PM
- A code of 2N bits: after each data bit, append one bit that is 0 for end-of-file (EOF) or 1 if more data is coming;
- A code of N+2lg N bits: at the beginning of the message, write N by code 1; then write the bit vector.
- A code of N+lg N+2lglg N bits: at the beginning, write N by code 2; then write the bit vector.
- Recursing, one obtains the optimal size of N+lg N+lglg N+...+O(lg*N)
- Split: Two input symbols in alphabet B+1 are changed into two symbols in alphabets B-3i and B+3(i+1), for i=0,1,2,... This works as long as (B-3i)(B+3i+3) ≥ (B+1)2, which is always the case for n2 ≤ B/4 (hence the assumption b≫2lg N).
- Merge: Two input symbols in alphabet B-3i and B+3i are regrouped into two symbols in alphabet B, which can be written out in binary (b bits each). This is always possible, since (B-3i)(B+3i) ≤ B2
Posted by Mihai at 1:32 PM
Tuesday, June 1, 2010
MADALGO is organizing a Summer School on Geometric Data Structures on Aug 16-19 in Aarhus, Denmark. Registration and local food are free (with a capacity limit), but you have to get there on your own dime.
Posted by Mihai at 1:42 PM
Posted by Mihai at 10:15 AM