Author Archive

I attended the 62nd Midwest Theory Day last Sunday, November 13rd. Usually there are two such theory days each year, but this was the only one in 2011. The event is like an informal workshop: anyone who wishes may sign up to speak, there are also invited speakers, lunch is provided, and there is no proceedings. Nicole Immorlica organized the event, and did a great job: there was a full day of talks, the room was great, the food was as good as any conference I’ve been to, and the invited speakers were entertaining and educational. 

Yael Tauman Kalai gave the first invited talk.  She gave a high-level overview of some hot topics in cryptography.  For example, she provided intuition into results she and co-authors obtained about designing systems whose algorithms resist physical attacks on cryptosystems.  A dramatic physical attack is someone who wants to break into a SIM card, so cooks it in a microwave oven for a while; this can cause bits to flip in the secret key, and even modify the circuitry of the SIM card itself.  (Some other examples of physical attacks are here.) Tauman Kalai presented a formalism in which the attacker could determine the system’s secret key, but would still be unable to produce a second secret key matching the system’s public key, unless the attacker used exponential resources or broke a reasonable cryptographic assumption.  For a system that can defend itself against an adversary capable of obtaining continual memory leakage of the system, see the FOCS 2010 paper Cryptography Resistant to Continual Memory Leakage (co-authors Brakerski, Katz, Vaikuntanathan).

Adam Kalai was the other invited speaker; he provided an overview of his ITCS 2011 paper Compression Without a Common Prior: an Information-Theoretica Justification for Ambiguity in Natural Language (co-authors Juba, Khanna, Sudan).  His talk was controversial: quite a few members of the audience either didn’t get his point, or got it and didn’t agree.  The idea, as I understand it, is to produce a mechanism two computers can use to compress and decompress messages they send to each other, even if their respective compression dictionaries (or “priors”) are different.  The motivation is how natural language works: you and I don’t have the same definitions for all words (and very different life experience) and yet we can communicate pretty well most of the time (for purposes of the example anyway).  If the message is large enough, one could of course use an algorithm like Lempel-Ziv, which approches best-possible compression in the limit.  But perhaps we just want to send one image, instead of thousands, and we would like to take advantage of the fact that both computers have useful priors for what an image is, even if those priors are not the same.  The paper provides an information-theoretic framework for this, but there is, as yet, no implementable algorithm.

There was also a day full of 15- and 20-minute talks by students, postdocs and faculty.  I will completely arbitrarily limit myself to the talks of the two people who sat on either side of me at lunch.  Fortunately, I thought both their talks were great.

Paolo Codenotti presented some brand new work on the group isomorphism problem: Polynomial-Time Isomorphism Test for Groups with no Abelian Normal Subgroups (co-authors Babai, Qiao).  This work extends the SODA 2011 paper Code Equivalence and Group Isomorphism (co-authors Babai, Grochow, Qiao).  The problem solved is the following: let $latex G$ be a group on $latex n$ elements, given to us as its multiplication table of size $latex n^2$.  Let $latex H$ be another group on $latex n$ elements, given in the same way.  If we know that $latex G$ and $latex H$ contain no normal subgroups that are abelian (i.e., commutative), then we can determine whether $latex G$ and $latex H$ are isomorphic in polynomial time.  One example of such a group is $latex A_5$, the alternating group on 5 elements, which has order $latex n=60$.  Another example would be any group built from direct sums of copies of $latex A_5$.

Tyson Williams gave an overview of his ITCS 2011 paper, Gadgets and Anti-Gadgets Leading to a Complexity Dichotomy (co-authors Cai, Kowalczyk).  Williams has also posted his slides from this talk online.  This paper is in the general category of holographic algorithms, a remarkable subfield of counting complexity started by Les Valiant and explored by Jin-Yai Cai, Williams’s advisor.  Since the slides are online, and the intuition behind the paper’s approach is so visual, I will let the slides speak for themselves, and close this post by simply stating the paper’s main theorem.

