My Research Interests

I graduated in Computer Science at the University of Milan on March 12th, 1998.
My master thesis was titled " Funzioni computabili da circuiti a soglia di profonditÓ costante" (that is, "Functions Computable by Constant Depth Threshold Circuits"), and explored the capability of small constant-depth (mainly 2 and 3 layers) polynomial-size threshold circuits to compute some interesting boolean functions.
If you want to know more about the subject, and you speak Italian, you can download the (gzipped) Postscript version of the thesis.

Soon after discussing my thesis, I have found a family of orthonormal bases for vector spaces R^{4^n} (for every integer n >= 1) that allows to extend the spectral techniques used to design threshold circuits to depth-3 threshold circuits; the previous use of spectral techniques led to (at most) depth-2 threshold circuits.
This result has been presented at ICTCS '98 (the 6th Italian Conference on Theoretical Computer Science - Prato, November 9th-11th). A successive extension of this result (showing that there exist depth-3 threshold circuits for which spectral techniques fail) has been submitted for publication; the Postscript version of this paper can be downloaded by clicking here.

Waiting for the competition to access the Ph.D. courses, I have participated to the FOOD (Fuzzy Object Oriented Database) project, in collaboration with Dr. Gloria Bordogna and Dr. Gabriella Pasi from the Institute of Information and Multimedia Technologies (ITIM) of CNR (the Italian National Council of Researches). The project was aimed at introducing into an object oriented database management system the capability to process vague, imprecise and uncertain information; the goal was reached by defining and implementing vague attributes into the classes, and by processing them through the use of fuzzy logic and possibility theory.
The results obtained in the project are described in a paper, currently submitted for publication.

Another area of interest is the comparison of the expressive power of relational databases with graph-oriented and object-oriented databases. A paper that describes a unifying framework for the study of the expressive power of databases has been submitted for publication. In such paper, two new characterizations of the set of relations that can be expressed from a given relational database are given, alternative to the one given by J. Paredaens in 1978.

Another area of interest is Quantum Computing. Such new paradigm of computation allows to extend classical computing devices in very interesting ways; I think that the investigation of the computational power of quantum devices will allow us to better understand the computational power of classical devices as well, no matter if a practical quantum computer will ever be built or not.
In particular, I am interested into the comparison of quantum circuits vs. classical circuits.

Last, but not the least, I am interested in Cryptography, both Applied and Theoretical (that is, viewed as a branch of Theoretical Computer Science and Complexity Theory). The subject of my Ph.D. thesis will probably be the use of digital signatures and zero-knowledge interactive proofs as authentication tools.

Future work, apart from cryptography and the Ph.D. thesis, will be devoted into looking for new bases for vector spaces R^{2^n} that allow (hopefully) to further extend the spectral techniques currently used to design constant-depth, polynomial-size threshold circuits.
Another work about circuit complexity is the investigation of a conjecture concerning the recognition of regular languages by means of constant-depth, polynomial-size threshold circuits.
Finally, I am currently working with Prof. Gianpiero Cattaneo and Roberto Leporini to define some gates for reversible and conservative many valued logics.

Go to top