tag:blogger.com,1999:blog-3722233.post7066167178937721771..comments2024-11-11T20:40:58.950-06:00Comments on Computational Complexity: Inverting a FunctionLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger6125tag:blogger.com,1999:blog-3722233.post-47040167120734144872023-11-20T22:57:54.801-06:002023-11-20T22:57:54.801-06:00I strongly resent the last comment.
There is an ...I strongly resent the last comment. <br /><br />There is an email thread involving 6 researchers from February 2023 in which Shuichi discovered the key hashing reduction in our paper (one major difference between our paper and the other one), and in which we figured how to use sorting to easily get 2^(n/2)*poly(n) size circuits for inverting permutations. <br /><br />A few months later, Rahul and I returned to the problem, and we worked out how to get 2^(4n/5) size circuits for the general case. We invited Shuichi to join the paper later due to his hashing contribution, after he was already on the ITCS PC. Our paper appeared online when it did because we submitted to STOC.<br /><br />I don't know how Mazor and Pass got their circuit result, around the same time. I can say for sure that, at some point, the problem of "circuitizing" Fiat-Naor was circulating among groups at the Simons Institute in Spring'23 as an interesting open problem, and that Mazor and Pass were also visitors in the Spring. I can also say for sure that Rahul shared with many other folks visiting Simons already in February how to solve MCSP in 2^(3N/4) time non-uniformly using function inversion (hence the above email thread), and I was confident from the beginning that one could obtain circuits from this.<br /><br />It is very unfortunate that someone out there hides behind an Anonymous name on the web, trying to publicly slander others.Ryan Williamsnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-60743382901240376452023-11-20T09:56:05.307-06:002023-11-20T09:56:05.307-06:00The Hirahara-Ilango-Williams result appeared on EC...The Hirahara-Ilango-Williams result appeared on ECCC after the reviewing process of ITCS 2024, where the Mazor-Pass result was submitted to. Interestingly, Hirahara was on the ITCS 2024 PC. I find it hard to believe they are really independent results.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-33586132760261521772023-11-16T22:28:30.600-06:002023-11-16T22:28:30.600-06:00@Lance, what direct implication does the result ha...@Lance, what direct implication does the result have for minimal boolean formula size problem .... there's a threshold upon which concrete values for formula and circuit are actually identical, I believe. EGnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-5178564099682981502023-11-16T22:23:47.884-06:002023-11-16T22:23:47.884-06:00The results are intriguing and in particular becau...The results are intriguing and in particular because they are connected to the minimum circuit-size problem .... <br />NB: Thanks for pointing out the ITC2024 site. It's a let down in terms of basics -- no TLS certificate features.EGnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-37199702013597455812023-11-16T22:18:55.126-06:002023-11-16T22:18:55.126-06:00The Hirahara-Ilango-Williams paper claims what you...The Hirahara-Ilango-Williams paper claims what you state, but the Mazor-Pass paper does not. The latter only claims a circuit of 2^(4n/5) size for compressing n-bit input.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-88223409262289818712023-11-16T15:15:36.771-06:002023-11-16T15:15:36.771-06:00> I have no inside knowledge whether these pape...> I have no inside knowledge whether these papers were either or both submitted to STOC<br /><br />The "Perebor" paper was accepted to ITCS 2024: http://itcs-conf.org/itcs24/itcs24-accepted.htmlDavehttps://www.blogger.com/profile/00243750470577898974noreply@blogger.com