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.