New answers tagged

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, ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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-...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar

Top 50 recent answers are included