Simple strategies for large zero-sum games with applications to complexity theory

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Simple strategies for large zero-sum games with applications to complexity theory

Full text

Pdf (720 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 734 - 740

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Richard J. Lipton	Computer Science Dept, Princeton Univ., Princeton, NJ
Neal E. Young	Dept. of Operations Research and Ind. Eng., Cornell University, Ithaca, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 39, Citation Count: 6

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions 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/195058.195447 What is a DOI?

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	Leonard M. Adleman. Two theorems on random polynomial time. In Proc. of the 19th IEEE Annual Syrup. on Foundation of Computer Science, pages 75-83, 1978.
	2	Noga Alon, Richard M. Karp, David Peleg, and Douglas West. A graph-theoretic game and its application to the k-server problem. In Lyle McGeoch and Daniel Sleator, editors, On-Line Algorithms: Proceedings of a DIMA CS Workshop, volume 7 of DIMA CS Series in Discrete Mathematics and Theoretical Computer Science, pages 1-9, 1992.
	3	ingo AlthSfer. On sparse approximations to randomized strategies and covex combinations. Linear Algebra and its Applications, 199, March 1994.
	4	Shai Ben-David , Benny Chor , Oded Goldreich , Michael Luby, On the theory of average case complexity, Journal of Computer and System Sciences, v.44 n.2, p.193-219, April 1992 [doi>10.1016/0022-0000(92)90019-F]
	5	M. Blum , S. Kanna, Designing programs that check their work, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.86-97, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73015]
	6	Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
	7	Joan Feigenbaum, Daphne Koller, and Peter Shor. Private communication. 1993.
	8	S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
	9	Y. Gurevich. Complete and incomplete randomized NP problems. In Proc. of the 28th IEEE Annual Symp. on Foundation of Computer Science, pages 111-117, 1987.
	10	Y. Gurevich. Matrix decomposition problem is complete for the average case. In Proc. of the 31st IEEE Annual Syrup. on Foundation of Computer Science, pages 802-811, 1990.
	11	Wassily Hoeffding. Probability inequalities for sums of bounded random variables. American Statistical Journal, pages 13-30, March 1963.
	12	Russell Impagliazzo and Leonid Levin. No better ways to generate hard NP instances than picking uniformly at random. In Proc. of the 31st IEEE Annual Syrup. oft Foundation of Computer Science, pages 812-821, 1990.
	13	Ming Li and P. M. B. Vitanyi. A theory of learning simple concepts under simple distributions and average case complexity for the universal distribution. In Proc. of the 30th IEEE Annual Symp. on Foundation of Computer Science, pages 34-39, 1989.
	14	Robert E. Schapire, The Strength of Weak Learnability, Machine Learning, v.5 n.2, p.197-227, Jun. 1990 [doi>10.1023/A:1022648800760]
	15	Uwe SchSning. Probabilistic complexity classes and lowness. In Proc. of the Second IEEE Structure in Complexity Theory Conference, pages 2-8, 1987.
	16	Ramarathnam Venkatesan , Leonid Levin, Random instances of a graph coloring problem are hard, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.217-222, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62231]
	17	John von Neumann. Zur Theorie der Gesellschaftspiel. Mathematische Annalen, 100(295-320), 1928.
	18	Andrew C.C. Yao. Probabilistic complexity: Towards a unified measure of complexity. In Proc. of the 18th IEEE Annual Symp. on Foundation of Computer Science, pages 222-227, 1977.
	19	Andrew C.C. Yao. Lower bounds by probabilistic arguments. In Proc. of the 24th IEEE Annual Symp. on Foundation of Computer Science, pages 420-428, 1983.
	20	Neal E. Young. Greedy algorithms by derandomizing unknown distributions. Technical Report T.R. 1087, Cornell University Department of Operations Research and Industrial Engineering, Ithaca, NY 14853, 1994.

CITED BY 6

	Christopher D. Rosin , Richard K. Belew, A competitive approach to game learning, Proceedings of the ninth annual conference on Computational learning theory, p.292-302, June 28-July 01, 1996, Desenzano del Garda, Italy
	Richard J. Lipton , Evangelos Markakis , Aranyak Mehta, Playing large games using simple strategies, Proceedings of the 4th ACM conference on Electronic commerce, p.36-41, June 09-12, 2003, San Diego, CA, USA
	Uriel Feige , Joe Kilian, Making games short (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.506-516, May 04-06, 1997, El Paso, Texas, United States
	Neal E. Young, Randomized rounding without solving the linear program, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.170-178, January 22-24, 1995, San Francisco, California, United States
	Constantinos Daskalakis , Aranyak Mehta , Christos Papadimitriou, A note on approximate Nash equilibria, Theoretical Computer Science, v.410 n.17, p.1581-1588, April, 2009
	Lance Fortnow , Russell Impagliazzo , Valentine Kabanets , Christopher Umans, On the Complexity of Succinct Zero-Sum Games, Computational Complexity, v.17 n.3, p.353-376, October 2008