ANDREA
CLEMENTI
(Full Professor)
Dipartimento di Matematica
Universita' degli Studi di Roma
"TorVergata"
Research interests : Foundationsof Distributed
Computing, Randomized and Approximation Algorithms,De-randomization,
Computational Complexity.
Current
Research Projects:
·
European
Project AEOLUS
·
Italian COFIN 2008 PROJECT: “Uncoordinated
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
- 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
- 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 Networks. IPDPS-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
- A. Clementi,P. Penna and R. Silvestri. The
- 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.
- 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.