Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EASY-WITNESS LEMMA:
Reports tagged with easy-witness lemma:
TR19-167 | 21st November 2019
Anant Dhayal, Russell Impagliazzo

UTIME Easy-witness Lemma & Some Consequences

Revisions: 2

We prove an easy-witness lemma ($\ewl$) for unambiguous non-deterministic verfiers. We show that if $\utime(t)\subset\mathcal{C}$, then for every $L\in\utime(t)$, for every $\utime(t)$ verifier $V$ for $L$, and for every $x\in L$, there is a certificate $y$ satisfing $V(x,y)=1$, that can be encoded as a truth-table of a $\mathcal{C}$ circuit. Our ... more >>>




ISSN 1433-8092 | Imprint