Implicit computational complexity and probabilistic classes

The thesis applies the ICC tecniques to the probabilistic polinomial complexity classes in order to get an implicit characterization of them. The main contribution lays on the implicit characterization of PP (which stands for Probabilistic Polynomial Time) class, showing a syntactical characterisation of PP and a static complexity analyser able to recognise if an imperative program computes in Probabilistic Polynomial Time. The thesis is divided in two parts. The first part focuses on solving the problem by creating a prototype of functional language (a probabilistic variation of lambda calculus with bounded recursion) that is sound and complete respect to Probabilistic Prolynomial Time. The second part, instead, reverses the problem and develops a feasible way to verify if a program, written with a prototype of imperative programming language, is running in Probabilistic polynomial time or not. This thesis would characterise itself as one of the first step for Implicit Computational Complexity over probabilistic classes. There are still open hard problem to investigate and try to solve. There are a lot of theoretical aspects strongly connected with these topics and I expect that in the future there will be wide attention to ICC and probabilistic classes.

Extending Implicit Computational Complexity and Abstract Machines to Languages with Control

The Curry-Howard isomorphism is the idea that proofs in natural deduction can be put in correspondence with lambda terms in such a way that this correspondence is preserved by normalization. The concept can be extended from Intuitionistic Logic to other systems, such as Linear Logic. One of the nice conseguences of this isomorphism is that we can reason about functional programs with formal tools which are typical of proof systems: such analysis can also include quantitative qualities of programs, such as the number of steps it takes to terminate. Another is the possiblity to describe the execution of these programs in terms of abstract machines. In 1990 Griffin proved that the correspondence can be extended to Classical Logic and control operators. That is, Classical Logic adds the possiblity to manipulate continuations. In this thesis we see how the things we described above work in this larger context.

Probabilistic Recursion Theory and Implicit Computational Complexity

In this thesis we provide a characterization of probabilistic computation in itself, from a recursion-theoretical perspective, without reducing it to deterministic computation. More specifically, we show that probabilistic computable functions, i.e., those functions which are computed by Probabilistic Turing Machines (PTM), can be characterized by a natural generalization of Kleene's partial recursive functions which includes, among initial functions, one that returns identity or successor with probability 1/2. We then prove the equi-expressivity of the obtained algebra and the class of functions computed by PTMs. In the the second part of the thesis we investigate the relations existing between our recursion-theoretical framework and sub-recursive classes, in the spirit of Implicit Computational Complexity. More precisely, endowing predicative recurrence with a random base function is proved to lead to a characterization of polynomial-time computable probabilistic functions.

Parieto-occipital suppression eliminates implicit bidirectionality in grapheme-colour synaesthesia

Synaesthesia is a condition in which the input of one sensory modality triggers extraordinary additional experiences. On an explicit level, subjects affected by this condition normally report unidirectional experiences. In grapheme-colour synaesthesia for example, the letter A printed in black may trigger a red colour experience but not vice versa. However on an implicit level, at least for some types of synaesthesia, bidirectional activation is possible. In this study we tested whether bidirectional implicit activation is mediated by the same brain areas as explicit synaesthetic experiences. Specifically, we demonstrated suppression of implicit bidirectional activation with the application of transcranial magnetic stimulation over parieto-occipital brain areas. Our findings indicate that parieto-occipital regions are not only involved in explicit but also implicit synaesthetic binding.

Implicit Memory for Music in Alzheimer's Disease

Short, unfamiliar melodies were presented to young and older adults and to Alzheimer's disease (AD) patients in an implicit and an explicit memory task. The explicit task was yes–no recognition, and the implicit task was pleasantness ratings, in which memory was shown by higher ratings for old versus new melodies (the mere exposure effect). Young adults showed retention of the melodies in both tasks. Older adults showed little explicit memory but did show the mere exposure effect. The AD patients showed neither. The authors considered and rejected several artifactual reasons for this null effect in the context of the many studies that have shown implicit memory among AD patients. As the previous studies have almost always used the visual modality for presentation, they speculate that auditory presentation, especially of nonverbal material, may be compromised in AD because of neural degeneration in auditory areas in the temporal lobes.

Tracking the implicit self using event-related potentials

Negative biases in implicit self-evaluation are thought to be detrimental to subjective well-being and have been linked to various psychological disorders, including depression. An understanding of the neural processes underlying implicit self-evaluation in healthy subjects could provide a basis for the investigation of negative biases in depressed patients, the development of differential psychotherapeutic interventions, and the estimation of relapse risk in remitted patients. We thus studied the brain processes linked to implicit self-evaluation in 25 healthy subjects using event-related potential (ERP) recording during a self-relevant Implicit Association Test (sIAT). Consistent with a positive implicit self-evaluation in healthy subjects, they responded significantly faster to the congruent (self-positive mapping) than to the incongruent sIAT condition (self-negative mapping). Our main finding was a topographical ERP difference in a time window between 600 and 700 ms, whereas no significant differences between congruent and incongruent conditions were observed in earlier time windows. This suggests that biases in implicit self-evaluation are reflected only indirectly, in the additional recruitment of control processes needed to override the positive implicit self-evaluation of healthy subjects in the incongruent sIAT condition. Brain activations linked to these control processes can thus serve as an indirect measure for estimating biases in implicit self-evaluation. The sIAT paradigm, combined with ERP, could therefore permit the tracking of the neural processes underlying implicit self-evaluation in depressed patients during psychotherapy.