1

The complexity of symmetric Boolean parity Holant problems

Heng Guo,
Pinyan Lu,
Leslie G. Valiant

July 2011
ICALP'11: Proceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I

**Publisher:** Springer-Verlag

For certain subclasses of NP, ⊕P or #P characterized by local constraints, it is known that if there exist any problems that are not polynomial time computable within that subclass, then those problems are NP-, ⊕P- or #P-complete. Such dichotomy results have been proved for characterizations such as Constraint Satisfaction ...

2

The Extent and Limitations of Mechanistic Explanations of Nature

Leslie Valiant

June 2011
ACM Turing award lectures

**Publisher:** ACM

**Bibliometrics**:

Citation Count: 0

Downloads (6 Weeks): 578, Downloads (12 Months): 2,045, Downloads (Overall): 2,279

Full text available:

Mp4

3

Leslie G. Valiant

January 2011
Journal of Computer and System Sciences: Volume 77 Issue 1, January, 2011

**Publisher:** Academic Press, Inc.

Writing software for one parallel system is a feasible though arduous task. Reusing the substantial intellectual effort so expended for programming a second system has proved much more challenging. In sequential computing algorithms textbooks and portable software are resources that enable software systems to be written that are efficiently portable ...

**Keywords**:
Multi-core, Parallel algorithms, Bridging model, Bulk synchronous

4

Leslie G. Valiant

April 2010
LATIN'10: Proceedings of the 9th Latin American conference on Theoretical Informatics

**Publisher:** Springer-Verlag

We define the notion of diversity for families of finite functions, and express the limitations of a simple class of holographic algorithms in terms of limitations on diversity. We go on to describe polynomial time holographic algorithms for computing the parity of the following quantities for degree three planar undirected ...

5

Experience-induced neural circuits that achieve high capacity

Vitaly Feldman,
Leslie G. Valiant

October 2009
Neural Computation: Volume 21 Issue 10, October 2009

**Publisher:** MIT Press

Over a lifetime, cortex performs a vast number of different cognitive actions, mostly dependent on experience. Previously it has not been known how such capabilities can be reconciled, even in principle, with the known resource constraints on cortex, such as low connectivity and low average synaptic strength. Here we describe ...

6

Leslie G. Valiant

May 2009
TAMC '09: Proceedings of the 6th Annual Conference on Theory and Applications of Models of Computation

**Publisher:** Springer-Verlag

In this talk we shall first give a brief review of a quantitative approach to understanding neural computation [4-6]. We target so-called *random access* tasks, defined as those in which one instance of a task execution may need to access arbitrary combinations of items in memory. Such tasks are communication ...

7

Evolvability

Leslie G. Valiant

February 2009
Journal of the ACM (JACM): Volume 56 Issue 1, January 2009

**Publisher:** ACM

**Bibliometrics**:

Citation Count: 18

Downloads (6 Weeks): 4, Downloads (12 Months): 58, Downloads (Overall): 1,726

Full text available:

PDF

Living organisms function in accordance with complex mechanisms that operate in different ways depending on conditions. Darwin's theory of evolution suggests that such mechanisms evolved through variation guided by natural selection. However, there has existed no theory that would explain quantitatively which mechanisms can so evolve in realistic population sizes ...

**Keywords**:
PAC learning, Evolvable, SQ learning

8

A first experimental demonstration of massive knowledge infusion

Loizos Michael,
Leslie G. Valiant

September 2008
KR'08: Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning

**Publisher:** AAAI Press

A central goal of Artificial Intelligence is to create systems that embody commonsense knowledge in a reliable enough form that it can be used for reasoning in novel situations. Knowledge Infusion is an approach to this problem in which the commonsense knowledge is acquired by learning. In this paper we ...

9

A Bridging Model for Multi-core Computing

Leslie G. Valiant

September 2008
ESA '08: Proceedings of the 16th annual European symposium on Algorithms

**Publisher:** Springer-Verlag

We propose a bridging model aimed at capturing the most basic resource parameters of multi-core architectures. We suggest that the considerable intellectual effort needed for designing efficient algorithms for such architectures may be most fruitfully pursued as an effort in designing portable algorithms for such a bridging model. Portable algorithms ...

