article

Average case complete problems

Author:

Leonid A LevinAuthors Info & Claims

SIAM Journal on Computing, Volume 15, Issue 1

Pages 285 - 286

https://doi.org/10.1137/0215020

Published: 01 February 1986 Publication History

Abstract

No abstract available.

Cited By

View all

Hirahara SIlango RWilliams RMohar BShinkar IO'Donnell R(2024)Beating Brute Force for Compression ProblemsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649778(659-670)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649778
Hirahara SShimizu NMohar BShinkar IO'Donnell R(2024)Planted Clique Conjectures Are EquivalentProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649751(358-366)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649751
Hirahara SSaha BServedio R(2023)Capturing One-Way Functions via NP-Hardness of Meta-ComplexityProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585130(1027-1038)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585130
Show More Cited By

Index Terms

Average case complete problems

Recommendations

On average complexity of global optimization problems

We discuss the average case complexity of global optimization problems. By the average complexity, we roughly mean the amount of work needed to solve the problem with the expected error not exceeding a preassigned error demand. The expectation is taken ...
A new average case analysis for completion time scheduling

We present a new average case analysis for the problem of scheduling n jobs on m machines so that the sum of job completion times is minimized. Our goal is to use the concept of competitive ratio---which is a typical worst case notion---also within an ...
Matrix Transformation is Complete for the Average Case

In the theory of worst case complexity, NP completeness is used to establish that, for all practical purposes, the given NP problem is not decidable in polynomial time. In the theory of average case complexity, average case completeness is supposed to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 February 1986

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

118
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Hirahara SIlango RWilliams RMohar BShinkar IO'Donnell R(2024)Beating Brute Force for Compression ProblemsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649778(659-670)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649778
Hirahara SShimizu NMohar BShinkar IO'Donnell R(2024)Planted Clique Conjectures Are EquivalentProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649751(358-366)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649751
Hirahara SSaha BServedio R(2023)Capturing One-Way Functions via NP-Hardness of Meta-ComplexityProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585130(1027-1038)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585130
Hirahara SNanashima M(2022)Finding errorless pessiland in error-prone heuristicaProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.25(1-28)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.25
Goldberg HKabanets VLu ZOliveira I(2022)Probabilistic Kolmogorov complexity with applications to average-case complexityProceedings of the 37th Computational Complexity Conference10.4230/LIPIcs.CCC.2022.16(1-60)Online publication date: 20-Jul-2022
https://dl.acm.org/doi/10.4230/LIPIcs.CCC.2022.16
Asadi VGolovnev AGur TShinkar ILeonardi SGupta A(2022)Worst-case to average-case reductions via additive combinatoricsProceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3519935.3520041(1566-1574)Online publication date: 9-Jun-2022
https://dl.acm.org/doi/10.1145/3519935.3520041
Ball MDachman-Soled DLoss J(2022)(Nondeterministic) Hardness vs. Non-malleabilityAdvances in Cryptology – CRYPTO 202210.1007/978-3-031-15802-5_6(148-177)Online publication date: 15-Aug-2022
https://dl.acm.org/doi/10.1007/978-3-031-15802-5_6
Brzuska CCouteau G(2022)On Building Fine-Grained One-Way Functions from Strong Average-Case HardnessAdvances in Cryptology – EUROCRYPT 202210.1007/978-3-031-07085-3_20(584-613)Online publication date: 30-May-2022
https://dl.acm.org/doi/10.1007/978-3-031-07085-3_20
Pass RVenkitasubramaniam M(2021)Guest ColumnACM SIGACT News10.1145/3457588.345759852:1(47-69)Online publication date: 16-Mar-2021
https://dl.acm.org/doi/10.1145/3457588.3457598
Hirahara SKhuller SVassilevska Williams V(2021)Average-case hardness of NP from exponential worst-case hardness assumptionsProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3451065(292-302)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3451065
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Index Terms

Recommendations

On average complexity of global optimization problems

A new average case analysis for completion time scheduling

Matrix Transformation is Complete for the Average Case

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations