Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR05-057 | 19th May 2005
Venkatesan Guruswami, Valentine Kabanets

Hardness amplification via space-efficient direct products

We prove a version of the derandomized Direct Product Lemma for
deterministic space-bounded algorithms. Suppose a Boolean function
$g:\{0,1\}^n\to\{0,1\}$ cannot be computed on more than $1-\delta$
fraction of inputs by any deterministic time $T$ and space $S$
algorithm, where $\delta\leq 1/t$ for some $t$. Then, for $t$-step
walks $w=(v_1,\dots, v_t)$ ... more >>>


TR05-056 | 25th April 2005
Alexis Kaporis, Efpraxia Politopoulou, Paul Spirakis

The Price of Optimum in Stackelberg Games

Consider a system M of parallel machines, each with a strictly increasing and differentiable load dependent latency function. The users of such a system are of infinite number and act selfishly, routing their infinitesimally small portion of the total flow r they control, to machines of currently minimum delay. It ... more >>>


TR05-055 | 19th May 2005
Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye

Leontief Economies Encode Nonzero Sum Two-Player Games

We give a reduction from any two-player game to a special case of
the Leontief exchange economy, with the property that the Nash equilibria of the game and the
equilibria of the market are in one-to-one correspondence.

Our reduction exposes a potential hurdle inherent in solving certain
families of market ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint