span.SPELLE {mso-spl-e:yes;} span.GRAME {mso-gram-e:yes;} @list L0:level1 {mso-bidi-font-size:10pt;}

 

ANDREA CLEMENTI

(Full  Professor)
Dipartimento di Matematica
Universita' degli Studi di Roma "TorVergata"

 

 

  • 1990. Degree in Mathematics   at the University "La Sapienza'' of Rome
  • 1994. PhD in Computer Science,   University  "La Sapienza'' of Rome
  • 1996-1998 Research Associate at Department of Computer Science of  University  "La Sapienza'' of Rome
  • 1999-2003 Associate Professor at the Department of Mathematics,  University "Tor Vergata" of Rome
  • 2003 - Full Professor at the Department of Mathematics,  University "Tor Vergata" of Rome





Research interests : Foundationsof Distributed Computing, Randomized and Approximation Algorithms,De-randomization, Computational Complexity.

 

Current Research Projects:  

·         European Project AEOLUS

·         Italian COFIN 2008 PROJECT: “Uncoordinated Mobile Networks: Foundations and Basic CommunicationProtocols”.




Current Teaching Activities (In Italian)  (see http://www.informatica.uniroma2.it/index.htm)

·        (2009/2010):  Distributed Algorithms and Complex Networks

·        (2010/2011):

o        Algorithms and Data Structures II

o        Distributed Algorithms and Complex Networks

 

 

Publications: most of my publications are available by using the DBLP system at:

               http://www.informatik.uni-trier.de/~ley/db/indices/a-tree/c/Clementi:Andrea_E=_F=.html

 

Publications organized by topics

 

Distributed Computing and Theory of Communication Networks
 

- A. Clementi, A. Monti, and R. Silvestri.  Fast Flooding over Manhattan.   arXiv.org, Tech. Rep. arXiv:1002.3757v1,2010.

- A. Clementi, A. Monti, and R. Silvestri.  Modelling Mobility:  A Discrete Revolution.   arXiv.org, Tech. Rep. arXiv:1002.1016v1, 2010.

-  T. Calamoneri, A. Clementi  E. Fusco, R. Silvestri. Maximizing the Number of Broadcast Operations in Static Random Geometric Ad-Hoc Networks, IEEE Transactions On Parallel And Distributed Systems, 2010, (Preliminary version in OPODIS’07) to appear.

- A. Clementi,A. Monti, F. Pasquale, and R. Silvestri. Broadcasting in Dynamic Radio Networks. Journal of Computer and System Sciences, 75(4): 213-230, 2009.

- Andrea E.F. Clementi, Francesco Pasquale, and Riccardo Silvestri. MANETS: High mobility can make up for low transmission power. 36th ICALP'09, LNCS 5556,  2009.

- A. Clementi,A. Monti, F. Pasquale, and R. Silvestri. Information Spreading in Stationary Markovian Evolving Graphs.  23rd IEEE  IPDPS'09, 2009.

- T. Calamoneri, A. Clementi, A. Monti, G. Rossi, and R. Silvestri. Minimum-energy broadcast in random-grid ad-hoc networks: approximation and distributed algorithms.  11th  ACM MSWIM’08, 2008.

- T. Calamoneri  A. Clementi,  M. Di Ianni, M. Lauria, A.  Monti, and R. Silvestri.  Minimum-Energy Broadcast and disk cover in grid wireless networks. Theoretical Computer Science, 399(1-2), 2008 (Preliminary Version in SIROCCO’06).

- A. Clementi,C. Macci, A. Monti, F. Pasquale, and R. Silvestri. Flooding time in edge-Markovian dynamic graphs.  27th ACM PODC’08, 2008.

- A. Clementi,A. Monti, F. Pasquale, and  R. Silvestri.   Optimal Fault-Tolerant Deterministic Broadcast in Directed Geometric Radio Networks.    32nd MFCS'07, LNCS 4708, 2007.

- A.  Clementi, A. Monti, F. Pasquale, and R. Silvestri. 
Communication in Dynamic Radio Networks. 26th ACM  PODC'07, 2007.

- T.Calamoneri  A. Clementi,  M. Di Ianni, M. Lauria, A.  Monti, and R. Silvestri. Minimum Energy Broadcast and Disk Cover in Grid Wireless Networks.    Theoretical Computer Science, 384(2-3), 2007, (Preliminary version in  SIROCCO’05).


- Clementi A., Di Ianni M, Lauria M, Monti A, Rossi R, Silvestri R .
A Distributed Protocol for the Bounded-Hops Converge-Cast in Ad-HocNetworks.  5th ADHOC-NOW '06, LNCS 4104, 2006.

-  T. Calamoneri  A. Clementi,  M.Di Ianni, M. Lauria, A.  Monti, andR. Silvestri. Minimum Energy Broadcast and Disk Cover in Grid Wireless Networks. SIROCCO’06, LNCS, 2006.


- C. Ambuhel, A. Clementi, P. Penna, G. Rossi, R. Silvestri.
On the approximability of the range assignment problem on radio networks in presence of selfish agents. Theoretical Computer Science,  343, 2005 (Preliminary version in SIROCCO’03).

- Clementi A.,M. Di Ianni, A. Monti, Rossi G, R. Silvestri  Experimental Analysis of Practically Efficient Algorithms for Bounded-Hop Accumulation in Ad-Hoc Wireless Networks.  5th IEEE WMAN'05,  2005.

- A. Clementi, P. Penna, and R. Silvestri. On the Power Assignment Problem in Radio Networks, Mobile Networks and Applications (MONET),  9(2), 2004  (Preliminary versions in STACS’00 and RANDOM-APPROX’01).


- A. E. F. Clementi, A. Monti, and R.  Silvestri.  Round Robin is optimal for fault-tolerant broadcasting on wireless networks.  
J. Parallel Distrib. Comput. 64(1), 89-96, 2004.  (Preliminary Version in ESA'01).

- C. Ambühl, A. Clementi, M. Di Ianni, N. Lev-Tov, A. Monti, D. Peleg, G. Rossi and R. Silvestri.
 Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks
  STACS'04, LNCS,  2004.

-  C. Ambühl, A. Clementi, M. Di Ianni, G. Rossi, A. Monti, R. Silvestri. The Range Assignment Problem in Non-Homogeneous Static Ad-Hoc Networks. IEEE  IPDPS-WMAN’04, 2004

- A.E.F. Clementi, A. Monti, and R. Silvestri. Distributed broadcast in radio networks of unknown topology.
  Theoretical Computer Science
, 302, 2003.  (Preliminary versions in  ACM-SIAM  SODA'01 and ACM PODC'01).

- A. 
Clementi, P. Penna, A.Ferreira, S. Perennes, R. Silvestri.  The Minimum Range Assignment Problem on Linear Radio Networks. Algorithmica 35(2), 2003.
 
 
- A.  Clementi, G. Huiban, P. Penna, G.
Rossi and Y. C. Verhoeven.  On the Approximation Ratio of the MST-based Heuristic for the Energy-Efficient Broadcast Problem in Static Ad-Hoc Radio NetworksIPDPS-WMAN '03, 2003.

- A. Clementi, A. Monti, R. Silvestri. Optimal F-Reliable Protocols for the Do-All Problem on Single-Hop Wireless Networks. ISAAC’02, LNCS, 2002.


- A.  Clementi, G. Huiban, P.Penna, G. Rossi and Y.C. Verhoeven.
Some Recent Theoretical Advances and Open Questions on Energy Consumption in Ad-Hoc Wireless Networks. Proc. of ARACNE'02,    23-38, 2002.


- A. Clementi, A. Monti, and R. Silvestri. Distributed Multi-Broadcast in Unknown Radio Networks. 20th ACM PODC'01
, 2001.
 

- A. Clementi, A. Monti, and R. Silvestri. Selective Families, Superimposed Codes, and Broadcasting in Unknown Radio Networks. 12th ACM-SIAM SODA'01,  2001.
 

- A. Clementi, P. Crescenzi, P. Penna, G. Rossi and P. Vocca. On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs.   18th STACS'01,  LNCS 2010,   2001.

 
- A. Clementi, A. Monti, and R. Silvestri.  Round Robin is Optimal forFault-Tolerant  Broadcasting on Wireless Networks . In 9th  ESA'01
,  LNCS, 2001.
 

- A. Clementi, A. Ferreira, P. Penna, S.Perennes and R. Silvestri. The Minimum Range Assignment Problem on Linear RadioNetworks.   8th  ESA'00, LNCS 1879,  2000.

- A. Clementi,P. Penna and R. Silvestri. The Power Range Assignment Problem in Radio Networkson the Plane.  17th  STACS'00, LNCS 1770, 2000.
  
- A. Clementi, P. Penna and R. Silvestri. Hardness Results for The PowerRangeAssignment Problem in Packet Radio Networks. RANDOM-APPROX`99
, LNCS 1671, 1999.
 

- Clementi and  M. Di Ianni, On the hardness of approximating optimum scheduleproblems in store and forward networks. ACM/IEEE Transaction on Networking, 4, 272 - 280,  1996 (Preliminary version in INFOCOM’04).

 

 

Pseudorandomness and Randomized Computation
 

- A. Clementi, P. Crescenzi, A. Monti, P. Penna, and R. Silvestri. On Computing  Ad-Hoc Selective Families. 5th  RANDOM'01, LNCS, 2001.

- A.  Andreev, J. L. Baskakov, A. Clementi, J. D. P. Rolim. Small Pseudo-Random Sets Yield Hard Functions: New Tight Explict Lower Bounds for Branching Programs. ICALP’99, LNCS, 1999.

- A. Andreev, A. Clementi , J. Rolim and L. Trevisan, Weak Random Sources, Hitting Sets, and BPP Simulation. 
SIAM J. of Computing
, 28(6), 1999  (Extended Abstract in IEEE FOCS'97).

 - A. Andreev, A. Clementi and J. Rolim, Worst-case hardness suffices for derandomization: a new method for  hardness-randomness trade-offs.   Theoretical Computer Science, 221, 3-18, 1999 (Extended Abstract in ICALP'97).

- A. Andreev, A. Clementi and J. Rolim, A new general derandomization method,  J. of ACM, 45(1), 1998 (Extended Abstract in ICALP'96).

- A. Clementi, J. D. P. Rolim, L. Trevisan. Recent Advances Towards Proving P = BPP. Bulletin of the EATCS, 64, 1998.

- A. Andreev, A. Clementi and J. Rolim.  Efficient Constructions of Hitting Sets for Systems of Linear Functions.
XIV  STACS'97
, LNCS  1200, 387--398,  1997.

- A. Clementi, J. Rolim and L. Kucera,  A note on parallel randomized algorithms for searching problems,   AMS-DIMACS Series in Discrete Mathematics and Theoretical Computer Sciences, 22, 33-43, 1995.

 

 

Parallel and Randomized Algorithms 

- A. Clementi, G.Bongiovanni and P. Penna. A Note on Parallel Read Operations on Large Public Databases. In Intern. Workshop on Approximation and Randomized Algorithms in Communication Networks  (ARACNE'00),  Carleton Scientific Press, 2000.

- A. Andreev, A.Clementi, P. Penna and J. Rolim. Parallel Read Operations Without  Memory Contention. 
In.   TR00-053,   ECCC
, 2000.

- A. Andreev, A.Clementi, P. Penna, and J. Rolim.  Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines.  In   16th STACS`99,  LNCS  1563,  1999.

- A. Andreev, A. Clementi, and J. Rolim. Constructing the highest degree subgraph for dense graphs  is in NCAS. 
Theoretical Computer Science
, 161(1-2),  307-314, 1996.

 - A.Andreev, A. Clementi, and  J. Rolim. On the parallel computations of boolean functions on unrelated inputs.  IV IEEE Israel Symposium on Theory of Computing and Systems (ISTCS'96),  1996.

- D. Bovet, A. Clementi, P. Crescenzi, and R. Silvestri. Parallel approximation of optimization problems. Chapter of Solving Combinatorial Optimization Problems in Parallel, LNCS 1054, 1996.

- Andrea E. F.Clementi, and José D. P. Rolim, Erik Urland: Randomized parallel algorithms. Chapter of Solving Combinatorial Optimization Problems in Parallel, LNCS 1054, 1996.

- Alexander E.Andreev, Andrea E. F. Clementi, José D. P. Rolim: Constructing the HighestDegree Subgraph for Dense Graphs is in NCAS. Theor. Comput. Sci. 161(1&2):307-314 (1996).

- A. Clementi,G. de Biase, A. Massini. Fast parallel arithmetic on cellularautomata.   Complex Systems,8, 1995.

- A. Clementi,P. Mentrasti and P. Pierini. Some results on  invertible cellularautomata,   Complex Systems, 9 (3), 1995.


 


COMPUTATIONAL COMPLEXITY

- A. Clementi,P. Crescenzi, and G. Rossi. On the Complexity of Approximating Colored-GraphProblems.    IV COCOON'99,  LNCS 1627,  1999.

- A. Andreev, A.Clementi, P. Crescenzi, S. De Agostino, E. Dhalhaus and J.  Rolim. Theparallel complexity of approximating the high degree subgraph problem.Theoretical Computer Science, 205(1-2),  1998 (Extended Abstract in ISAAC'95).

- A. Clementiand L. Trevisan. Improved Non-approximability Results for Vertex Cover Problemswith Density Constraints. Theoretical Computer Science,  225, 1999 (Extended Abstract in COCOON'96).

- A. Andreev, A. Clementi and  J.  Rolim. Optimal bounds for the approximation of boolean functions and some applications.  TheoreticalComputer Science, 180, 243-268, 1997 (Extended Abstract in STACS'96).

- A. Clementi and R. Impagliazzo. Thereachability problem for finite cellular automata, Information ProcessingLetters,  53 (1),  27-31,1995.

- A. Clementi,P. Pierini and R. Impagliazzo. On the average-case  complexity of thereversibility problem for finite cellular automata''.   IEEE -Workshop on Physics and Computation (PhysComp`94),  1994.