8 citations · 15 across the 2 of their papers we have counts for
2 papers
cs.CC2008★ 7 cited
Frequency of Correctness versus Average-Case Polynomial Time and Generalized Juntas
Gabor Erdelyi, Lane A. Hemaspaandra, Joerg Rothe +1
We prove that every distributional problem solvable in polynomial time on the average with respect to the uniform distribution has a frequently self-knowingly correct polynomial-ti…
cs.GT2007★ 8 cited
On Approximating Optimal Weighted Lobbying, and Frequency of Correctness versus Average-Case Polynomial Time
Gabor Erdelyi, Lane A. Hemaspaandra, Joerg Rothe +1
We investigate issues related to two hard problems related to voting, the optimal weighted lobbying problem and the winner problem for Dodgson elections. Regarding the former, Chri…