Theorem. Over 3-regular graphs $latex G$, the counting problem for any binary, complex-weighted function $latex f$,  $latex \displaystyle Z(G) = \sum_{\sigma:V \rightarrow \{0,1\}} \prod_{(u,v) \in E} f(\sigma(u),\sigma(v))$ is either polynomial-time computable or #P hard.  Furthermore, the complexity is efficiently decidable.

 The formalism of $latex f$ captures a wide variety of problems on 3-regular graphs, such as #VertexCover (how many vertex covers are there for the input graph), which is #P hard.

Many CSTheory people probably know there is a new StackExchange Q&A site, Theoretical Physics, which is now in public beta, and was originally started by Joe Fitzsimons, co-editor of this blog.  My purpose for this post is to give TCS people a heads-up that there are now 16 questions on that site under the quantum-computing tag and the quantum-information tag that may be of interest to theoretical computer science.

My favorite of these questions is Rigorous Security Proof for Wiesner’s Quantum Money?  In this question, Scott Aaronson asks for an explicit upper bound on a value that is “known to exist” according to folklore, but that he and a co-author were unable to find in the literature or derive. Master’s student Abel Molina solves the problem, using a formalism of Gutoski and Watrous.  John Watrous then verifies the solution’s correctness.  There are also contributions by Dan Gottesman and Peter Shor.

In related news, there is now a proposal for a Quantum Information question and answer site on the Stack Exchange Area 51.  This proposal is (mildly) controversial, though, because some people are concerned it would duplicate topics already available on Theoretical Physics.

There is a new page to this blog: Theoretical Computer Science Conferences and Workshops.  It provides names and links to theory venues — with theory broadly defined, including, for example, the theory of programming languages, which is usually considered outside the SIGACT purview  (EDIT: see comments).  This page is the result of dozens of contributions to a community wiki question on CSTheory, and Joe and I would like to thank everyone who participated.

Those interested in lists of TCS venues may also want to check out Microsoft Research’s list of computer science conferences.  That list considers all of CS, not just theory, and provides some added information, like citations per conference.  The list on this blog contains some conferences that the MR list does not.

If you see errors, or can think of useful additions, please comment here or on the new page, or edit the community wiki answer that contains the conference information.  Thanks, and we hope you find this helpful.

Almost exactly one year ago (10 Sept 2010), Cem Say asked the following deceptively simple question:

Is the language $latex \{ a^{i}b^{j}c^{k} \mid  i \neq j, i \neq k, j \neq k \}$ non-context-free?

Recall that a language is context-free if it can be accepted by a pushdown automaton.  A pushdown automaton, in turn, is a finite automaton with access to a stack (so it has access to an unbounded amount of memory).  A standard example of a context-free language that cannot be recognized by a finite automaton without a stack is {$latex a^n b^n \mid n \geq 1 $}.  If a finite automaton has no access to a stack, it cannot store the value of $latex n$ if $latex n$ gets too large, so it has no way to be certain that the number of $latex b$ appearing exactly match the number of $latex a$.  This intuition is formalized in the famous pumping lemma; and there is a similar tool, the pumping lemma for context-free languages, that can be used to prove that a language is not context-free.

It is easy to apply a standard technique — the pumping lemma — to show the language Cem Say asked about is not regular.  (We make the exponents large enough that a finite automaton has to repeat a state, and take advantage of that confusion.)  However, there doesn’t appear to be a good way to apply the pumping lemma for context-free languages to show this particular language is context-free.  Initially, though, some site members thought the question was easy enough to be undergraduate homework, since the definition of the language is so close to other languages whose status can be resolved with a pumping lemma.

Fortunately, Frank Weinberg knew about Ogden’s Lemma, which is an extension of the pumping lemma for context-free languages (the pumping lemma is a special case of Ogden’s Lemma).  With this tool, he was able to prove that, indeed, the language Cem Say asked about is not context-free.  The proof I will give in this blog entry can be found in Frank Weinberg’s answer; I will give a version of the proof polished by Tsuyoshi Ito in the comments to that answer.

