ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > AUTHORS > NIKHIL R. DEVANUR:
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
Deeparnab Chakrabarty, 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