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