With the STOC deadline this last Monday, a number of complexity papers have appeared on arXiV and ECCC. Two caught my eye because they seem to independently prove the same interesting result.
Beating Brute Force for Compression Problems by Shuichi Hirahara, Rahul Ilango and Ryan Williams
The Non-Uniform Perebor Conjecture for Time-Bounded Kolmogorov Complexity is False by Noam Mazor and Rafael Pass
Suppose you have a function f that maps from \(\Sigma^*\) to \(\Sigma^n\) and runs in time poly(n). Suppose for some x you knew there was a y of length m such that f(y) = x. How hard is it to find y? Standard brute force search would take time \(poly(n)2^m\). With a quantum computer you could find the y in time \(poly(n)2^\frac{m}{2}\) using Grover's algorithm. How about classically?
These papers show that you solve this problem non-uniformly in time \(poly(n)2^\frac{4m}{5}.\) A bit surprising that you can avoid searching the whole space of solutions. Has applications to the minimum circuit-size problem and time-bounded Kolmogorov complexity. Both papers build on earlier work of Amos Fiat and Moni Naor.
I have no inside knowledge whether these papers were either or both submitted to STOC, but if they were and the program committee finds the results worthy, how will it be handled? Merge or no-merge. We'll find out in mid-February when the committee announces the acceptances.
> I have no inside knowledge whether these papers were either or both submitted to STOC
ReplyDeleteThe "Perebor" paper was accepted to ITCS 2024: http://itcs-conf.org/itcs24/itcs24-accepted.html
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.
ReplyDeleteThe results are intriguing and in particular because they are connected to the minimum circuit-size problem ....
ReplyDeleteNB: Thanks for pointing out the ITC2024 site. It's a let down in terms of basics -- no TLS certificate features.
@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.
ReplyDeleteThe 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.
ReplyDeleteI strongly resent the last comment.
ReplyDeleteThere 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.
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.
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.
It is very unfortunate that someone out there hides behind an Anonymous name on the web, trying to publicly slander others.