First, here is a statement of Ogden’s Lemma.

 Ogden’s Lemma: If $latex L$ is a context-free language, then there exists some number $latex p>0$ such that for any string $latex w$ of length at least $latex p$ in $latex L$, and every way of “marking” $latex p$ or more of the positions in $latex w$, $latex w$ can be written as $latex w=uxyzv$ with string $latex u$, $latex x$, $latex y$, $latex z$, $latex v$, such that

1. $latex xz$ has at least one marked position,
2. $latex xyz$ has at most $latex p$ marked positions, and
3. $latex ux^iyz^iv$ is in $latex L$ for every $latex i \geq 0$.

The pumping lemma for context-free languages is the special case where every position is marked.  Armed with this tool, we can now prove that $latex \lbrace a^{i}b^{j}c^{k} \mid  i \neq j, i \neq k, j \neq k \rbrace$ is not context-free.

Proof (that Cem Say’s language is not context-free): For a given $latex p$, choose $latex a^i b^p c^k$ and mark all the $latex b$’s (and nothing else).  We choose $latex i$ and $latex k$ such that for every choice of how many $latex b$’s are actually pumped there is one pumping exponent such that the number of $latex b$’s is equal to $latex i$ and one where it is equal to $latex k$.  Then $latex i$ and $latex k$ have to be from the set $latex S= \bigcap_{1 \leq n \leq p} \lbrace p-n + m*n \mid m \in IN_0\rbrace$ where $latex IN_0$ is the set of positive integers.  The set $latex S$ is infinite, because it contains $latex p+ im$ for all $latex i \geq 0$, where $latex m$ is the least common muiltiple of $latex \lbrace 1, \ldots, p \rbrace$.  So, assuming the language is context-free, we can always find an $latex i$ and $latex k$ in $latex S$ for any $latex b$, and by condition (3) of Ogden’s Lemma, the resulting string will be in $latex L$, contradicting the original definition of $latex L$.  So the language cannot be context-free after all.

For questions and answers on related topics, click on the formal languages tag.

In previous posts about graph minors, we reviewed the definitions of graph minors and topological minors, then looked at a relationship between the two; and explored whether there was a relationship between the computational hardness of a set of forbidden subgraphs and the graph class defined as all graphs that avoid the set of forbidden subgraphs.  Both of those questions are fundamentally related to the Graph Minor Theorem of Robertson and Seymour.  Today, I’d like to take a step back and look big-picture at the Graph Minor Theorem, and its relationship to computer science, by featuring an answer Timothy Chow gave to a question Ryan Williams asked about the role of the Axiom of Choice in TCS.

Ryan’s question, which he asked in October 2010, was, “What interesting theorems in TCS rely on the Axiom of Choice (or, alternatively the Axiom of Determinacy)?” The Axiom of Choice, of course, is a (sometimes controversial) axiom extending Zermelo-Fraenkel set theory, and at this point is generally accepted as part of the foundations of mathematics.  Intuitively, the Axiom of Choice says that anytime you have a mathematical construction in which there is a set of nonempty bins, then it is legal to produce a set that contains exactly one item from each bin.  While this might seem “obviously true,” once this intuition is applied to infinitely-many bins, there are nonconstructive and perhaps counter intuitive consequences.  So it is natural to wonder, in the world of TCS where the sets of bins we encounter are unlikely to be “pathologically infinite,” whether we really need the Axiom of Choice to prove anything.  (I won’t discuss the Axiom of Determinacy, except to say that it is consistent with the Zermelo-Fraenkel axioms, but inconsistent with the Axiom of Choice, and set theorists sometimes put it forth as a “better” axiom, but it has not been widely accepted by mathematicians outside of logic.)

Janne Korhonen answered Ryan’s question by noting that the proof of the Graph Minor Theorem fundamentally uses Kruskal’s Tree Theorem, which in turn uses the Axiom of Choice.  A fine answer, and one might think that was the end of the story — but one would be wrong, as Timothy Chow demonstrated in a followup answer which I will now quote from.

