Leslie G. Valiant - Publications

Affiliations: 
University of Edinburgh, Edinburgh, Scotland, United Kingdom 
 Computer Science Harvard University, Cambridge, MA, United States 

33 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2017 Valiant LG. Some observations on holographic algorithms Computational Complexity. 27: 351-374. DOI: 10.1007/S00037-017-0160-4  0.395
2014 Valiant LG. What must a global theory of cortex explain? Current Opinion in Neurobiology. 25: 15-9. PMID 24709595 DOI: 10.1016/J.Conb.2013.10.006  0.324
2013 Guo H, Lu P, Valiant LG. The Complexity of Symmetric Boolean Parity Holant Problems Siam Journal On Computing. 42: 324-356. DOI: 10.1137/100815530  0.364
2011 Valiant LG. A bridging model for multi-core computing Journal of Computer and System Sciences. 77: 154-166. DOI: 10.1016/J.Jcss.2010.06.012  0.342
2009 Feldman V, Valiant LG. Experience-induced neural circuits that achieve high capacity. Neural Computation. 21: 2715-54. PMID 19635015 DOI: 10.1162/Neco.2009.08-08-851  0.651
2005 Valiant LG. Memorization and association on a realistic neural model. Neural Computation. 17: 527-55. PMID 15802006 DOI: 10.1162/0899766053019890  0.331
2002 Valiant LG. Quantum Circuits That Can Be Simulated Classically in Polynomial Time Siam Journal On Computing. 31: 1229-1254. DOI: 10.1137/S0097539700377025  0.345
2002 Valiant LG. Expressiveness of matchgates Theoretical Computer Science. 289: 457-471. DOI: 10.1016/S0304-3975(01)00325-5  0.325
2000 Valiant LG. A neuroidal architecture for cognitive computation Journal of the Acm. 47: 854-882. DOI: 10.1145/355483.355486  0.358
1999 Valiant LG. Machine Learning. 37: 115-130. DOI: 10.1023/A:1007678005361  0.353
1994 Kearns M, Li M, Valiant L. Learning Boolean formulas Journal of the Acm (Jacm). 41: 1298-1328. DOI: 10.1145/195613.195656  0.564
1994 Kearns M, Valiant L. Cryptographic limitations on learning Boolean formulae and finite automata Journal of the Acm (Jacm). 41: 67-95. DOI: 10.1145/174644.174647  0.602
1994 Gerbessiotis A, Valiant L. Direct Bulk-Synchronous Parallel Algorithms Journal of Parallel and Distributed Computing. 22: 251-267. DOI: 10.1006/Jpdc.1994.1085  0.316
1989 Ehrenfeucht A, Haussler D, Kearns M, Valiant L. A general lower bound on the number of examples needed for learning Information and Computation. 82: 247-261. DOI: 10.1016/0890-5401(89)90002-3  0.526
1988 Pitt L, Valiant LG. Computational limitations on learning from examples Journal of the Acm (Jacm). 35: 965-984. DOI: 10.1145/48014.63140  0.388
1986 Valiant LG. Negation is Powerless for Boolean Slice Functions Siam Journal On Computing. 15: 531-535. DOI: 10.1137/0215037  0.317
1986 Jerrum MR, Valiant LG, Vazirani VV. Random generation of combinatorial structures from a uniform distribution Theoretical Computer Science. 43: 169-188. DOI: 10.1016/0304-3975(86)90174-X  0.607
1985 Skyum S, Valiant LG. A complexity theory based on Boolean algebra Journal of the Acm (Jacm). 32: 484-502. DOI: 10.1145/3149.3158  0.366
1983 Lev G, Valiant L. Size bounds for superconcentrators Theoretical Computer Science. 22: 233-251. DOI: 10.1016/0304-3975(83)90105-6  0.304
1981 Valiant LG. Universality considerations in VLSI circuits Ieee Transactions On Computers. 30: 135-140. DOI: 10.1109/Tc.1981.6312176  0.328
1981 Lev GF, Valiant LG, Pippenger N. A Fast Parallel Algorithm for Routing in Permutation Networks Ieee Transactions On Computers. 93-100. DOI: 10.1109/Tc.1981.6312171  0.329
1980 Valiant L. Computing multivariate polynomials in parallel Information Processing Letters. 11: 44-45. DOI: 10.1016/0020-0190(80)90033-2  0.309
1979 Valiant LG. The Complexity of Enumeration and Reliability Problems Siam Journal On Computing. 8: 410-421. DOI: 10.1137/0208032  0.369
1979 Valiant L. The complexity of computing the permanent Theoretical Computer Science. 8: 189-201. DOI: 10.1016/0304-3975(79)90044-6  0.397
1979 Angluin D, Valiant LG. Fast probabilistic algorithms for hamiltonian circuits and matchings Journal of Computer and System Sciences. 18: 155-193. DOI: 10.1016/0022-0000(79)90045-X  0.351
1976 Pippenger N, Valiant LG. Shifting Graphs and Their Applications Journal of the Acm (Jacm). 23: 423-432. DOI: 10.1145/321958.321962  0.326
1976 Valiant LG. Graph-theoretic properties in computational complexity Journal of Computer and System Sciences. 13: 278-285. DOI: 10.1016/S0022-0000(76)80041-4  0.355
1976 Paterson MS, Valiant LG. Circuit size is nonlinear in depth Theoretical Computer Science. 2: 397-400. DOI: 10.1016/0304-3975(76)90090-6  0.485
1975 Valiant LG. Regularity and Related Problems for Deterministic Pushdown Automata Journal of the Acm (Jacm). 22: 1-10. DOI: 10.1145/321864.321865  0.332
1975 Valiant LG. Parallelism in Comparison Problems Siam Journal On Computing. 4: 348-355. DOI: 10.1137/0204030  0.343
1975 Valiant LG. General context-free recognition in less than cubic time Journal of Computer and System Sciences. 10: 308-315. DOI: 10.1016/S0022-0000(75)80046-8  0.319
1975 Valiant LG, Paterson MS. Deterministic one-counter automata Journal of Computer and System Sciences. 10: 340-350. DOI: 10.1016/S0022-0000(75)80005-5  0.561
1974 Valiant LG. The equivalence problem for deterministic finite-turn pushdown automata Information and Control. 25: 123-133. DOI: 10.1016/S0019-9958(74)90839-0  0.323
Show low-probability matches.