Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with refuters:
TR21-159 | 15th November 2021
Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams

Constructive Separations and Their Consequences

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 every $C$-algorithm attempting to decide $L$. We study the questions: Which lower bounds can be made constructive? What are the consequences ... more >>>

ISSN 1433-8092 | Imprint