10 votes

What is worst case complexity of number field sieve?

In the past few months, a version of the number field sieve has been analyzed rigorously: http://www.fields.utoronto.ca/talks/rigorous-analysis-randomized-number-field-sieve-factoring Basically the ...
djao's user avatar
  • 201
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 ...
Sasho Nikolov's user avatar
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.
Kolja's user avatar
  • 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 (...
Lijie Chen's user avatar
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 ...
J..y B..y's user avatar
  • 2,776
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 ...
David Eppstein's user avatar
2 votes

The Average-case Complexity of Simplex Algorithm

The first thing that comes to mind is "Smoothed Analysis" of Spielman and Teng: arxiv.org/pdf/cs/0111050.pdf. Their main result is Theorem 5.0.1, which bounds the expected (over "typical instances") ...
Aryeh's user avatar
  • 10.5k

Only top scored, non community-wiki answers of a minimum length are eligible