## Selected other publications

References to some of my work appear below.
The links included are to personal copies (ps files) of
these papers on my home machine.
** These links do not lead to the
respective journal/conference proceedings.**
You are expected to respect all relevant copyright laws.

The following paper shows that (unless the polynomial hierarchy collapses)
it is hard to guess even partial information about the permanent of a random
matrix.

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.

Uriel Feige.

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.

Uriel Feige.

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