What about arithmetical statements whose proof requires something like Koenig’s lemma or Kruskal’s tree theorem? Don’t these require a weak form of the axiom of choice? The answer is that it depends on exactly how you state the result in question. For example, if you state the graph minor theorem in the form, “given any infinite set of unlabeled graphs, there must exist two of them such that one is a minor of the other,” then some amount of choice is needed to march through your infinite set of data, picking out vertices, subgraphs, etc. However, if instead you write down a particular encoding by natural numbers of the minor relation on labeled finite graphs, and phrase the graph minor theorem as a statement about this particular partial order, then the statement becomes arithmetical and doesn’t require AC in the proof.

So the question comes down to, “What do we really mean in theoretical computer science when we talk about a mathematical proof of an infinitary statement?”  To quote from Chow’s answer again:

Most people feel that the “combinatorial essence” of the graph minor theorem is already captured by the version that fixes a particular encoding, and that the need to invoke AC to label everything, in the event that you’re presented with the general set-theoretic version of the problem, is sort of an irrelevant artifact of a decision to use set theory rather than arithmetic as one’s logical foundation. If you feel the same way, then the graph minor theorem doesn’t require AC. (See also this post by Ali Enayat to the Foundations of Mathematics mailing list, written in response to a similar question that I once had.)

So, in the final analysis, at least in Chow’s opinion, there appears to be no example of a TCS theorem that requires the Axiom of Choice to prove.  His final suggestion to Ryan is that it may be more fruitful to ask whether there are TCS statements that require large cardinal axioms to prove, instead of the Axiom of Choice.  Harvey Friedman has apparently demonstrated some artificial examples of finitary graph theory statements that require the consistency of large cardinals to prove.  So if artificial examples exist already, perhaps natural examples are around the corner.

The previous graph theory post mentioned the concept of forbidden minors — a class of graphs that contains no minors of a particular type.  We can also, of course, consider the notion of forbidden subgraphs, in which a graph class $latex \mathcal{C}$ is defined by avoidance of another graph class $latex \mathcal{H}$: graph $latex G$ is a member of $latex \mathcal{C}$ iff $latex G$ contains no subgraph that is a member of $latex \mathcal{H}$.  A partial list of graph classes defined in this way can be found here.

Suppose the forbidden subgraph family $latex \mathcal{H}$ is finite.  If we want to check whether $latex G \in \mathcal{C}$ “all we have to do” is to confirm that $latex G$ does not contain finitely many subgraphs of a particular type, which can be done in time polynomial in the size of $latex G$.  While this has tremendous real-world applications, it also lands us in the world of “nonconstructive polynomial time”: there are graph classes that are provably characterized by finite forbidden families, and yet, we don’t know what the families are.  Moreover, there may be no reasonable way to find out, as shown by the following theorem of Fellows and Langston:

Theorem: There is no algorithm to compute, from a finite description of a minor-closed family represented by a Turing machine that accepts precisely the graphs in the family, the set of obstructions for that family.

I will turn now to a question about what happens when the forbidden family is infinite but easy (or hard) to recognize.  Nonconstructive polynomial time, and the use of finite forbidden family characterization in graph algorithms, is dealt with in more detail in many places, including Algorithmic Implications of the Graph Minor Theorem, by Bienstock and Langston.

Consider chordal graphs, which are graphs where every cycle of length four or more contains a chord, that is to say, an edge between two vertices that are part of the cycle.  So chordal graphs have a simple forbidden graph characterization: no subgraphs that are cycles of size four or more with no chords.  This is an infinite forbidden family, but one that is computationally simple to recognize.  Of course, not all graph classes are simple to recognize, which motivated Vincius Santos to ask the question 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 a remarkable answer to this question, but I wanted to blog about this question both to publicize the answer, and also because the original question remains open.  Nobrega’s answer boils down to “probably not,” though it provides a beautiful example that shows any straightforward “intuitions” will not work.  Perhaps someone reading this blog knows the answer, or has further insight.  If you know any work in this direction, please do leave a comment on the post, or on the original question.  Nobrega’s answer is brief enough that I will reproduce it in full (lightly edited).

