{"id":437,"date":"2010-01-13T10:38:06","date_gmt":"2010-01-13T14:38:06","guid":{"rendered":"https:\/\/scottaaronson.blog\/?p=437"},"modified":"2010-01-13T10:38:06","modified_gmt":"2010-01-13T14:38:06","slug":"changing-fields","status":"publish","type":"post","link":"https:\/\/scottaaronson.blog\/?p=437","title":{"rendered":"Changing fields"},"content":{"rendered":"

I’m at CWI<\/a> in Amsterdam, after spending two weeks in Israel.\u00a0 Next week I head to QIP’2010<\/a> in Zurich, and the week after that, to the Perimeter Institute in Waterloo.<\/p>\n

The following meta-question emerged from a conversation with Dorit Aharonov two weeks ago:<\/p>\n

What’s your favorite example of a result in theoretical computer science that works over finite fields, but doesn’t<\/em> work (or isn’t known to work) over the reals or complex numbers?<\/p>\n

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?<\/p>\n

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?<\/p>\n

By “crucial property”, I mean something like this:<\/p>\n

    \n
  1. There’s a natural metric (i.e., a distance measure) on the reals or complex numbers, but not on a finite field.<\/li>\n
  2. There’s a uniform distribution over a finite field, but not over the reals or complex numbers.<\/li>\n<\/ol>\n

    I’d especially be interested in properties that don’t<\/em> reduce to one of the two above.<\/p>\n","protected":false},"excerpt":{"rendered":"

    I’m at CWI in Amsterdam, after spending two weeks in Israel.\u00a0 Next week I head to QIP’2010 in Zurich, and the week after that, to the Perimeter Institute in Waterloo. 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 […]<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"advanced_seo_description":"","jetpack_seo_html_title":"","jetpack_seo_noindex":false,"_jetpack_feature_clip_id":0,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"_wpas_customize_per_network":false},"categories":[5],"tags":[],"class_list":["post-437","post","type-post","status-publish","format-standard","hentry","category-complexity"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/437","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=437"}],"version-history":[{"count":0,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=\/wp\/v2\/posts\/437\/revisions"}],"wp:attachment":[{"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=437"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=437"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scottaaronson.blog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=437"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}