Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization

In three linesTheoretical study showing that exact certification of threshold circuits (depth ≥2) and log-precision Transformers becomes exponentially hard with minimal overparametrization. Adding a single gate or constant architectural overhead forces certificate sizes exponential in input dimension. Empirical validation on binary addition recognition.

Summary generated by Claude — human-verified