The Minimum Circuit Size Problem has an almost unyielding quality. Since the 1950s, it has been sitting in the back room of computational complexity, watched, prodded, and occasionally yelled at, but never quite cornered. The question itself seems surprisingly straightforward. Can you compute a Boolean function given its truth table using a circuit that is at most θ in size? That completes the puzzle. Nevertheless, decades later, neither the NP-hardness nor the ease of MCSP have been established.
The July 2020 ACM Transactions on Computation Theory paper by Cheraghchi, Kabanets, Lu, and Myrisiotis doesn’t claim to resolve that long-standing issue. It has a more subdued effect. It brings the lower bounds for MCSP closer to what we already know about hard functions like PARITY, which is the kind of advancement that subtly alters the way researchers view the field but doesn’t make headlines.
| Information | Details |
|---|---|
| Paper Title | Circuit Lower Bounds for MCSP from Local Pseudorandom Generators |
| Authors | Mahdi Cheraghchi, Valentine Kabanets, Zhenjian Lu, Dimitrios Myrisiotis |
| Affiliations | University of Michigan, Simon Fraser University, Imperial College London |
| Published In | ACM Transactions on Computation Theory, Volume 12, Issue 3 |
| Publication Date | 20 July 2020 |
| Earlier Version | ICALP 2019 conference proceedings |
| Article Number | 21 (27 pages) |
| Citations | 25+ as of recent counts |
| Primary Topic | Minimum Circuit Size Problem, circuit complexity |
| Key Result | N³⁻ᵒ⁽¹⁾ lower bound for de Morgan formulas computing MCSP |
It’s not just the outcome that makes the work intriguing. It’s the instrument. The authors rely on local pseudorandom generators, which allow small circuits to compute the output strings when they are read as truth tables. That has a certain grace to it. In order to demonstrate how difficult it is to recognize structure, you are using a manufactured object that imitates randomness. When you sit with it long enough, it’s the kind of move that almost seems recursive.
It’s worth stopping to look at the numbers. They improve on the N²⁻ᵒ⁽¹⁾ bound from Hirahara and Santhanam two years ago by proving a N³⁻ᵒ⁽¹⁾ lower bound for de Morgan formulas computing MCSP. For general formulas and branching programs, where nothing nontrivial previously existed, they obtain N²⁻ᵒ⁽¹⁾. Additionally, they push the size requirement for AC circuits of depth d to 2^Ω(N^(1/(d+1.01)), which is almost identical to what we know about PARITY itself. The bound, 2^Ω(N), is practically optimal for depth-2.
It’s difficult to ignore how frequently complexity theory develops in this manner. Not by an epiphany, but by tightening, improving, and swapping out one constant for a marginally better one. In 2006, Allender and his colleagues developed an implicit exponential bound. It is strengthened and made explicit in this paper. That work requires a level of patience that isn’t always evident in citation counts.
An additional layer is added by the cryptographic perspective. Researchers have long known that MCSP is not in P if there are one-way functions. Thus, the issue is at this peculiar crossroads where its difficulty appears to be linked to presumptions that practitioners already rely on on a daily basis—the same presumptions that underpin the majority of contemporary encryption. This entanglement may be the reason the issue continues to garner new attention. It won’t fit into a box.
It’s tempting to notice a pattern developing as you follow the course of this field of study. The gap between what we suspect and what we can prove gets smaller with each paper. It remains to be seen if that gap will ever completely close. However, it seems that MCSP has changed from being a curiosity to something more akin to a load-bearing wall in complexity theory, particularly in recent years. The 2020 paper is not final. However, it’s a strong one, and others will be building against it for a very long time.
