In a 2016 paper, the four researchers proved that a certain kind of average-case MCSP algorithm could be used to construct a worst-case algorithm for identifying patterns hidden in random-looking strings of digits — a task that computer scientists refer to as “learning.” It’s a striking result because learning intuitively seems harder than the binary classification task — high complexity or low complexity — performed by an MCSP algorithm. And, surprisingly, it linked the worst-case complexity of one task to the average-case complexity of the other.

“It wasn’t obvious that such a connection would exist at all,” Impagliazzo said.

A fast algorithm for MCSP is purely hypothetical for general Boolean circuits: It can’t exist unless MCSP turns out to be an easy computational problem, despite all evidence to the contrary, and that means the learning algorithm implied by the four researchers’ paper is equally hypothetical.

But for some simpler versions of MCSP — distinguishing high-complexity truth tables from low-complexity ones when there are specific restrictions on the circuits — fast algorithms have been known for many years. Carmosino, Impagliazzo, Kabanets and Kolokolova’s paper showed that these algorithms could be transformed into learning algorithms that were likewise restricted but still more powerful than any that researchers had previously understood at such a rigorous theoretical level.

“Somehow their self-referential flavor enables you to do things that seemingly you can’t do with more standard problems,” Ilango said.

The result grabbed the attention of complexity theorists working on other topics. It was also a preview of further connections between meta-complexity and average-case complexity that would emerge over the coming years.

Most of all, it was a testament to how far researchers can get by asking simple questions about barriers that at first seem only to obstruct their progress.

“This kind of duality is a theme throughout at least the last 30 or 40 years of complexity,” Impagliazzo said. “The obstacles are often the opportunities.”

Partial Credit

Progress has only accelerated in the years since Carmosino and his colleagues published their paper.

“New things are happening,” Kolokolova said. “There are lots of really, really bright junior researchers.”

Ilango is one of these young researchers — in his first three years of graduate school, he’s attacked the daunting open problem of proving MCSP NP-complete using a two-pronged strategy: proving NP-completeness for simpler versions of MCSP, as circuit complexity researchers did when attacking P versus NP in the 1980s, while also proving NP-completeness for more complicated versions, which intuitively seem harder and thus are perhaps easier to prove hard.

Ilango credits his interest in meta-complexity to Eric Allender, a complexity theorist at Rutgers University and one of the few researchers who continued working on meta-complexity in the 2000s and early 2010s. “His enthusiasm was infectious,” Ilango said.

Another young researcher inspired by Allender is Shuichi Hirahara, now a professor at the National Institute of Informatics in Tokyo. While still a graduate student in 2018, Hirahara revealed the true extent of the relationship between meta-complexity and average-case complexity that Carmosino and his co-authors had discovered. Those four researchers had found a connection between the average-case complexity of one problem — MCSP — and the worst-case complexity of another — Boolean learning. Hirahara developed their techniques further to derive a worst-case to average-case reduction for MCSP. His result implies that a hypothetical average-case MCSP algorithm like the one Carmosino and his colleagues had considered would actually be powerful enough to solve a slightly different version of MCSP without making any mistakes.

Hirahara’s result is exciting because many researchers suspect that MCSP is NP-complete, unlike all other problems for which worst-case to average-case reductions are known. If they can extend Hirahara’s results to cover all average-case algorithms and then prove that MCSP is NP-complete, that would prove we don’t live in Heuristica.

“That would really be an earth-shattering result,” Santhanam said.

Proving that MCSP is NP-complete may seem like a tall order — after all, the question has been open for over 50 years. But after a breakthrough last year by Hirahara, researchers are now much closer than anyone would have expected a few years ago.

Hirahara proved NP-completeness for a variant of the problem called partial MCSP, in which you ignore certain entries in each truth table. His proof built on methods developed by Ilango to show that partial MCSP was equivalent to a seemingly unrelated problem involving a cryptographic technique called secret sharing. This is a way to divide an encrypted message among many people so that it can only be decoded if a certain fraction of them work together.

For any real application in cryptography, you’d want to know that fraction in advance, but with the help of extra cryptographic tricks, you can construct a frustrating scenario in which it’s hard just to figure out how many people need to cooperate. Hirahara found a way to prove that this contrived cryptographic problem was NP-complete and then showed that the proof implied the NP-completeness of partial MCSP as well.