We consider the computational complexity of the market equilibrium
problem by exploring the structural properties of the Leontief
exchange economy. We prove that, for economies guaranteed to have
a market equilibrium, finding one with maximum social welfare or
maximum individual welfare is NP-hard. In addition, we prove that
counting the ... more >>>

Inspired by Feige ({\em 36th STOC}, 2004),
we initiate a study of sublinear randomized algorithms
for approximating average parameters of a graph.
Specifically, we consider the average degree of a graph
and the average distance between pairs of vertices in a graph.
Since our focus is on sublinear algorithms, ... more >>>

We survey recent results on disjoint NP-pairs. In particular, we survey the relationship of disjoint NP-pairs to the theory of proof systems for propositional calculus.

more >>>