6
votes
Average-case complexity open problems other than one-way functions
You can look at the survey paper by Bogdanov and Trevisan, and this survey talk by Luca. The main open question is whether $\mathsf{P} \neq \mathsf{NP}$ implies that there exist hard on average ...
- 18.3k
4
votes
Accepted
NP-hard problem which is easy on average
This 1989 article by Dyer and Frieze answers the question directly:
The Solution of Some Random NP-hard Problems in Polynomial Expected Time.
- 181
3
votes
Accepted
Fine-grained average-case derandomization
There are some recent works on this topic, for example [DMOZ20], [CT21a], and [CT21b].
For worst-case derandomization: following [DMOZ20], [CT21a] showed that under plausible hardness assumption (...
- 176
3
votes
NP-hard problem which is easy on average
That is a good question :)
As mentioned in the comments, there are various decision problems which are NP-Hard (worst case complexity) while easy on average (average case complexity), for some ...
- 2,816
2
votes
What are the worst-case and average-case time complexities of the greedy algorithm for the weighted set cover problem?
Let $n$ be the total number of elements in all sets in $F$, basically your input size. Maintain a priority queue of the remaining sets, prioritized by cost / number of uncovered elements. Every time ...
- 51.2k
Only top scored, non community-wiki answers of a minimum length are eligible