BACKGROUND
Louis and I were discussing the problem of finding an arithmetic progression of "special elements" in a general series. It all started like this:
Louis: Awesome question:
Me: ?
Louis: Find the longest arithmetic sequence of awesome XKCD comics
Me: XD
Me: 1. that's totally subjective, 2. that's AWESOME
Louis: well, it's different for every person of coures
Louis: *course
Me: well, of course, since they do have positive density, if xkcd were to continue forever
Me: there'd be arbitrarily long APs...
[...]
Louis: I'm talking a computational
Louis: problem
Me: oh
Me: hm.
Louis: not VDW :P
Me: well that's technically szemeredi...
Me: wait, is finding long APs...
Louis: VDW.
Me: szemeredi, and is it in P?
Louis: VDW.
Louis: And yes, I believe so
Louis: given that there are only n^2 possible AP'sMe: oh, d'oh. gp.
Me: lol
Louis: ;-)
Me: (incidentally, there's more like n^3 partial APs, but still polynomial)
Louis: ah, partial AP's.
Louis: well, we needn't consider only partial AP's
Louis: for each a_i, for each a_j, search the arithmetic sequence going a_i, a_j, a_i + 2(a_j - a_i),...
Louis: as far as you can go until you reach something not in the set.
Me: yeah, yeah
Me: and, btw, it is about n^2 log n [Exercise for the reader: Why?]
I'm many things, but I'm not an Algorithms person, and this was now, to me, an Algorithms question and therefore dead. (It didn't help that I couldn't find any way of checking for an AP in o(n^2) time). But then:
AN EPIPHANY
Me: I'm wondering if this might
Me: if this could provide an oracle separation between P and BPP
Louis: XD
Me: seriously!
Louis: how?
Louis: it's in P!
Me: yeah, but
Me: let's take sets of size
Me: well, let's consider the problem of finding an AP of length at least n in the range [1, superpoly(n)], 2-colored according to some cuh-razy random oracle.
Louis: okay
Me: (actually, we should probably specify that it has to be one specific color)
Louis: you do realize you're now reminding me of the quantum database search problem, too?
Me: let's say that all of the elements of the AP have to be yellow, and the oracle colors a number yellow with some fairly high probability
Louis: okay
Me: actually, let's not make it length n, let's make it length [O(log(superpoly(n)))]
Louis: how will BPP help us?
Me: for almost all oracles, all we have to do is pick a random AP and there's positive probability it's yellow.
Louis: but wait
Louis: if the numbers are colored randomly
Louis: then why would randomized search be any better than brute force?
Me: on average? duh, it wouldn't. worst-case, though...
Me: it seems less hard to show brute-force won't work well in some fraction of oracle universes
Mathematical backing-up of my assertions in the conversation: Consider a random coloring of [1, superpoly(n)] s.t. the probability of a given number being colored yellow is \delta. There are approximately superpoly(n)^2 APs of length log(superpoly(n)) [I'm totally fudging the numbers there, but the basic argument should still hold.] If the implied constant of the log(superpoly(n)) is sufficiently small, then the probability of a randomly chosen AP of that length being yellow is at least \delta^log(superpoly(n)) > 1/superpoly(n)^2.
N.B., in fact, that by doing nothing more than messing around with a few constants, we can get the probability to be > k/superpoly(n)^2 for any constant k we want to work with. (Or even, for that matter, > k/superpoly(n).) Then the expected value of the number of APs of the...oh, screw it, of the right length is k.
So! In retrospect, the functions I picked don't work very well, but it's not difficult to change them around a bit so that our above argument (after throwing in some stuff about the Chernoff bound) actually ends up telling us the following:
1. For almost all oracles we've considered here, there exists f(n) superpolynomial, g(n) really slow-growing such that a BPP algorithm can pick polynomially many APs of length g(n) in the range [1, f(n)] s.t. with positive, constant probability, at least one will be yellow.
And here's the crux: There's no obvious way that a deterministic algorithm can do the same thing. Actually, with all these oracle universes floating around, it should be obvious to even the most dimwitted individual who holds an advanced degree in hyperbolic topology, n'hey [sorry], that some of them won't.
CONCLUSION
The problem is, though, that like most lower bounds, this fact is easier noticed than proved. And since there are already known oracle separations of P from BPP, one more wouldn't be particularly exciting. Still, though, it's fun to see two of my (and some other occasional readers') main interests -- computational complexity and additive combinatorics -- work together in a way I can understand, even if I can't quite finish the proof.
Subscribe to:
Post Comments (Atom)
3 comments:
"Van der Waerden's theorem states that for any given positive integers r and k, there is some number N such that if the integers {1, 2, ..., N} are colored, each with one of r different colors, then there are at least k integers in arithmetic progression all of the same color."
VDW it is.
"and, btw, it is about n^2 log n [Exercise for the reader: Why?]"
Actually, the longest AP can be found in O(n^2) time, or in O((n^2/k) log(n/k) log k) time, where k is the output length. Probably one can remove a few more log factors on a word RAM using bit tricks.
"this was now, to me, an Algorithms question and therefore dead. (It didn't help that I couldn't find any way of checking for an AP in o(n^2) time)."
Nope, it's an open lower-bound question, and therefore very much alive. There is an Ω(n^2) lower bound for finding 3-term arithmetic progressions in a weak but natural model of computation (3-linear decision trees), so you'd have to do something really weird (like bit tricks) to beat that. It's a longstanding open problem whether 3-term APs can be found in subquadratic time (by more than a polylog factor) in any model of computation.
"it should be obvious to even the most dimwitted individual who holds an advanced degree in hyperbolic topology, n'hey [sorry], that some of them won't."
No you can't play with it, you won't enjoy it on as many levels as I do... Mm-hai bw-ha whoa-hoa. The colors, children. Mwa-ha-lee.
Jeff: The n^2 log n was actually referring to the total number of (partial) APs. Apologies if that wasn't clear.
Post a Comment