tag:blogger.com,1999:blog-3722233.post4580221543262282386..comments2022-11-27T20:31:33.169-06:00Comments on Computational Complexity: Intersecting ClassesLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-53951151794916418132021-07-05T11:57:05.526-05:002021-07-05T11:57:05.526-05:00@Unknown -- yes, solutions are there and if you ca...@Unknown -- yes, solutions are there and if you can find one, it's easy to recognize as a solution. Note that an "exponential number of gradient iterations" result is known from https://arxiv.org/abs/1807.01280 (On the Computational Power of Online Gradient Descent, by Vaggos Chatziafratis, Tim Roughgarden, Joshua R. Wang). Our paper shows that the solution concept (of local optimum of a continuous function) is "hard" to find by any algorithm (that may be allowed to inspect the circuit that computes the objective function, looking for short-cut alternatives to gradient iterations).Paul Goldberghttps://www.blogger.com/profile/10952445127830395305noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-75519058359445300062021-07-03T00:40:23.685-05:002021-07-03T00:40:23.685-05:00Lance, nice fonts ... sets a and B rendered nicely...Lance, nice fonts ... sets a and B rendered nicely on my screen.EGnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19182006714441997352021-07-02T19:04:27.056-05:002021-07-02T19:04:27.056-05:00Thank you. Essentially the solution is there but i...Thank you. Essentially the solution is there but it would take an exponential number of gradient iterations.. correct? Is there Ptime cases for the class CLS?Anonymoushttps://www.blogger.com/profile/15215802322939426847noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-30156518829039005402021-07-02T03:34:28.607-05:002021-07-02T03:34:28.607-05:00Thanks Lance. Let me admit that the paper is a fin...Thanks Lance. Let me admit that the paper is a fine example of the humorous stereotype of complexity theorists proving a problem "hard" when meanwhile the problem is being routinely solved in practice in the real world. (In this case, the problem of finding continuous local optima.) But of course, our hope is that by understanding the worst-case hardness, this will lead to a better understanding of solvability in practice.Paul Goldberghttps://www.blogger.com/profile/10952445127830395305noreply@blogger.com