Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-046 | 22nd March 2010 18:50

Nisan-Wigderson generators in proof systems with forms of interpolation

RSS-Feed




TR10-046
Authors: Ján Pich
Publication: 23rd March 2010 10:45
Downloads: 3354
Keywords: 


Abstract:

We prove that the Nisan-Wigderson generators based on computationally hard functions and suitable matrices are hard for propositional proof systems that admit feasible interpolation.



ISSN 1433-8092 | Imprint