tag:blogger.com,1999:blog-3722233.post114177093126971998..comments2021-09-28T10:13:47.638-05:00Comments on Computational Complexity: Computation and GeometryLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger2125tag:blogger.com,1999:blog-3722233.post-1141921850452699772006-03-09T10:30:00.000-06:002006-03-09T10:30:00.000-06:00Lance,Sorry for offtopic. There seems to be some P...Lance,<BR/>Sorry for offtopic. There seems to be some P/NP-related activity in group-theory community, for example this workshop - http://math.berkeley.edu/index.php?module=announce&ANN_user_op=view&ANN_id=56<BR/>Participants are very well-known mathematicians. I wonder if you are aware and maybe able to provide us with some additional info?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1141773642757708832006-03-07T17:20:00.000-06:002006-03-07T17:20:00.000-06:00Thanks for the comment, Lance.One point of clarifi...Thanks for the comment, Lance.<BR/><BR/>One point of clarification is about the connection to the closest vector problem (CVP). Unfortunately, the first paper doesn't show that finding the length of the minimal geodesic is necessarily equivalent to solving a closest vector problem. All it shows is an equivalence between the closest vector problem and finding the minimal geodesic amongst a certain special class of geodesics, which I call Pauli geodesics.<BR/><BR/>To make this connection to CVP really useful, we'd need a guarantee that the minimal geodesic is, in fact, a Pauli geodesic. In my paper I prove that this will be the case if the minimal geodesic is unique, but there's no guarantee I know of that this will be the case for problems of interest. So the connection to CVP is, at best, incomplete.<BR/><BR/>The question of to what extent Razborov-Rudich applies to the geometric approach to quantum computing is a really interesting one, and it's not yet clear to me what the answer is.<BR/><BR/>Michael NielsenAnonymousnoreply@blogger.com