Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SUCCINCT PERMANENT:
Reports tagged with succinct permanent:
TR12-086 | 4th July 2012
Shlomi Dolev, Nova Fandina, Dan Gutfreund

Succinct Permanent is NEXP-hard with Many Hard Instances

Finding a problem that is both hard to solve and hard to solve on many instances is a long standing issue
in theoretical computer science.
In this work, we prove that the Succinct Permanent $\bmod \; p$ is $NEXP$
time hard in the worst case (via randomized polynomial time ... more >>>




ISSN 1433-8092 | Imprint