Hi all,

Can you help me test our implementation of the Fast Hadamard Transform? It will take you a couple of minutes provided that you have modern enough C and C++ compilers. I'm especially interested in testing it under OS X and 32-bit systems.

You would need to have gcc that would compile C99 and g++ that would compile C++11. Also, you would need make to build everything.

What you need to do:

1. Tell me your OS and CPU.
2. Download the code from http://ilyaraz.org/fht.zip and unzip.
3. Run "make", tell me if something does not compile.
4. Run "test", make sure it does not fail. Tell me, if it fails.
5. Run "best_chunk" with n = 1024, 1048576, 134217728 and send me the outputs.

Thanks! Ilya

Hi all,

I'm about to teach AVL trees for a section of 6.006, and while thinking it through, I came up with the following question, which, I strongly suspect, should be well-understood.

Say one wants to maintain a binary search tree with height , where n is the total number of nodes, under insertions. How quickly can one insert? Is time per insert possible?

For instance, AVL trees achieve height around and red-black trees — .

What do you think?

Hi everyone!

We have just started a student blog of MIT Theory of Computation Group. If you are curious to read or gossip about "real" research in Theoretical Computer Science or life of graduate students, feel free to sign up!

• Blog: http://mittheory.wordpress.com
• RSS: http://mittheory.wordpress.com/feed
• Twitter: https://twitter.com/notsogitcs

The blog is run by:

• Alon Cohen
• Ilya Razenshteyn
• Aaron Sidford
• Prashant Vasudevan
• Henry Yuen