Publications on Journals
A. Andreev, A. Clementi, P. Crescenzi, S. De Agostino, E. Dhalhaus and J.
Rolim, "The Parallel Complexity of Approximating the High Degree Subgraph
Problem", Theoretical Computer Science, to appear (1997).
A. Andreev, A. Clementi, J. Rolim, and L. Trevisan "Weak Random Sources,
Hitting Sets, and BPP Simulation",
SIAM J. of Computing., to appear (1997).
A. Andreev, A. Clementi and J. Rolim, "A New General Derandomization
Method",
Journal of the A.C.M, to appear (1997).
A. Clementi and L. Trevisan, "Improved Non-approximability Results
for Vertex Cover Problems with Density Constraints", Theoretical
Computer Science, to appear (1997).
A. Andreev, A. Clementi and J. Rolim, "Optimal bounds for the approximation
of boolean functions and some applications", Theoretical
Computer Science, 180, 243-268 (1997).
A. Clementi and M. Di Ianni, "On the hardness of approximating optimum
schedule problems in store and forward networks", IEEE/ACM Transaction
on Networking, 4, 272 - 280 (1996).
A. Andreev, A. Clementi and J. Rolim, "Constructing the highest degree
subgraph problem for dense graphs is in NCAS", Theoretical Computer
Science, 161, 307-314 (1996).
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).
A. Clementi and M. Di Ianni, "Optimum Schedule Problems in Store and Forward
Networks",
Intern. J. of Foundations of Computer Science, 6.2, 155-168 (1995).
A. Clementi, P. Mentrasti and P. Pierini, "Some results on invertible cellular
automata",
Complex Systems, 9 .3, 235-250 (1995).
A. Clementi and R. Impagliazzo, "The reachability problem for finite
cellular automata", Information Processing Letters, 53 (1) 27-
31 (1995).
A. Clementi, G. de Biase, A. Massini, "Fast parallel arithmetic on
cellular automata'',
Complex Systems, 8, 435-441 (1995).
Publications on Conference Proceedings
A. Andreev, A. Clementi , J. Rolim and L. Trevisan, "Weak Random Sources,
Hitting Sets, and BPP Simulation", XXXVIII - IEEE - Foundations of Computer
Science (FOCS'97), 264-273 (1997).
A. Andreev, A. Clementi and J. Rolim, "Worst-case hardness suffices
for
derandomization: a new method for hardness-randomness trade-offs",
Proc. of XXIV Intern. Coll. on Automata, Languages, and Programming
(ICALP'97) Springer-Verlag LNCS, 1256, 177-187 (1997) (also available
in ECCC as TR96-055).
A. Andreev, A. Clementi and J. Rolim, "Efficient Constructions of Hitting
Sets for Systems
of Linear Functions", Proc. of XIV Symposium on Theoretical Aspects
of Computer Science
(STACS'97), Springer-Verlag LNCS, 1200, 387-398 (1997)
(also availale in ECCC
as TR96-029 ).
A. Andreev, A. Clementi and J. Rolim, "Hitting Sets derandomize BPP",
Proc. of XXIII Intern. Coll. on Automata, Languages, and Programming
(ICALP'96), Springer-Verlag, LNCS, 1099, 357-368 (1997) (also available
in ECCC as TR96-055).
A. Andreev, A. Clementi and J. Rolim, "Optimal bounds for the approximation
of boolean functions and some applications"Proc. of XIII Symposium on
Theoretical Aspects of Computer Science
(STACS'96), Springer-Verlag, LNCS, 1046, 319-330 (1996) (also
available in ECCC as TR95-041
).
A. Clementi and L. Trevisan, "Improved Non-approximability Results
for Vertex Cover Problems with Density Constraints", in Proc. of
the II Annual International Computing and Combinatorics Conference (COCOON'96),
Springer-Verlag, LNCS 1090, 333-342 (1996)
(also available in ECCC
as TR96-016).
A. Andreev, A. Clementi and J. Rolim, "On the parallel computations
of boolean functions on unrelated inputs", Proc. of the IV IEEE
Israel Symposium on Theory of Computing and Systems (ISTCS'96), IEEE,
155-161 (1996).
A. Andreev, A. Clementi, P. Crescenzi, S. De Agostino, E. Dhalhaus and J.
Rolim, "The Parallel Complexity of Approximating the High Degree Subgraph
Problem", Proc. of VI Annual Intern. Symp. on Algorithms and Computation
(ISAAC'95), LNCS, Springer-Verlag, 1004, 132-141 (1995).
A. Clementi and M. Di Ianni, ``Optimum Schedule Problems in Store and Forward
Networks'',
Proc. of IEEE-INFOCOM'94., 3, 1336-1343 (1994).
A. Clementi, P. Pierini and R. Impagliazzo, ``On the average-case complexity
of the reversibility problem for finite cellular automata'', Proc. of IEEE
- Workshop on Physics and Computation - PhysComp`94, 151-155,
(1994).
A. Clementi and R. Impagliazzo, "Graph theory and IP-protocols for
Reachability Problems on Finite Cellular Automata'', Proc. of II Italian
Conf. on Algorithms and Complexity (CIAC'94) , Springer-Verlag, LNCS, 778, 73-90,
Springer-Verlag, (1994).
Other Publications
D. Bovet, A. Clementi, P. Crescenzi and R. Silvestri, "Approximating
parallel algorithms for combinatorial optimization problems", II Chapter
of Parallel Algorithms for Combinatorial Optimization Problems, Springer-Verlag, LNCS,
1054, 7-24, Springer-Verlag (1996).
A. Clementi, On the Complexity of Cellular Automata., Ph.D.-Dissertation,
University of Rome "La Sapienza", (1994).