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