Proving lower bounds via Pseudo-random generators

Agrawal, Manindra (2005) Proving lower bounds via Pseudo-random generators 25th International Conference, FSTTCS 2005, 3821 . pp. 1-14.

[img]
Preview
PDF - Author Version
198kB

Official URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=1...

Abstract

In this paper, we formalize two stepwise approaches, based on pseudo-random generators, for proving P 6≠ NP and its arithmetic analog: Permanent requires superpolynomial sized arithmetic circuits.

Item Type:Article
Source:Copyright of this article belongs to 25th International Conference, FSTTCS 2005.
ID Code:92015
Deposited On:26 May 2012 13:58
Last Modified:19 May 2016 05:36

Repository Staff Only: item control page