Author name cluster
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
I&C Journal 2004 Journal Article
We show that not all sets in NP (or other levels of the polynomial-time hierarchy) have efficient average-case algorithms unless the Arthur-Merlin classes MA and AM can be derandomized to NP and various subclasses of P/poly collapse to P. Furthermore, other complexity classes like P(PP) and PSPACE are shown to be intractable on average unless they are easy in the worst case.
SAT Conference 2003 Conference Paper
Abstract The satisfiability problem of Boolean Formulae in 3-CNF (3-SAT) is a well known NP-complete problem and the development of faster (moderately exponential time) algorithms has received much interest in recent years. We show that the 3-SAT problem can be solved by a probabilistic algorithm in expected time O (1, 3290 n ). Our approach is based on Schöning’s random walk algorithm for k -SAT, modified in two ways.
MFCS Conference 1998 Conference Paper
Abstract We use the assumption that all sets in NP (or other levels of the polynomial-time hierarchy) have efficient average-case algorithms to derive collapse consequences for MA, AM, and various subclasses of P /poly. As a further consequence we show for C ∃ { P(PP), PSPACE } that C is not tractable in the average-case unless C=P.
TCS Journal 1995 Journal Article
It is shown that the assumption of NP having polynomial-size circuits implies (apart from a collapse of the polynomial-time hierarchy as shown by Karp and Lipton) that the classes AM and MA of Babai's Arthur-Merlin hierarchy coincide. This means that also a certain inner collapse of the remaining classes of the polynomial-time hierarchy occurs.