Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

All reports by Author Leslie G. Valiant:

TR06-120 | 12th September 2006
Leslie G. Valiant


Living cells function according to complex mechanisms that operate in different ways depending on conditions. Evolutionary theory suggests that such mechanisms evolved as a result of a random search guided by selection and realized by genetic mutations. However, as some observers have noted, there has existed no theory that would ... more >>>

TR05-099 | 9th September 2005
Leslie G. Valiant

Holographic Algorithms

Complexity theory is built fundamentally on the notion of efficient
reduction among computational problems. Classical
reductions involve gadgets that map solution fragments of one problem to
solution fragments of another in one-to-one, or
possibly one-to-many, fashion. In this paper we propose a new kind of
reduction that allows for gadgets ... more >>>

TR05-004 | 3rd January 2005
Leslie G. Valiant

Memorization and Association on a Realistic Neural Model

A central open question of computational neuroscience is to identify the data structures and algorithms that are used in mammalian cortex to support successive acts of the basic cognitive tasks of memorization and association. This paper addresses the simultaneous challenges of realizing these two distinct tasks with the same data ... more >>>

ISSN 1433-8092 | Imprint