tag:blogger.com,1999:blog-3722233.post378272747883656707..comments2023-03-25T10:00:22.914-05:00Comments on Computational Complexity: When did Computer Science Theory Get so Hard?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-3722233.post-60560286749054002762021-12-13T10:37:09.800-06:002021-12-13T10:37:09.800-06:00There are brilliant people in both math and CS. Th...There are brilliant people in both math and CS. There are conjectures in Math that were solved by people in CS and vice-versa. <br />There are times when Math ends up applying to CS or Physics or ...<br /><br />There are times when CS ends up applying to Math or Phyics or<br /><br />There are times when Physics ...<br /><br />There are times when X ends up applying to Y<br /><br />None of these fields has a moral or intellectual superiority to any other field. <br /><br />I have meant to do a blog post about times when a CS result was used to resolve a math conjecture. Your comment has inspired me to actually do such a post. Thank you. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-43630010485524622552021-12-13T02:07:26.394-06:002021-12-13T02:07:26.394-06:00The true mathematician who resolving the PoincarĂ© ...The true mathematician who resolving the PoincarĂ© conjecture would think that the CS theory just likes an exercise listed in the textbook.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-77850049190435671602021-11-17T15:52:32.723-06:002021-11-17T15:52:32.723-06:00This is just bragging with no meaning. Who cares r...This is just bragging with no meaning. Who cares really about these rankings etc? Everyone wants to distinguish themselves so mathematicians may want to brag about their depth, CS people about their salaries, or what ever. Difficulty is not the point in life. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-51422286525611895312021-11-17T13:10:04.543-06:002021-11-17T13:10:04.543-06:00The distinction between a mathematician and a theo...The distinction between a mathematician and a theoretical computer scientist is very thin or perhaps non-existent. <br /><br />Note that Field medal winners Gowers and Tao have an interest in P vs NP though I am unaware of any papers they may have on it. gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-73443671883497280932021-11-17T07:39:25.015-06:002021-11-17T07:39:25.015-06:00One needs to qualify for whom cs-theory got harder...One needs to qualify for whom cs-theory got harder. It may be harder for a rusty cs-researcher to contribute high quality work or to get familiar with the new techniques. For a mathematician well versed in the relevant topic it used to be and still is a relatively easy prey. But and therefore, success in cs-theory is not particularly prestigious in math. I think logic and cs-theory (in earlier times cs-theory looked like a subfield of logic) still rank at the bottom of the math internal ranking of fields. The only Fields Medal for logic was awarded in 1966 (to Paul Cohen for resolving CH). For cs-theory none was awarded so far and we may not live to see when someone eventually resolves P-NP earning the first Fields Medal for cs-theory. Probably this will be a mathematician proper rather than someone raised as a computer scientist :-)Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8570016827267604112021-11-15T16:23:29.286-06:002021-11-15T16:23:29.286-06:00I'm supposed to say, "When I read _The Go...I'm supposed to say, "When I read _The Golden Ticket_, right :-)?<br /><br />I'm an engineer, not a theorist, and I'm...not old, but getting there. The very little I knew about theory I learned from Carver Mead, Richard Feynman, TAOCP, and eventually a battered copy of the 1979 Hopcroft and Ullman automata & compilers book. Oh, and I read a few things like the original Karp and Turing papers. My "home" conferences would be places like ASPLOS, ISCA, SIGCOMM, USENIX ATC, not STOC and FOCS. So it should not have been but was something of a surprise to me to discover that, while I was busy with other things, the theorists were...working. And discovering new things.<br />In 2003, I dropped the classical gig and started working on quantum computing full time, more or less (most of my teaching is still classical systems, and I work closely with Internet operations and education people). Today, my gig is still systems, it's just quantum instead of classical systems. I do a lot of work on Quantum Internet, machine-specific compilation of algorithms, architecture, quantum error correction; just a bit on algorithms themselves, and recently a little on cryptography. So I need to know more theory, but I spend more time reading quantum hardware and quantum algorithms papers.<br />When I cracked open Mike & Ike (Nielsen & Chuang) and discovered that were was going to be more than a single quantum complexity class wedged in between(?) P and NP, I thought, "Hmm, I have some studying to do."<br />That amount of studying looked tractable until I discovered the Complexity Zoo.<br />rdvhttps://www.blogger.com/profile/02779783832257780750noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1636136405398501262021-11-15T13:07:54.120-06:002021-11-15T13:07:54.120-06:00Hmm, it is easy to say that people are plucking lo...Hmm, it is easy to say that people are plucking low hanging fruit. This is what the current generation thinks about the past work because problems were easier then and there were fewer people. The field has gotten deeper and broader and there are many more people working in it. The math may nor may not be hard but each area requires domain knowledge to understand and make progress. That's it. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-90769204457167281342021-11-15T02:07:32.230-06:002021-11-15T02:07:32.230-06:00@gasarch: touching on just one of the points -- pu...@gasarch: touching on just one of the points -- publications<br />(in case that's a metric to evaluate output and thus<br />a correlation to hardness.)<br />My own myopic perception is that getting things published at u/grad level is simply a result of <br />* new mini frontiers being pioneered/proposed <br />* low hanging fruits have been picked and analyzed;<br />in the past the focus used to be on more abstract/general solutions<br />* many new journals/conferences popped up <br />(and sadly, quality varies vastly)<br />* we actually have a mature ecosystem with many professors needing to publish work; thus easier for u/grads to make mini contributions (or, as we all know, sometimes quite the opposite in terms of contribution -- w/ sad endings.)<br />So, I presume the rate/number of publications should not be used as metric for hardness.<br /><br />EGnoreply@blogger.com