The RSS feed of the CSTheory Community Blog was broken for a couple weeks. Thanks to Jukka Suomela, we discovered this (just recently), and the feed is now valid again. Here are the posts that appeared while the feed was down.
- Lower Bounds by Negative Adversary Method, by Artem Kaznatcheev. Artem provides a technical introduction to proving lower bounds in quantum query complexity, by using the new technique of the negative adversary method. He contrasts it with the older technique of the polynomial method.
- If a family of forbidden subgraphs is hard, does that imply that the graph class is hard? Written by me. I consider a question asked on CSTheory: is there a relationship between the computational complexity of recognizing a forbidden family of subgraphs, and the computational complexity of the graph class defined by the forbidden family? Hugo Nobrega gave an inspired answer to this question, but ultimately, things are not fully resolved. An intriguing “open problem” for people interested in graph minors and forbidden subgraphs.
- Happy birthday, cstheory! Written by Suresh Venkatasubramanian. Suresh reviews some of the open problems, original proofs, career advice and technical discussions that have appeared on cstheory.stackexchange.com since it was founded Aug 16, 2010.
- On Learning Regular Languages, by Lev Reyzin. Lev gives a technical introduction to learning theory applied to regular languages, for example, whether it is NP-complete to find the minimum regular expression that captures a regular language. He considers multiple learning models and mentions open problems.
I hope you enjoy the posts!
As always, we are looking for one-time or regular contributors for the community blog. The following is new: we would like to start a regular “column” of Conference Reports, where TCS’ers report, either formally and technically, or informally and more personably (or both), about conferences they are currently attending. We already have one correspondent for ESA (European Symposium on Algorithms) (thank you Dave!), which starts September 5th, but it is a large meeting and additional perspective(s) would be welcomed. If you would like to blog about a TCS conference or workshop you will be attending, please get in touch with me or Joe Fitzsimons, or add your name to the Community Blog Contributor Signup Sheet. Thank you.
(UPDATE: My statements in this blog entry about the Göös Orponen paper were based on an earlier draft, which was on an author’s web page, but was not the final, published version. I have updated the link to their paper, and struck out my statements that are not consistent with their final draft. In particular, the final version of their paper reads, “Ma & Lombardi show a certain derivative of the above optimization problem NP-hard in . However, to our knowledge, a proof of the NP-hardness of the PATS problem as stated above is lacking.” Please see the comment of Mika Göös below for more information.)
One of my research interests is the DNA self-assembly of multicolored shapes. Almost all DNA self-assembly literature — both theory and practice — has focused on the assembly of either 1-color or 2-color shapes. Nevertheless, if we think of the DNA assembly as a substrate, or scaffolding, upon which transistors or nanomachines are placed later, different colors can correspond to OR gates or NAND gates, or the “landing pads” of much more sophisticated objects. A while back, I did a literature search on the self-assembly of multicolored shapes, and I thought I “knew everything” that was currently in the literature. However, I was wrong. I recently discovered papers in the literature track of Computer Assisted Design of integrated circuits (a track I had never followed before, and clearly I will have to start), whose objective is to tackle DNA self-assembly of multicolored rectangles, an obviously related special case of “my” problem. I will discuss two of these papers in this blog entry.
The two papers, both by Xiaojun Ma and Fabrizio Lombardi of Northeastern University, are On the Computational Complexity of Tile Set Synthesis for DNA Self-Assembly, and Combinatorial Optimization Problem in Designing DNA Self-Assembly Tilesets. The second is much shorter, reads like an announcement of results, and appeared in a workshop. The first appeared in a journal and contains a full proof of an NP-completeness result. I had initially intended this blog entry to be a technical discussion of the NP-completeness result, which I find clever, and I think it defines a graph model of tilesets that might be useful in other settings. However, when I looked into the literature, I found things were a bit of a mess.
A subsequent paper by other authors incorrectly states that Ma and Lombardi proved something stronger than they actually did, and this error is understandable, because Ma and Lombardi changed the informal description of their theorem in between the workshop paper and the journal paper. (The workshop paper makes a stronger claim, which the journal proof does not support.) So the rest of this entry reads more like a detective story — or a he-said she-said dialogue (!) — than an exposition. It took me a couple days to separate claims from proofs, and I hope that, by writing this up, I will save other researchers some time.
The list of accepted papers for the 17th International Conference on DNA Computing and Molecular Programming is now up. This isn’t breaking news, but I haven’t seen it mentioned on other theory blogs, so I figured it was worth posting.
Some of these papers, and ones they cite, will be my blogging focus over the next few weeks.