L G Valiant
L G Valiant

homepage

  Affiliation history
Bibliometrics: publication history
Average citations per article45.68
Citation Count4,248
Publication count93
Publication years1973-2011
Available for download31
Average downloads per article1,298.81
Downloads (cumulative)40,263
Downloads (12 Months)4,193
Downloads (6 Weeks)829
A. M. Turing Award Winner ACM Fellow
SEARCH
ROLE
Arrow RightAuthor only
· Editor only
· Advisor only
· All roles


AUTHOR'S COLLEAGUES
See all colleagues of this author

SUBJECT AREAS
See all subject areas



AUTHOR PROFILE PAGES
Project background Author-Izer logoAuthor-Izer Service

BOOKMARK & SHARE


94 results found Export Results: bibtex | endnoteacmrefcsv

Result 1 – 20 of 94
Result page: 1 2 3 4 5

Sort by:

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
Bibliometrics:
Citation Count: 3

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 published by ACM
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: Mp4Mp4

3
Leslie G. Valiant
January 2011 Journal of Computer and System Sciences: Volume 77 Issue 1, January, 2011
Publisher: Academic Press, Inc.
Bibliometrics:
Citation Count: 22

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
Bibliometrics:
Citation Count: 6

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
Bibliometrics:
Citation Count: 3

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
Bibliometrics:
Citation Count: 0

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 published by ACM
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: PDFPDF
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
Bibliometrics:
Citation Count: 1

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
Bibliometrics:
Citation Count: 24

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
Bibliometrics:
Citation Count: 32

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
Bibliometrics:
Citation Count: 5

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
Bibliometrics:
Citation Count: 42

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.
Bibliometrics:
Citation Count: 4

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
Bibliometrics:
Citation Count: 9

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
Bibliometrics:
Citation Count: 10

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
Bibliometrics:
Citation Count: 14

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
Bibliometrics:
Citation Count: 12

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
Bibliometrics:
Citation Count: 35

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.
Bibliometrics:
Citation Count: 0


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.
Bibliometrics:
Citation Count: 0




The ACM Digital Library is published by the Association for Computing Machinery. Copyright © 2017 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us