Theoretical Computer Science
Jeffε's user avatar
Jeffε's user avatar
Jeffε's user avatar
Jeffε
  • Member for 13 years, 3 months
  • Last seen more than 1 year ago
Profile Activity

21 Questions

Score Activity Newest Views
145 votes
2 answers
19k views

Super Mario Galaxy problem

129 votes
11 answers
12k views

How hard is unshuffling a string?

97 votes
2 answers
40k views

What is the actual time complexity of Gaussian elimination?

41 votes
2 answers
6k views

Sum-of-square-roots-hard problems?

40 votes
3 answers
10k views

Is optimally solving the n×n×n Rubik's Cube NP-hard?

35 votes
6 answers
10k views

Is there a stable heap?

31 votes
3 answers
2k views

Is it NP-hard to play international draughts correctly?

27 votes
1 answer
913 views

Other applications of Karger-Stein branching amplification?

27 votes
2 answers
2k views

Complexity of n-queens-completion?

26 votes
2 answers
4k views

Exact number of comparisons to compute the median

22 votes
1 answer
462 views

Exact planar electrical flow

22 votes
1 answer
1k views

Complexity of computing shortest paths in the plane with polygonal obstacles

22 votes
2 answers
2k views

Detecting two kinds of almost-simple polygons

20 votes
4 answers
2k views

Permutation game redux

20 votes
3 answers
784 views

Is it hard to find optimal addition chains?

18 votes
2 answers
7k views

Complexity of computing the discrete Fourier transform?

16 votes
2 answers
5k views

Time complexity of Bellman-Held-Karp algorithm for TSP, take 2

13 votes
0 answers
374 views

Applications of an access lemma for dynamic forests?

12 votes
1 answer
598 views

Positive topological ordering, take 2

10 votes
0 answers
239 views

Complexity of cycle cancellation with integral capacities and irrational costs

7 votes
2 answers
287 views

Paths in a weighted line arrangement

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.