Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Shankar Kalyanaraman:

TR09-145 | 20th December 2009
Shankar Kalyanaraman, Chris Umans

The Complexity of Rationalizing Network Formation

We study the complexity of {\em rationalizing} network formation. In
this problem we fix an underlying model describing how selfish
parties (the vertices) produce a graph by making individual
decisions to form or not form incident edges. The model is equipped
with a notion of stability (or equilibrium), and we ... more >>>

TR08-021 | 3rd March 2008
Shankar Kalyanaraman, Chris Umans

The Complexity of Rationalizing Matchings

Given a set of observed economic choices, can one infer
preferences and/or utility functions for the players that are
consistent with the data? Questions of this type are called {\em
rationalization} or {\em revealed preference} problems in the
economic literature, and are the subject of a rich body of work.

... more >>>

TR07-059 | 6th July 2007
Shankar Kalyanaraman, Chris Umans

Algorithms for Playing Games with Limited Randomness

We study multiplayer games in which the participants have access to
only limited randomness. This constrains both the algorithms used to
compute equilibria (they should use little or no randomness) as well
as the mixed strategies that the participants are capable of playing
(these should be sparse). We frame algorithmic ... more >>>

TR06-128 | 5th October 2006
Shankar Kalyanaraman, Chris Umans

On obtaining pseudorandomness from error-correcting codes.

A number of recent results have constructed randomness extractors
and pseudorandom generators (PRGs) directly from certain
error-correcting codes. The underlying construction in these
results amounts to picking a random index into the codeword and
outputting $m$ consecutive symbols (the codeword is obtained from
the weak random source in the case ... more >>>

ISSN 1433-8092 | Imprint