tag:blogger.com,1999:blog-6555947.post6808252559799522283..comments2022-06-30T16:51:50.733-06:00Comments on The Geomblog: SODA list is outSuresh Venkatasubramanianhttp://www.blogger.com/profile/15898357513326041822noreply@blogger.comBlogger7125tag:blogger.com,1999:blog-6555947.post-21526413895081809842008-09-15T11:45:00.000-06:002008-09-15T11:45:00.000-06:00Actually, there was some misunderstanding about th...Actually, there was some misunderstanding about the definition of embedding. So their undecidability result is correct, but not too interesting. Sorry.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-6481104459629639412008-09-13T19:16:00.000-06:002008-09-13T19:16:00.000-06:00I think part (i) is wrong and part (ii) is correct...<I><BR/><BR/>I think part (i) is wrong and part (ii) is correct.<BR/><BR/>Care to elaborate for the benefit of mankind? I don't see the point of keeping a spotted bug a secret -- it only hinders progress.<BR/></I><BR/><BR/>Sure. The paper is "The Hardness of Embedding Simplicial Complexes in R^d" by Matousek, Tancer, and Wagner. <BR/><BR/>They claim that under certain circumstances the question of determining whether an abstract simplicial complex is embeddable in a given dimension is undecidable. To me, the question can be phrased as a first-order sentence over the field of real numbers and therefore is decidable, by a theorem of Tarski.<BR/><BR/>However, somehow they manage to claim that it is undecidable and one key step (the wrong step) is proved by the assertion that "it's clear." Kinda of annoying... <BR/><BR/>Disclaimer: I was reading the ArchivX version, not the one submitted and accepted to SODA. Maybe they fixed this 'bug.'Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-30218848703862155022008-09-12T02:20:00.000-06:002008-09-12T02:20:00.000-06:00Suresh: many thanks for formatted list of abstract...Suresh: many thanks for formatted list of abstract!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-78558696225895100732008-09-11T21:11:00.000-06:002008-09-11T21:11:00.000-06:00I think part (i) is wrong and part (ii) is correct...<I>I think part (i) is wrong and part (ii) is correct.</I><BR/><BR/>Care to elaborate for the benefit of mankind? I don't see the point of keeping a spotted bug a secret -- it only hinders progress.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-51684421006949248852008-09-10T08:15:00.000-06:002008-09-10T08:15:00.000-06:00Go abstracts! Woo!Go abstracts! Woo!Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-64542979358131965832008-09-10T00:13:00.000-06:002008-09-10T00:13:00.000-06:00I am happy and not so happy about the accepts as w...I am happy and not so happy about the accepts as well. One of the papers, written by some heavyweights, addresses an issue I've long been wondering about. So I am happy. Finally the topic got some attention!!!! I am unhappy because it seems to contradict a result I put in my thesis but never published because I thought it was trivial. <BR/><BR/>A key lemma in their proof has two parts. I think part (i) is wrong and part (ii) is correct. Here is their proof of Part(i). "Part(i) is clear."<BR/><BR/>Oh my.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6555947.post-53293444529341141242008-09-09T18:38:00.000-06:002008-09-09T18:38:00.000-06:00Procrastinating pays off! Randomly browsing that p...Procrastinating pays off! Randomly browsing that paper list, I found Belkin, Sun and Wang's paper about the Laplacian operator for PCD.. which happened to be exactly what I needed for my quals question. Nice :)Anonymousnoreply@blogger.com