Publications

Recent Papers

Carles Boix, Bruno Codenotti, Giovanni Resta War, Wealth, and the Formation of States, in POlitical Economy and Institution, Springer Verlag 2011
Michele Budinich, Bruno Codenotti, Filippo Geraci, Marco Pellegrini: On the Benefits of Keyword Spreading in Sponsored Search Auctions: An Experimental Analysis. EC-Web 2010: 158-171
Bruno Codenotti, Stefano De Rossi, Marino Pagan: An experimental analysis of Lemke-Howson algorithm CoRR abs/0811.3247: (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).