tag:blogger.com,1999:blog-3722233.post112986033854346443..comments2023-12-07T03:00:23.146-06:00Comments on Computational Complexity: Math in ComplexityLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-1129947451949308582005-10-21T21:17:00.000-05:002005-10-21T21:17:00.000-05:00This comment has been removed by a blog administrator.andrejhttps://www.blogger.com/profile/01524486936587302987noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129913143226207792005-10-21T11:45:00.000-05:002005-10-21T11:45:00.000-05:00One missing area is Information Theory. While stri...One missing area is Information Theory. While strictly speaking it might not be an area in Math (is it EE?), but numerous complexity papers use it as a powerful mathematical tool.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129903456941190532005-10-21T09:04:00.000-05:002005-10-21T09:04:00.000-05:00--I thought ints were Z_{2^32}How quaint! Everybod...--I thought ints were Z_{2^32}<BR/><BR/>How quaint! <BR/><BR/>Everybody knows that the ints are Z_{2^64}...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129871531499917782005-10-21T00:12:00.000-05:002005-10-21T00:12:00.000-05:00When I started working in theory, Combinatorica (t...When I started working in theory, Combinatorica (the journal) was a typical place to go look for useful results, and also the place where computer scientists would publish papers of "cross-over" appeal.<BR/><BR/>Combinatorica still plays this role, and it will in the foreseeable future, but I also increasingly see GAFA (the journal on geometric and functional analysis) playing a similar one. Several important results used in at least three different areas (metric embeddings and approximation algorithms; constructions of various kinds of extractors; and PCP constructions for hardness of approximation results) appeared there. And, increasingly, theoreticians are publishing their own papers in GAFA. (Mostly on PCP-related and embeddings-related stuff.)<BR/><BR/>What's next? Maybe ten years from now we will start hearing "Atiyah", "Langlands", "sheaf" and "cohomology" as often as we now hear "Bourgain", "ell-two" and so on.Lucahttps://www.blogger.com/profile/17835412240486594185noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129867492477229022005-10-20T23:04:00.000-05:002005-10-20T23:04:00.000-05:00I thought ints were Z_{2^32}.I thought ints were Z_{2^32}.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129865491704563192005-10-20T22:31:00.000-05:002005-10-20T22:31:00.000-05:00Hmmm, this prompts my memory from last week when I...Hmmm, this prompts my memory from last week when I was wondering what the hell an int would be, as they aren't closed under much, at least not so long as there're monkeys pounding on assemblers!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1129861622955505112005-10-20T21:27:00.000-05:002005-10-20T21:27:00.000-05:00No "graph theory" in your list? Is graph theory a ...No "graph theory" in your list? Is graph theory a branch of Combinatorics ?<BR/><BR/>While we're at it, is combinatorics a branch of discrete mathematics? If it is, what else is there (other than combinatorics) in discrete math? (Discrete probability ? :-))Anonymousnoreply@blogger.com