All reports by Author Bruno Codenotti:

__
TR06-012
| 17th January 2006
__

Bruno Codenotti, Mauro Leoncini, Giovanni Resta#### Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games

__
TR05-055
| 19th May 2005
__

Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye#### Leontief Economies Encode Nonzero Sum Two-Player Games

__
TR03-081
| 10th October 2003
__

Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta Barneva, Mauro Leoncini#### Computation of the Lov\'asz Theta Function for Circulant Graphs

__
TR02-071
| 6th June 2002
__

Bruno Codenotti, Igor E. Shparlinski#### Non-approximability of the Permanent of Structured Matrices over Finite Fields

__
TR97-043
| 25th September 1997
__

Bruno Codenotti, Pavel Pudlak, Giovanni Resta#### Some structural properties of low rank matrices related to computational complexity

Revisions: 1
,
Comments: 1

Bruno Codenotti, Mauro Leoncini, Giovanni Resta

It is known that finding a Nash equilibrium for win-lose bimatrix

games, i.e., two-player games where the players' payoffs are zero

and one, is complete for the class PPAD.

We describe a linear time algorithm which computes a Nash

equilibrium for win-lose bimatrix games where the number of winning

positions ...
more >>>

Bruno Codenotti, Amin Saberi, Kasturi Varadarajan, Yinyu Ye

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 >>>

Valentin E. Brimkov, Bruno Codenotti, Valentino Crespi, Reneta Barneva, Mauro Leoncini

The Lov\'asz theta function $\theta(G)$ of a graph $G$ has attracted a lot of attention for its connection with diverse issues, such as communicating without errors and computing large cliques in graphs. Indeed this function enjoys the remarkable property of being computable in polynomial time, despite being sandwitched between clique ... more >>>

Bruno Codenotti, Igor E. Shparlinski

We show that for several natural classes of ``structured'' matrices, including symmetric, circulant, Hankel and Toeplitz matrices, approximating the permanent modulo a prime $p$ is as hard as computing the exact value. Results of this kind are well known for the class of arbitrary matrices; however the techniques used do ... more >>>

Bruno Codenotti, Pavel Pudlak, Giovanni Resta

We consider the conjecture stating that a matrix with rank

$o(n)$ and ones on the main diagonal must contain nonzero

entries on a $2\times 2$ submatrix with one entry on the main

diagonal. We show that a slightly stronger conjecture implies

that ...
more >>>