10

Holographic Algorithms

Leslie G. Valiant

February 2008
SIAM Journal on Computing: Volume 37 Issue 5, January 2008

**Publisher:** Society for Industrial and Applied Mathematics

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

**Keywords**:
enumeration, computational complexity

11

Evolvability

Leslie G. Valiant

August 2007
MFCS'07: Proceedings of the 32nd international conference on Mathematical Foundations of Computer Science

**Publisher:** Springer-Verlag

Living organisms function according to complex mechanisms that operate in different ways depending on conditions. Evolutionary theory suggests that such mechanisms evolved as result of a random search guided by selection. However, there has existed no theory that would explain quantitatively which mechanisms can so evolve in realistic population sizes ...

12

Accidental Algorthims

Leslie G. Valiant

October 2006
FOCS '06: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science

**Publisher:** IEEE Computer Society

We provide evidence for the proposition that the computational complexity of individual problems, and of whole complexity classes, hinge on the existence of certain solvable polynomial systems that are unlikely to be encountered other than by systematic explorations for them. We consider a minimalist version of Cook's 3CNF problem, namely ...

13

A Quantitative Theory of Neural Computation

Leslie G. Valiant

August 2006
Biological Cybernetics: Volume 95 Issue 3, August 2006

**Publisher:** Springer-Verlag New York, Inc.

We show how a general quantitative theory of neural computation can be used to explain two recent experimental findings in neuroscience. The first of these findings is that in human medial temporal lobe there exist neurons that correspond to identifiable concepts, such as a particular actress. Further, even when such ...

14

Knowledge infusion

Leslie G. Valiant

July 2006
AAAI'06: proceedings of the 21st national conference on Artificial intelligence - Volume 2

**Publisher:** AAAI Press

The question of how machines can be endowed with the ability to acquire and robustly manipulate commonsense knowledge is a fundamental scientific problem. Here we formulate an approach to this problem that we call knowledge infusion. We argue that robust logic offers an appropriate semantics for this endeavor because it ...

15

Completeness for parity problems

Leslie G. Valiant

August 2005
COCOON'05: Proceedings of the 11th annual international conference on Computing and Combinatorics

**Publisher:** Springer-Verlag

In this talk we shall review recent work on holographic algorithms and circuits. This work can be interpreted as offering formulations of the question of whether computations within such complexity classes as NP, ⊕P, BQP, or #P, can be efficiently computed classically using linear algebra. The central part of the ...

16

Holographic circuits

Leslie G. Valiant

July 2005
ICALP'05: Proceedings of the 32nd international conference on Automata, Languages and Programming

**Publisher:** Springer-Verlag

Holographic circuits are defined here to be circuits in which information is represented as linear superpositions. Holographic circuits when suitably formulated can be emulated on classical computers in polynomial time. The questions we investigate are those of characterizing the complexity classes of computations that can be expressed by holographic circuits.

17

Leslie G. Valiant

March 2005
Neural Computation: Volume 17 Issue 3, March 2005

**Publisher:** MIT Press

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 letter addresses the simultaneous challenges of realizing these two distinct tasks with the same data ...

18

Holographic Algorithms (Extended Abstract)

Leslie G. Valiant

October 2004
FOCS '04: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science

**Publisher:** IEEE Computer Society

We introduce a new notion of efficient reduction among computational problems. Classical reductions involve gadgets that map local solutions of one problem to local solutions of another in one-to-one, or possibly many-to-one or one-to-many, fashion. Our proposed reductions allow for gadgets with many-to-many correspondences. Their objective is to preserve the ...

19

Corrigendum: Corrigendum to "Expressiveness of matchgates"

Leslie G. Valiant

April 2003
Theoretical Computer Science: Volume 299 Issue 1-3, 18 April 2003

**Publisher:** Elsevier Science Publishers Ltd.

20

Corrigendum to “Expressiveness of matchgates”

Leslie G. Valiant

April 2003
Theoretical Computer Science: Volume 299 Issue 1, April 2003

**Publisher:** Elsevier Science Publishers Ltd.