Uri Feige
A computational problem is any kind
of problem that a computer may solve, such as multiplying two numbers, selecting
a move in a chess position, or sorting a list of names by alphabetical order.
Computational complexity is the area of classifying computational problems by
the amount of computational resources (such as amount of computer memory, or
number of time steps) used for their solution. It attempts to give a high level
view of the inherent complexity of computational problems, ignoring details
that may depend on the actual hardware on which computation is performed. For
example, it can be shown in an exact mathematical sense, that playing chess-like
games perfectly is a computational task that is considerably more complex than
multiplying numbers.
For some problems, finding exact (or optimal) solutions is computationally hard. One way of coping with computational hardness is by settling for approximate (or near-optimal) solutions. Much of my research investigates this approach. One of the most surprising results in this area, is that for a large number of computational problems, finding near optimal solutions is essentially as hard as finding optimal solutions. For such problems I seek other ways of coping with their computational hardness.
Recent Publications
- Approximating the bandwidth via volume respecting embeddings. Journal of Computer and Systems Sciences 60(3) (2000) 510-539.
- [with J. Kilian] Heuristics for semi-random graph problems. Journal of Computer and Systems Sciences 63 (2001) 639-671.
- Relations between average case complexity and approximation complexity. In the Proceedings of 34th Annual Symposium on Theory of Computing (2002) 534-543.