Nothing Special   »   [go: up one dir, main page]

skip to main content
10.1145/195058.195447acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article
Free access

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

Published: 23 May 1994 Publication History
First page of PDF

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, and Michael Luby. On the theory of average case complexity. Journal of Computer and System Sciences, 44:193-219, 1992.
[5]
Manuel Blum and S. Kannan. Designing programs that check their work. In Proc. of the 21st Ann. A CM Symp. on Theory of Computing, pages 86- 97, 1989.
[6]
Ashok K. Chandra, Dexter Kozen, and Larry J. Stockmeyer. Alternation. Journal of the A CM, 28(1):114-133, January 1981.
[7]
Joan Feigenbaum, Daphne Koller, and Peter Shor. Private communication. 1993.
[8]
Shaft Goldwasser, Silvio Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18( 1):186-208, 1989.
[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, 5:197-227, 1990.
[15]
Uwe SchSning. Probabilistic complexity classes and lowness. In Proc. of the Second IEEE Structure in Complexity Theory Conference, pages 2-8, 1987.
[16]
R. Venkatesan and Leonid Levin. Random instances of a graph coloring problem are hard. In Proc. of the 20lh Ann. A CM Syrup. on Theory of Computing, pages 217-222, 1988.
[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

View all
  • (2024)Batch Proofs Are Statistically HidingProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649775(435-443)Online publication date: 10-Jun-2024
  • (2024)One-Way Functions and Zero KnowledgeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649701(1731-1738)Online publication date: 10-Jun-2024
  • (2024)A Probabilistic Approach to the Game of Guessing in a Random EnvironmentJournal of Applied and Industrial Mathematics10.1134/S199047892401007118:1(70-80)Online publication date: 26-Apr-2024
  • Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing
May 1994
822 pages
ISBN:0897916638
DOI:10.1145/195058
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 May 1994

Permissions

Request permissions for this article.

Check for updates

Qualifiers

  • Article

Conference

STOC94
Sponsor:
STOC94: Symposium on Theory of Computing
May 23 - 25, 1994
Quebec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25
57th Annual ACM Symposium on Theory of Computing (STOC 2025)
June 23 - 27, 2025
Prague , Czech Republic

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)95
  • Downloads (Last 6 weeks)11
Reflects downloads up to 17 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2024)Batch Proofs Are Statistically HidingProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649775(435-443)Online publication date: 10-Jun-2024
  • (2024)One-Way Functions and Zero KnowledgeProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649701(1731-1738)Online publication date: 10-Jun-2024
  • (2024)A Probabilistic Approach to the Game of Guessing in a Random EnvironmentJournal of Applied and Industrial Mathematics10.1134/S199047892401007118:1(70-80)Online publication date: 26-Apr-2024
  • (2024)Localizability of the approximation methodcomputational complexity10.1007/s00037-024-00257-033:2Online publication date: 5-Sep-2024
  • (2023)Personalised AI Based Yoga-Pose Recommendation System Using Game Theory2023 International Conference on Advanced Computing Technologies and Applications (ICACTA)10.1109/ICACTA58201.2023.10393658(1-6)Online publication date: 6-Oct-2023
  • (2022)Complexity Limitations on One-turn Quantum Refereed GamesTheory of Computing Systems10.1007/s00224-022-10105-967:2(383-412)Online publication date: 10-Dec-2022
  • (2021)Strong co-nondeterministic lower bounds for NP cannot be proved feasiblyProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451117(223-233)Online publication date: 15-Jun-2021
  • (2020)Sharp threshold results for computational complexityProceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3357713.3384283(1335-1348)Online publication date: 22-Jun-2020
  • (2019)Hardness magnification near state-of-the-art lower boundsProceedings of the 34th Computational Complexity Conference10.4230/LIPIcs.CCC.2019.27(1-29)Online publication date: 17-Jul-2019
  • (2019)Why are Proof Complexity Lower Bounds Hard?2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS.2019.00080(1305-1324)Online publication date: Nov-2019
  • Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media