The following paper shows that (unless the polynomial hierarchy collapses)
it is hard to guess even partial information about the permanent of a random
Uriel Feige and Carsten Lund.
On the Hardness of Computing the Permanent of Random Matrices.
Computational Complexity 6 (1996/1997) 101-132.
Suppose that two computationally unlimited experts give conflicting advice
to a computationally limited referee.
How can the referee decide which expert to believe?
The following paper suggests procedures by which the referee can reject one
of the experts.
Uriel Feige and Joe Kilian.
Making games short.
Proceedings of 29th STOC, 1997, 506--516.
The following paper suggests simple protocols for selecting a leader in the
full information model in the presence of a minority of cheating players.
It also proves that for these protocols, the probability of choosing an
honest leader (as a function of the fraction of players that are honest)
is close to optimal.
Noncryptographic selection protocols.
Proceedings of 40th FOCS, 1999, 142--152.
The following paper proves a new inequality in probability theory, that bounds the probability that the sum of independent random variables significantly exceeds its expectation. It also presents the application that motivated the development of the new inequality. It concerns estimating the average degree of a graph by sampling the degrees of random vertices.
On sums of independent random variables with unbounded variance and estimating the average degree in a graph.
SIAM J. Comput. 35(4): 964-984 (2006).