domotorp's user avatar
domotorp's user avatar
domotorp's user avatar
domotorp
  • Member for 13 years, 7 months
  • Last seen this week
28 votes
Accepted

Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?

26 votes
Accepted

Coloring Planar Graphs

17 votes
Accepted

PARITY $\notin$ $AC^0$ with bounded fanout: easy proof?

15 votes
Accepted

Why do computer scientists on the whole work under the assumption that P ≠ NP?

14 votes

Is there any known NP-Complete (or NP-Intermediate) problem in sublinear nondeterministic space?

14 votes

Comparing Two Algorithms for 3SUM problem over Integers

13 votes
Accepted

Straight line complexity of monomials

13 votes
Accepted

Complexity of the problem of words with fewest distinct letters accepted by a finite automaton

13 votes

Is the wording of Google's QC Supremacy valid?

12 votes
Accepted

Find Shortest Pairwise Distance of Points in o(n log n)?

12 votes
Accepted

Positive topological ordering, take 3

11 votes
Accepted

Circuit lower bounds and kolmogorov complexity

10 votes
Accepted

Protocol partition number and deterministic communication complexity

10 votes

Expected values of Kolmogorov complexity in a random sample

9 votes

Positive topological ordering

9 votes
Accepted

What are the inclusion relationships if any, between the classes Pspace, PLS, PPP, PPA and PPAD

9 votes

Perfect matchings in a chessboard?

9 votes

Are regular languages closed under addition?

9 votes

Is every recursive language recognized by a mortal Turing machine?

9 votes
Accepted

Complexity of topological sort with constrained positions

9 votes

What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?

9 votes
Accepted

Is DSPACE(n) = DSPACE(1.5n)?

8 votes

Approximating Bipartite Vertex Cover

8 votes
Accepted

Is there some mathematical closed form (or somewhat tight asymptotic one) for "Google Eggs Puzzle"?

7 votes

Complexity of a subset sum variant

7 votes
Accepted

Hyperplanes not intersecting points on a cube

7 votes

Las Vegas vs Monte Carlo randomized decision tree complexity

7 votes
Accepted

Is there a name for this concept in Communication Complexity?

6 votes
Accepted

Can generalized twenty questions be solved by a greedy algorithm?

6 votes

The complexity of finding a Borsuk-Ulam point

1
2 3 4 5