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).