The following meta-question emerged from a conversation with Dorit Aharonov two weeks ago:
What’s your favorite example of a result in theoretical computer science that works over finite fields, but doesn’t work (or isn’t known to work) over the reals or complex numbers?
Conversely, what’s your favorite example of a result in TCS that works over the reals or complex numbers, but doesn’t work (or isn’t known to work) over finite fields?
In either case, what’s the crucial property of the underlying field, that causes the result to work in one case but not the other?
By “crucial property”, I mean something like this:
- There’s a natural metric (i.e., a distance measure) on the reals or complex numbers, but not on a finite field.
- There’s a uniform distribution over a finite field, but not over the reals or complex numbers.
I’d especially be interested in properties that don’t reduce to one of the two above.