A folk theorem is a mathematical fact that is generally known (at least by experts), even though its proof may never have appeared in print, or may be difficult to locate.  Recently, cstheory user Eli asked for a citation to a proof of the following folk theorem.

If $latex G$ is a graph with maximum degree 3 and is a minor of $latex H$, then $latex G$ is a topological minor of $latex H$.

Wikipedia mentions this to be true, and refers to Reinhard Diestel’s excellent book on graph theory.  Diestel’s book asserts its truth as well, but does not give a proof.

Graph $latex G$ is a minor of graph $latex H$, if $latex G$ can be obtained from $latex H$ by removing edges in $latex H$ and identifying the vertices that were previously the endpoints of the now-deleted edge.  So, in a sense, we can say that $latex H$ “has local structures that looks like” $latex G$ if $latex G$ is a minor of $latex H$.  It is sometimes possible to prove strong properties about the global structure of $latex H$ if we are guaranteed that $latex H$ has no minors of a certain type, because then no local area of $latex H$ can look a certain way, so it is possible to say something about the entire graph.  The most famous example of this is Wagner’s Theorem, which states that a graph is planar iff neither $latex K_5$ nor $latex K_{3,3}$ is a minor of it.

A topological minor is a related notion.  Informally, $latex G$ is a topological minor of $latex H$ if we can start with $latex G$, and transform it into a subgraph of $latex H$ by only adding vertices into edges that already exist (i.e., subdividing edges, so edge $latex (u,v)$ becomes two edges, $latex (u,x)$ and $latex (x,v)$).  Figure 1 on this web page shows examples of a minor and a topological minor.  (Note: that figure may be behind a paywall.  If anyone knows a good diagram explaining minor vs. topological minor that is freely available, please put it in the comments.)

Fortunately for Eli, Robin Kothari and co-authors had needed this folk theorem for a paper, and they had been unable to find a proof of it either, so they reproved it themselves.  Kothari’s proof (and answer to Eli’s question) appears here.  It is an example of a growing number of original proofs that appear on cstheory.  That proof by Kothari is definitely my “favorite answer of the week.”  As Eli put it, “This is stellar.”

The question-and-answer site cstheory, also known as “Theoretical Computer Science,” was founded in 2010 by community volunteers, and now has over 4500 registered users.  Some of the founding members of cstheory participated in discussion of a proposed solution to the P/NP problem that spanned multiple blogs, led to the creation of wiki pages, and brought together researchers in disparate areas from around the world.  This effort made it clear that the worldwide theoretical computer science community was ready for – and needed – a structured way to ask research-level questions and to consider answers to such questions.  (For more background on cstheory, please see this SIGACT News article.)

This blog is intended for community discussion of topics in theoretical computer science, broadly construed.  While the blog’s parent site (cstheory) requires that questions asked there be “research-level” (e.g., not elementary), posts and comments here can have a wider scope.  We hope to publish both introductory and advanced posts in complexity theory, learning theory, quantum computing, programming language theory, logic, algorithms, and other areas of theory, and theory applied to practice.

We are actively soliciting one-time contributions, and the participation of regular contributors.  If you would like to participate in the blog, please email one of the editors — Joe Fitzsimons or Aaron Sterling — or post your interest on the blog contributor signup sheet.

Editors’ bios:

Aaron Sterling is a PhD candidate in computer science at Iowa State University.  He is currently a Visiting Predoctoral Fellow at Northwestern University, working with Ming-Yang Kao on the theory of self-assembly.  He authors the blog Nanoexplanations.

Joe Fitzsimons recieved his DPhil from the from the University of Oxford in 2007, and is currently research assistant professor at the Centre for Quantum Technologies, at the National University of Singapore, and a visiting lecturer at University College Dublin. Prior to joining CQT, Joe spent 3 years as a Junior Research Fellow at Merton College, Oxford, and as a visiting researcher at the Institute for Quantum Computing and the department of Combinatorics and Optimization at the University of Waterloo. His research interests lie mainly in the field of quantum computation.