tag:blogger.com,1999:blog-3722233.post4599175495420459984..comments2022-09-27T13:51:30.964-05:00Comments on Computational Complexity: Computational Intractability: A Guide to Algorithmic Lower Bounds. First draft available! Comments Welcome!Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-21858692383505637152022-08-31T16:28:46.166-05:002022-08-31T16:28:46.166-05:00Some comments:
-ABGS21 does not show 2^{(1-\eps)n}...Some comments:<br />-ABGS21 does not show 2^{(1-\eps)n} hardness for ShVecProb_p, but shows 2^{C_p n} hardness where the constant C_p grows with p, and C_p approaches 1 when p tends to infinity. <br /><br />-The following statement is ambiguous. "This problem is the basis for many post-quantum crypto systems. Thats just a fancy way of saying crypto systems that do not depend on number-theoretic hardness assumptions." How would you define what a number-theoretic hardness assumption is? Why would, say, learning with errors not qualify?<br />Diveshhttps://www.blogger.com/profile/03199525318560734147noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-38345855718833042992022-08-31T08:41:01.049-05:002022-08-31T08:41:01.049-05:00Looks like a well-done update of Garey & Johns...Looks like a well-done update of Garey & Johnson's 1979 classic. This was distinguished with a catalogue of all known NP-complete problems which the new version does not provide. Instead it focuses on well chosen examples and a broader up-to-date treatment of intractability. As a considerable amount of the content is referred to the exercises, there should be a solutions section which may at least contain a hint or a reference to the bibliography. I think Knuth, in his "The Art of Computer Programming," has done it in an exemplary way with his solutions to the excercises section. A rating of the difficulty of each excercise (another feature of Knuth's) is nice to have but not mandatory.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-63810150337401262972022-08-25T00:05:22.482-05:002022-08-25T00:05:22.482-05:00Congratulations and appreciation to all three of y...Congratulations and appreciation to all three of you!<br />- Jonathan ShewchukJonathanhttps://www.blogger.com/profile/04699323493832882000noreply@blogger.com