Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Nikhil R. Devanur:

TR08-046 | 14th April 2008
Nikhil R. Devanur, Lance Fortnow

A Computational Theory of Awareness and Decision Making

We exhibit a new computational-based definition of awareness,
informally that our level of unawareness of an object is the amount
of time needed to generate that object within a certain environment.
We give several examples to show this notion matches our intuition
in scenarios where one organizes, accesses and transfers
more >>>

TR06-029 | 21st February 2006
Diptarka Chakraborty, Nikhil R. Devanur, Vijay V. Vazirani

Eisenberg-Gale Markets: Rationality, Strongly Polynomial Solvability, and Competition Monotonicity

We study the structure of EG[2], the class of Eisenberg-Gale markets
with two agents. We prove that all markets in this class are rational and they
admit strongly polynomial algorithms whenever
the polytope containing the set of feasible utilities of the two agents can be described
via a combinatorial LP. ... more >>>

ISSN 1433-8092 | Imprint