Natural Properties, MCSP, and Proving Circuit Lower Bounds
summary
Asserts concrete reductions: an average-case MCSP algorithm yields a worst-case gap-MCSP solver, and putting MCSP in randomized polytime or giving a pseudo-deterministic construction produces explicit hard truth tables and collapses randomness-vs-nonuniformity consequences (breaking local PRF constructions like NW-style generators and implying BPX-like classes fall outside P/poly). Uses locality of generators, reconstruction arguments, and bounded-arithmetic witnessing to extract hard functions from proofs. Open targets include proving MCSP hardness for slightly stronger AC0 models and using an MCSP oracle to solve SAT.
AI-written summary · about