Posts Tagged ‘cs.CC’

What’s a “locally determined graph property?”

January 1, 2010

This has nothing to do with the rest of the post, but I’ll put it here so you read it before you get bored. I’d like to thank my readers (all seven of you) for supporting this blog in the first six months or so of its existence, and hope that you’ll stick around (and be joined by hundreds of new readers…) to hear my sporadic ramblings and wild ravings in the next year. Here’s to a happy and successful 2010!

Over at MathOverflow, Gjergji Zaimi asks (in a criminally under-voted-for question): How can we obtain global information from local data in graph theory?  This is something that perhaps everyone working in or around graph theory has asked themselves, in some form, at some point — I know I have. So it’s not surprising that Gjergji’s question has received many different answers with many different interesting things to say.

I originally wanted to write a post trying to “answer” Gjergji’s question as best I could, but quickly realized the futility of that goal — it’s such a broad and deep question that I doubt if anyone could answer it concisely, and I know I couldn’t! So instead I’ll just talk about an \epsilon of the question — what does it even mean, “local data?”

(more…)

Advertisements

The importance of choosing the right model

December 13, 2009

I’ve had the idea for this post bouncing around in my head for several months now, but now that I don’t have classes to worry about I can finally get around to writing it. I want to talk about some “pathological examples” in computer science, in particular in complexity and computability theory.

I wanted to post a picture of William H. Mills with this post, in the spirit of Dick Lipton’s blog. Unfortunately I can’t find one! Mills was a student of Emil Artin in the ’40s; he finished his thesis in 1949 and promptly (as far as I can tell) disappeared until the ’70s, when we find some work by a William H. Mills on combinatorial designs. After this, there’s nothing of note until Dr. Mills passed away several years ago at the age of 85.

While his work (assuming it’s his) on combinatorial designs looks interesting, W.H. Mills’ small place in history is assured by a short and unassuming paper from 1947, published when he was still a student. In this paper he showed that there’s a constant, which he called A, such that [A^{3^n}] is prime for all integers n \geq 1. Nowadays it’s called Mills’ constant.

(more…)

A FOCS-related question

July 27, 2009

Actually, it’s not so much related to FOCS as to a specific paper in FOCS. I’m talking about the paper of Basu and Zell in which they formulate and prove an analogue over the real numbers of Toda’s theorem. I happen to know virtually nothing about real complexity theory, and even in standard complexity theory Toda’s theorem is pretty far from my usual interests of circuit complexity and derandomization, but their abstract nevertheless caught my attention for one single reason: the method of proof.

As far as I know, all of the proofs of (the classical) Toda’s theorem rely on heavy machinery from complexity and combinatorics, and tend to be quite involved. Basu and Zell’s paper also seems to be pretty long and technical, but their result is proved (and formulated) using tools from algebraic topology. For instance, the real analogue of #P is defined using the Poincare polynomial (the generating function of the Betti numbers, from a combinatorialist’s viewpoint). Basu and Zell are also kind enough to provide a definition of #P from a “geometric” viewpoint as well. My question is whether this topological or geometric intuition over GF_2 (or in classical complexity) can be extended to produce a new proof of Toda’s theorem.

By the way, if this post sounds like I don’t know what I’m talking about even more so than usual, that’s because I don’t know what I’m talking about even more so than usual. Apologies.

(more…)