Constructive Separations and Their Consequences

Lijie Chen, Ce Jin, Rahul Santhanam +1

For a complexity class $C$ and language $L$, a constructive separation of $L\notin C$ gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for…