New answers tagged time-complexity
3
votes
Are there any problems whose best known algorithms have running time $n^{\log \log n}$?
The best-known algorithm for testing isomorphism of finite groups whose solvable radical is either (a) contained in the center or (b) elementary abelian, is $n^{O(\log \log n)}$. These are, ...
- 35.7k
5
votes
Are there any problems whose best known algorithms have running time $n^{\log \log n}$?
The best-known deterministic algorithm for testing polynomial identities given by depth-three diagonal circuits has running time $n^{O(\log \log n)}$ [1].
More explicitly, we are given an expression ...
- 628
0
votes
Selecting unique records from a large dataframe with many duplicate records
In the context of Theoretical Computer Science, there are various strategies to (quickly) select the unique elements of a list, mainly comparison based and value based.
Value based: If computing a ...
- 2,391
1
vote
What is the problem in "closest pair problem" if all points share the same x-coordinate
Without the assumption that no points share the same x-coordinate, we run into one of two problems:
One problem occurs if you partition the space by x-coordinate. Say all points have the same x-...
- 111
3
votes
Solving All-Pairs Shortest Paths using a distance matrix in sub-cubic time
The discussion in this paper, Section 3 beginning on page 7, might be useful to you. It focuses on reducing distance product witnesses to distance product, which is the same as distance vs path APSP ...
- 2,293
9
votes
Lower-bounds under SETH
Most problems need at least linear time, so $O(n \log n)$ may be a little too close to optimal for a SETH based lower bound, generally we want running times where one can improve on the exponent by ...
- 26.3k
Top 50 recent answers are included