User domotorp

28 votes

Accepted

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

answered Dec 24, 2017 at 20:43

26 votes

Accepted

Coloring Planar Graphs

answered Dec 30, 2010 at 18:52

17 votes

Accepted

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

answered Jul 19, 2011 at 18:00

15 votes

Accepted

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

answered Jan 2, 2017 at 19:20

14 votes

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

answered May 5, 2012 at 11:21

14 votes

Comparing Two Algorithms for 3SUM problem over Integers

answered Apr 5, 2014 at 2:55

13 votes

Accepted

Straight line complexity of monomials

answered Nov 19, 2014 at 20:17

13 votes

Accepted

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

answered Dec 19, 2017 at 12:00

13 votes

Is the wording of Google's QC Supremacy valid?

answered Oct 24, 2019 at 8:58

12 votes

Accepted

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

answered Jan 25, 2012 at 6:00

12 votes

Accepted

Positive topological ordering, take 3

answered Nov 22, 2010 at 8:37

11 votes

Accepted

Circuit lower bounds and kolmogorov complexity

answered Jul 21, 2012 at 7:52

10 votes

Accepted

Protocol partition number and deterministic communication complexity

answered Oct 31, 2011 at 21:10

10 votes

Expected values of Kolmogorov complexity in a random sample

answered Aug 28, 2011 at 9:53

10 votes

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

answered Jan 15, 2018 at 11:33

9 votes

Accepted

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

answered Nov 22, 2018 at 20:21

9 votes

Positive topological ordering

answered Oct 1, 2010 at 14:16

9 votes

Accepted

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

answered Mar 16, 2011 at 6:56

9 votes

Perfect matchings in a chessboard?

answered Jan 15, 2012 at 11:08

9 votes

Are regular languages closed under addition?

answered Nov 8, 2014 at 7:37

9 votes

Is every recursive language recognized by a mortal Turing machine?

answered Feb 15, 2014 at 19:28

9 votes

Accepted

Complexity of topological sort with constrained positions

answered Sep 19, 2013 at 13:31

8 votes

Approximating Bipartite Vertex Cover

answered Apr 15, 2013 at 19:13

8 votes

Accepted

Hyperplanes not intersecting points on a cube

answered Apr 19, 2013 at 17:17

8 votes

Accepted

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

answered Dec 10, 2012 at 10:56

7 votes

Complexity of a subset sum variant

answered Nov 15, 2011 at 22:29

7 votes

Las Vegas vs Monte Carlo randomized decision tree complexity

answered May 25, 2014 at 19:22

7 votes

What is this variant of set cover problem known as?

answered Dec 3, 2014 at 22:51

7 votes

Accepted

Is there a name for this concept in Communication Complexity?

answered Dec 18, 2016 at 12:22

6 votes

Accepted

Can generalized twenty questions be solved by a greedy algorithm?

answered Aug 14, 2017 at 15:59

Stack Exchange Network

133 Answers

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

Coloring Planar Graphs

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

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

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

Comparing Two Algorithms for 3SUM problem over Integers

Straight line complexity of monomials

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

Is the wording of Google's QC Supremacy valid?

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

Positive topological ordering, take 3

Circuit lower bounds and kolmogorov complexity

Protocol partition number and deterministic communication complexity

Expected values of Kolmogorov complexity in a random sample

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

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

Positive topological ordering

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

Perfect matchings in a chessboard?

Are regular languages closed under addition?

Is every recursive language recognized by a mortal Turing machine?

Complexity of topological sort with constrained positions

Approximating Bipartite Vertex Cover

Hyperplanes not intersecting points on a cube

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

Complexity of a subset sum variant

Las Vegas vs Monte Carlo randomized decision tree complexity

What is this variant of set cover problem known as?

Is there a name for this concept in Communication Complexity?

Can generalized twenty questions be solved by a greedy algorithm?