Blog

How hard in unshuffling a square?

A shuffle of two strings is formed by interspersing the characters into a new string, keeping the characters of each string in order. For example, MISSISSIPPI is a shuffle of MISIPP and SSISI. Lets call a string a square if it is a shuffle of two identical strings.

In November 2012, Sam Buss and I have succeeded in proving that the problem of determining whether a string can be written as a square shuffle is NP complete. This applies even over a finite alphabet with only 7 distinct symbols, although our proof is written for an alphabet with 9 symbols. This question is still open for smaller alphabets, say with only 2 symbols.

This problem was first posted on the CS Theory Community Blog in August of 2010. The problem received a lot of attention at the Theoretical Computer Science StackExchange. Our solution has been published in December 2013, the Journal of Computer and System Sciences:

http://www.sciencedirect.com/science/article/pii/S002200001300189X

(here is the corresponding StackExchange post)

Making the Web Faster with HTTP 2.0 – ACM Queue

A modern Web application looks significantly different from a decade ago. According to HTTP Archive,6 an average Web application is now composed of more than 90 resources, which are fetched from more than 15 distinct hosts, totaling more than 1,300 KB of (compressed) transferred data. As a result, a large fraction of HTTP data flows consist of small (less than 15 KB), bursty data transfers over dozens of distinct TCP connections. Therein lies the problem. TCP is optimized for long-lived connections and bulk data transfers. Network RTT (round-trip time) is the limiting factor in throughput of new TCP connections (a result of TCP congestion control), and consequently, latency is also the performance bottleneck for most Web applications.

via Making the Web Faster with HTTP 2.0 – ACM Queue.