tag:blogger.com,1999:blog-3722233.post3376175334269832980..comments2024-03-02T02:08:38.816-06:00Comments on Computational Complexity: Being Random and Trivial in DagstuhlLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-3722233.post-6941974317459012382012-01-16T19:13:05.044-06:002012-01-16T19:13:05.044-06:00Is there a result in Complexity Theory such that i...<i>Is there a result in Complexity Theory such that its statement has nothing to do with Kolmogorov Complexity, yet its proof uses Kolmogorov Complexity in a critical way?</i><br /><br />If you consider lower bounds as a hybrid between algorithms and complexity theory then there are tons of them.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-34710061940769212882012-01-14T04:25:48.388-06:002012-01-14T04:25:48.388-06:00Attending this meeting it seemed to me that the co...Attending this meeting it seemed to me that the computability school of K-complexity is slowly taking over the complexity school, with the majority of young people present studying computability aspects of K-complexity.<br /><br />I don't know if this an accurate description of the actual state of K-complexity, e.g. it may be due to the mere fact that the majority of the organizers have a computability background.<br /><br />I'm sure the organizers had good reasons, but I found the number of talks was on the low side, and I would have liked to hear more talks given the many "famous" people present.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85592866717027321832012-01-13T11:50:04.292-06:002012-01-13T11:50:04.292-06:00CORRECTION- my comment said Superlow=K-trivial.
Ac...CORRECTION- my comment said Superlow=K-trivial.<br />Actually its K-Trivail is proper Subset of Superlow.<br />Rod Downey emailed me the corrections for which I thank him.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-31440110685408274192012-01-12T21:06:45.397-06:002012-01-12T21:06:45.397-06:00Two big non-stagnant topics in computability theor...Two big non-stagnant topics in computability theory:<br /><br />1) Reverse Mathematics- using computability theory to pin down<br />how constructive certain theorems in math are. Here Computability<br />theory is a tool for something else. (An earlier program which<br />is more obviously using computability theory is Nerode's <br />Recursive Mathematics program). For more see Stephen Simpson's home page.<br /><br />2) Random sets, as Lance is talking about. That Superlow=K-trivial<br />is a very nice result that connects the two fields. For more<br />see Downey-Hirschfeld.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-56573785635199472402012-01-12T17:07:51.480-06:002012-01-12T17:07:51.480-06:00Doesn't Robin Moser's proof of the LLL use...Doesn't Robin Moser's proof of the LLL use Kolmogorov complexity?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-47069778036764260952012-01-12T15:39:39.012-06:002012-01-12T15:39:39.012-06:00Ignorant question (and I'm legitimately curiou...Ignorant question (and I'm legitimately curious, not trying to be smarmy), what do computability researchers research these days? Are there new results? I always thought (or at least have read, not being in academia I don't have my own view on this) that computability theory has been stagnant for quite a while and most "related" results are in complexity theory now. Obviously I see this view is wrong, but what's cooking on on that end of things?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-18383193758495275142012-01-12T15:07:20.028-06:002012-01-12T15:07:20.028-06:00Is there a result in Complexity Theory such that i...Is there a result in Complexity Theory such that its statement has nothing to do with Kolmogorov Complexity, yet its proof uses Kolmogorov Complexity in a critical way?Anonymousnoreply@blogger.com