Bruno CODENOTTI
Research Director
Istituto di Informatica e Telematica
Consiglio Nazionale delle Ricerche
Pisa, Italy
Phone: +39-0503152401
Fax: +39-0503152333
Email: bruno.codenotti@iit.cnr.it
- Computation of Market Equilibria
- Computational Game Theory
- WEB Algorithmics
- Algorithms in Linear Algebra
- Distributed Computing
Extended Vita (ps file)
Coauthors (list with links)
- Editorial Board `ACM Journal of Computation Theory`
- Program Committee of ESA 07
- Program Committee of IBC'06
- Program Committee of
HICSS-39 Peer-to-Peer Infrastructures and Applications, 2006
- Program Committee of
WINE 2005
- Program Committee of IBC'05
- Program Committee of MFCS 2004
- Program Committee of HICSS-38 Peer-to-Peer Infrastructures and Applications, 2005
- Program Committee of HICSS-37
Peer-2-Peer Ecommerce Systems and Applications, 2004
- Program Committee of ECT 2004
- Program Committee of Fourth International Workshop on
Global and Peer-to-Peer Computing, April 2004
- 48th Midwest Theory Day
- I am writing a book on Computation and Game Theory for
Cambridge University Press.
Recent Talks:
Publications
Most Recent Papers (2004-2008)
- The Complexity of Equilibria: Hardness Results for Economies via a Correspondence with Games
(with A. Saberi, Y. Ye, K. Varadarajan), Theoretical Computer Science, 408, pp. 188-198 (2008) (Journal version of SODA paper).
- An Experimental Study of
Different Approaches to Solve the Market Equilibrium Problem
(with B. McCune, S. Pemmaraju, R. Raman, K. Varadarajan), ACM Journal of Experimental Algorithmics, Vol. 12 (August 2008). (Journal version that combines two previous
conference papers)
- An Optimal Multiprocessor Combinatorial Auction Solver (with S. Yang and A. Segre), Computers and Operations Research, Volume 36, Issue 1, January 2009, Pages 149-166.
- Computation of Market Equilibria by Convex Programming (with K. Varadarajan).
In `Algorithmic Game Theory`,
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V. Vazirani, Editors,
Cambridge University Press, September 2007, pp. 135-159.
- Military Competition, Types of Wealth and State Formation: An Agent-Based Model (with C. Boix and G. Resta). Preliminary version of the paper with the simulation of the evolution of the number of states. Presented at the 102nd American Political Science Association Annual Meeting, 2006.
- Efficient Computation of Nash Equilibria for Very Sparse Win-Lose Games
(with M. Leoncini and G. Resta). Electronic Colloquium on
Computational Complexity, Report TR06-012. ESA 2006.
- Computing Equilibrium Prices in Exchange Economies with Tax Distortions
[Posted on 1/13/06]
Preliminary version of the paper with efficient algorithms for some models of economies with taxes
on consumption (with L. Rademacher and K. Varadarajan). ICALP 2006.
-
Leontief Economies Encode Nonzero Sum Two-Player Games [Posted on
5/20/05] Preliminary version on the paper showing the
one-to-one correspondence between Nash equilibria in bimatrix
games and market equilibria in certain Leontief economies
(with A. Saberi, K. Varadarajan, Y. Ye). Electronic Colloquium on
Computational Complexity, Report TR05-055. SODA 2006.
- Computing Equilibrium Prices: Does
Theory Meet Practice? [Posted on 4/12/05] Preliminary version
of the paper with experiments on the computation of market equilibria,
where we explore the gray zone between the general problem and the
poly-time solvable special cases (with B. McCune, R. Raman, and K.
Varadarajan). ESA 2005 -- Engineering and Applications Track.
- Market Equilibrium via the Excess
Demand
Function [Posted on 11/07/04]
Preliminary version of the paper with a discrete
version of tatonnement which runs in poly time and other results
(with B. McCune and K. Varadarajan). STOC 2005.
- Existence, Multiplicity and Computation of
Equilibria for CES Exchange Economies [Posted on
06/27/05]
This paper includes convex programs
characterizing equilibria for CES functions - some do not
satisfy WGS - and results on the existence of equilibria for
CES functions
(with B. McCune, S. Penumatcha, and K. Varadarajan). FSTTCS 2005.
It also simplifies an earlier unpublished version
Market Equilibrium in Exchange Economies with Some Families
of Concave Utility Functions [Posted on 11/04/04], that was
presented at the
DIMACS Workshop on Large Scale Games, April 2005.
- Algorithms Column: The Computation of
Market Equilibria [Posted on 11/10/04] Survey on the Computation
of Market Equilibria (with
S. Pemmaraju and K.
Varadarajan), ACM SIGACT News 35(4) December 2004.
- Experimental Analysis of Several Algorithms
for Market Equilibrium
Computation Preliminary version of the paper experimenting on
different
approaches to the computation of market equilibria (with B. McCune, S.
Pemmaraju, R. Raman, and K. Varadarajan). [Revised version posted on
10/04/04]. ALENEX 2005.
- Equilibrium for Exchange Markets Satisfying WGS [Revised version --
Posted
on 11/04/04] Preliminary version of the paper on
the polynomial time computation of equilibria for exchange
economies satisfying weak gross substitutability (with S. Pemmaraju, K. Varadarajan).
SODA 2005.
- Nash
Equilibria for (0,1) Bimatrix Games.[Revised version posted on
10/22/04] Preliminary
version of the paper on the computation of Nash equilibria
for win-lose bimatrix games (with D. Stefankovic). Information Processing
Letters, Volume 94, Issue 3, pp. 145-150 (2005).
- Equilibrium for Markets with Leontief Utilities.
Preliminary
version of the paper on the efficient computation of equilibrium prices for Fisher's markets
with Leontief utilities (with K. Varadarajan). ICALP 2004.
- Realistic Combinatorial Auctions. Preliminary
version of the paper on the generation of realistic data sets for
combinatorial auctions (with A. Bonaccorsi, N. Dimitri, M. Leoncini, G.
Resta, P. Santi). Proc. IEEE Conference on Electronic
Commerce (CEC), Newport Beach, CA, pp. 331-338 (June 2003).
- Distributed Web Crawler. Preliminary version of
the paper describing the software architecture of UbiCrawler (with P.
Boldi, M. Santini, S. Vigna). Software - Practice and Experience, 32(8):711-726, 2004.
Some less recent papers are on line here
Some Older Papers
- B. Codenotti, I. Gerace, G. Resta ``Some remarks on the
Shannon capacity of odd cycles'', Ars Combinatoria, Vol. 66 (2003).
- B. Codenotti, I. E. Shparlinski, A. Winterhof, ``Non-approximability
of the Permanent of Structured Matrices over Finite Fields'',
Computational Complexity, 11, 158-170 (2002).
- Codenotti,B. Resta,G. ``Computation of sparse circulant permanents
via determinants'', Linear Algebra and Its Applications 355(1-3),
pp.15-34 (2002).
- B. Codenotti, M. Leoncini, F.P. Preparata, ``The role of arithmetic
in fast parallel matrix inversion'', Algorithmica, Vol. 3(4) 2001,
pp. 685-707.
- A. Bernasconi, B. Codenotti, J.M. VanderKam, ``A Characterization of
Bent Functions in terms of Strongly Regular Graphs'', IEEE
Transactions on Computers 50(9), pp. 984-985 (2001).
- B. Codenotti, P. Pudl\'ak, G. Resta ``Some structural properties of
low rank matrices related to computational complexity'', Theoretical
Computer Science, Vol: 235 (1) (2000), pp. 89-107.
- B.Codenotti, G. Del Corso, G. Manzini, ``Matrix Rank and
Communication Complexity'', Linear Algebra and its Applications 304
(1-3) (2000), 193--200.
- B.Codenotti, ``Matrix Rigidity'', Linear Algebra and its
Applications, 304 (1-3) (2000), 181--192.
- A. Bernasconi, B. Codenotti, ``Spectral Analysis of Boolean
Functions as a Graph Eigenvalue Problem'', IEEE Transactions on
Computers, Vol. 48(3) (1999), 345-351.
- B.Codenotti, I. Gerace, S. Vigna, ``On Some Combinatorial Questions
Related to Circulant Graphs'', Linear Algebra and its Applications,
285 (1998), 123-142.
- I. Bar On, B. Codenotti, M.Leoncini, ``A Fast Parallel Cholesky
Decomposition Algorithm for Tridiagonal Symmetric Matrices'', SIAM
Journal on Matrix Analysis, Vol. 18(2) (1997) 403-418.
- B. Codenotti, F.Erg\"un, P. Gemmell, R.Kumar, ``Checking Properties
of Polynomials'', ICALP 97.
- G. Bilardi, B. Codenotti, G. Del Corso, C. Pinotti, G. Resta,
``Broadcast and Other primitive Operations on Fat Trees'', EUROPAR
97.
- B. Codenotti, L. Margara, ``Transitive Cellular Automata are
Sensitive to Initial Conditions'', American Mathematical Monthly, 1
(1996), 60-64.
- P. Boldi,B. Codenotti, P. Gemmell, S. Shammah, J. Simon, S. Vigna,
``Symmetry Breaking in Anonymous Networks: Characterizations'', Proc
4th Israel Symposium on Theory of Computing and Systems, pp. 16-26
(1996).
- B. Codenotti, G.Manzini, L. Margara, G. Resta ``Perturbation:
An Efficient
technique for the Solution of Very Large Instances of the TSP'',
INFORMS Journal on Computing, Vol. 8 (2) 1996.
- Bar On, I. Codenotti, B. Leoncini, M. ``Checking robust
nonsingularity of Tridiagonal Matrices in linear time'', BIT 36:2 (1996)
206-220.
- Bar On, I. Codenotti, B. ``A Fast and Stable Parallel QR Algorithm
for Symmetric Tridiagonal Matrices'', Linear Algebra and its
Applications, 220 (1995) 63-95.
- M. Blum, B. Codenotti, P. Gemmell, T. Shahoumian, ``Self-Correcting
for Function Fields of Finite Transcendental Degree'', ICALP 95.
- B. Codenotti, P. Gemmell, J. Simon, ``Average Circuit Depth and
Average Communication Complexity'', ESA 95.
- Ar, S. Blum, M. Codenotti,B. Gemmell, P. ``Checking Approximate
Computations over the Reals'', STOC 93.
- Codenotti,B. Manzini, G, Margara, L., Resta,G. ``Global Strategies
for Augmenting the Efficiency of TSP Heuristics'', WADS 93.
- Codenotti,B. Tamassia,R. ``A Network Flow Approach to the
Reconfiguration of VLSI Arrays'', IEEE Transactions on Computers,
40(1) (1991) 118-121.
- Codenotti,B. Leoncini,M. ``Matrix Inversion in $RNC^1$'', Journal
of Complexity, 7 (1991), 282-295.
- Codenotti,B. Lotti,G. Romani,F. ``Area-Time Tradeoffs for Matrix
Vector Multiplication'', Journal of Parallel and Distributed
Computing 8 (1990) 52-59.
- Codenotti,B. Lotti,G. ``A Fast Algorithm for the Division of Two
Polynomial Matrices'', IEEE Transactions on Automatic Control, 34
(1989), 446-448.
- Codenotti,B. Flandoli,F. ``A Monte Carlo Method for the Parallel
Solution of Linear Systems'', Journal of Complexity, 5 (1989),
107-117.
- Bevilacqua,R. Codenotti,B. Romani,F. ``Parallel Solution of Block
Tridiagonal Linear Systems'', Linear Algebra and its Applications,
104 (1988), 39-57.
Books: 
- Codenotti,B. Leoncini,M. ``Fondamenti di Calcolo
Parallelo", (in Italian) Milano, Addison Wesley (1990).
- Codenotti,B. Leoncini,M. Parallel
Complexity of Linear System
Solution Singapore, World Scientific Publishing Company,
(1991).
- Codenotti,B. Leoncini,M. Introduction to
Parallel Processing,
(translation of a revised version of ``Fondamenti di Calcolo
Parallelo'') Addison Wesley (1993).
- Bernasconi, A. Codenotti, B. ``
Introduzione
alla Complessita' Computazionale'', (in Italian),
Springer Verlag (1998).
- Bernasconi, A. Codenotti, B. Resta, G.
``Metodi
Matematici in Complessita'
Computazionale'', (in Italian), Springer Verlag (1999).
Sparse photos with family and friends