The work of Leslie Valiant

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The work of Leslie Valiant

Full text

Pdf (333 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the 41st annual ACM symposium on Theory of computing table of contents

Bethesda, MD, USA

Pages 1-2

Year of Publication: 2009

ISBN:978-1-60558-506-2

Author

Avi Wigderson

Institute for Advanced Study, Princeton, NJ, USA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
ACM: Association for Computing Machinery

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 35, Downloads (12 Months): 169, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1536414.1536415 What is a DOI?

ABSTRACT

On Saturday, May 30, one day before the start of the regular STOC 2009 program, a workshop was held in celebration of Leslie Valiant's 60th birthday. Talks were given by Jin-Yi Cai, Stephen Cook, Vitaly Feldman, Mark Jerrum, Michael Kearns, Mike Paterson, Michael Rabin, Rocco Servedio, Paul Valiant, Vijay Vazirani, and Avi Wigderson. The workshop was organized by Michael Kearns, Rocco Servedio, and Salil Vadhan, with support from the STOC local arrangements team and program committee. To accompany the workshop, here we briefly survey Valiant's many fundamental contributions to the theory of computing.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
	2	D. A. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Trans. Inform. Theory, 42(6, part 1):1723--1731, 1996.
	3	Seinosuke Toda, PP is as hard as the polynomial-time hierarchy, SIAM Journal on Computing, v.20 n.5, p.865-877, Oct. 1991 [doi>10.1137/0220053]
	4	L. G. Valiant. Graph-theoretic properties in computational complexity. J. Comput. System Sci., 13(3):278--285, 1976.
	5	Working papers presented at the ACM-SIGACT Symposium on the Theory of Computing (Albuquerque, N. M., 1975).
	6	L. G. Valiant. Graph-theoretic arguments in low-level complexity. In Mathematical foundations of computer science (Proc. Sixth Sympos., Tatranska Lomnica, 1977), pages 162--176. Lecture Notes in Comput. Sci., Vol. 53. Springer, Berlin, 1977.
	7	L. G. Valiant, Completeness classes in algebra, Proceedings of the eleventh annual ACM symposium on Theory of computing, p.249-261, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804419]
	8	L. G. Valiant. The complexity of computing the permanent. Theoret. Comput. Sci., 8(2):189--201, 1979.
	9	L. G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410--421, 1979.
	10	L. G. Valiant. Negation can be exponentially powerful. Theoret. Comput. Sci., 12(3):303--314, 1980.
	11	L. G. Valiant. Parallel computation. In Proceedings of the 7th IBM Symposium on Mathematical Foundations of Computer Science. IBM, New York, 1982.
	12	L. G. Valiant. A scheme for fast parallel communication. SIAM J. Comput., 11(2):350--361, 1982.
	13	L. G. Valiant. Short monotone formulae for the majority function. J. Algorithms, 5(3):363--366, 1984.
	14	L. G. Valiant, A theory of the learnable, Communications of the ACM, v.27 n.11, p.1134-1142, Nov. 1984 [doi>10.1145/1968.1972]
	15	Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
	16	Leslie G. Valiant, Circuits of the mind, Oxford University Press, Inc., New York, NY, 1994
	17	Leslie G. Valiant, Quantum Circuits That Can Be Simulated Classically in Polynomial Time, SIAM Journal on Computing, v.31 n.4, p.1229-1254, 2002 [doi>10.1137/S0097539700377025]
	18	Leslie G. Valiant, Memorization and Association on a Realistic Neural Model, Neural Computation, v.17 n.3, p.527-555, March 2005 [doi>10.1162/0899766053019890]
	19	Leslie G. Valiant, A Quantitative Theory of Neural Computation, Biological Cybernetics, v.95 n.3, p.205-211, August 2006 [doi>10.1007/s00422-006-0079-3]
	20	Leslie G. Valiant, Holographic Algorithms, SIAM Journal on Computing, v.37 n.5, p.1565-1594, January 2008 [doi>10.1137/070682575]
	21	Leslie G. Valiant, Evolvability, Journal of the ACM (JACM), v.56 n.1, p.1-21, January 2009 [doi>10.1145/1462153.1462156]
	22	L. G. Valiant, S. Skyum, S. Berkowitz, and C. Rackoff. Fast parallel computation of polynomials using few processors. SIAM J. Comput., 12(4):641--644, 1983.
	23	L. G. Valiant , V. V. Vazirani, NP is as easy as detecting unique solutions, Theoretical Computer Science, v.47 n.1, p.85-93, Nov. 1986