Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-086 | 4th July 2012 18:02

Succinct Permanent is NEXP-hard with Many Hard Instances

RSS-Feed




TR12-086
Authors: Shlomi Dolev, Nova Fandina, Dan Gutfreund
Publication: 5th July 2012 23:14
Downloads: 3283
Keywords: 


Abstract:

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 reduction).

We find hard instances for any given heuristic, either by running the
heuristic or using
auxiliary provers to gain a more efficient procedure for generating a hard
instance. We provide a technique for building an exponential set (in the
number of additional bits added to the found instance)
of hard instances of the problem.



ISSN 1433-8092 | Imprint