There is a new post category on the CSTheory StackExchange Community Blog — Conference/Workshop Reports — and Dave Pritchard (who often goes by the nick daveagp online) has just posted the first such report, covering the sixth annual meeting of EuroComb in Budapest, a conference in honor of Gyula Katona’s 70th birthday, and the European Symposium on Algorithms (ESA), which is part of ALGO this year (so the link points there). Dave’s post is excellent, thank you very much!
I mentioned recently on this blog that we are looking for more people who can blog from conferences and workshops they attend, but there is a new wrinkle. StackExchange has just inspired a formal policy of sponsoring (some) site bloggers who attend conferences. (See this post, especially the section “Sponsoring Community Leaders to Attend.”) Further, Jeff Atwood, founder of StackExchange, just posted on the CSTheory meta site, encouraging theoretical computer scientists to take him up on this. Suresh Venkatasubramanian has started a thread, looking for reporters for the upcoming FOCS.
Here are five other conferences that are starting soon; all have a significant TCS component (with TCS broadly defined).
- Conference on Computer Science Logic (Sept 12-15)
- International Conference on Functional Programming (Sept 19-21)
- International Conference on DNA Computing and Molecular Programming (Sept 19-23)
- International Symposium on Distributed Computing (Sept 20-22)
- International Symposium on Graph Drawing (Sept 21-23)
Anyway, you get the idea, I’m sure. I just wrote someone who will be at DNA, asking about blogging. If you will be attending an upcoming TCS event — or if know someone who will be, please share this information — please contact Joe Fitzsimons or me, or leave an answer on Suresh’s thread. Thanks.
UPDATE: The site has reached 100% commitment, and is about to launch a beta Q&A period.
There is an active proposal at StackExchange to build a research-level Q and A site for theoretical physics. There is a Physics StackExchange site already, for questions at the high school or undergraduate level. The new site would be expert-level only, like MathOverflow for math, or CSTheory for theoretical computer science.
The new site is currently in the “commitment” phase, meaning more people need to add their names to a list of individuals who want to participate in the site when it does live. If enough people commit (at 79% of requirement as I write this) the site will enter a “private beta” phase, where only those who committed will be able to ask and answer questions for a while.
More information, and the commitment page, is here.
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.
In a previous post, I considered a proof of the Church-Turing Thesis that Dershowitz and Gurevich published in the Bulletin of Symbolic Logic in 2008. It is safe to say that the proof is controversial — not because it is technically inaccurate, but because it relies on an axiomatization of computation that excludes randomness, parallelism and quantum computing. (For more discussion of that paper, please see the previous blog entry, or the question about disproving the Church-Turing Thesis on CSTheory.) Nevertheless, one of the authors, Dershowitz, and his PhD student Falkovich, have just published a proof of an even more controversial statement, the Extended Church-Turing Thesis. It is this new proof which I will now discuss.
The Extended Church-Turing Thesis is the statement that every physically realizable computational device can be simulated efficiently by Turing machines. (By contrast, the “mere” Church-Turing Thesis says that Turing machines can simulate any computational device, but perhaps at the cost of an exponential blowup in time and/or space.) Unlike the Church-Turing Thesis, which computer science convential wisdom appears to think is true, many CS people believe the Extended Church-Turing Thesis to be false, because quantum computers are expected to be strictly stronger than classical computers. (The most famous example of this difference in strength is a quantum algorithm that can factor large integers in polynomial time, due to Peter Shor. Most CS people believe that classical computers cannot factor integers in polynomial time, and many cryptography programs depend on this infeasibility.) Dershowitz and Falkovich sidestep this issue by attempting to axiomatize only “classical” algorithms — no quantum, no randomization, no massive parallelism. They define an algorithm’s implementation, a program, an efficient program, and then prove that any efficient program (in their general axiomatic sense) can be simulated in linear time by a Random Access Machine (RAM). Since a RAM can be simulated efficiently by a Turing machine, the Extended Church-Turing Thesis follows as a consequence. Continue reading
The first technical post is now up on the CSTheory Community Blog. It is Quantum Query Complexity, by Artem Kaznatcheev. Artem is currently working on a followup post on the “negative adversary method,” a fairly recent proof technique in quantum computing, which we will post there soon.
I hope you enjoy the new blog! I think this is a great first post. Thanks very much, Artem. And, everyone else, if you would like to participate, either on a one-time basis, or regularly, please add your name to the blog contributor signup sheet, or email me or Joe Fitzsimons directly. Thank you.