Theoretical Computer Science

Nice Question

 Nice Question
Question score of 10 or more. This badge can be awarded multiple times.

earned this badge 31 times.
Regular languages accepted by an automaton with at most one transition per letter
Awarded Nov 2 at 12:25
Reconstructing labeled poset from linear extensions
Awarded Jul 7 at 21:31
Which monotone DNFs are evasive?
Awarded Jul 18 '19 at 9:00
Finding subgraphs with high treewidth and constant degree
Awarded Apr 21 '19 at 11:45
Space complexity to compute the optimal string alignment for the Levenshtein edit distance
Awarded Feb 13 '19 at 17:15
Generalization of Dilworth's theorem for labeled DAGs
Awarded May 8 '18 at 19:45
Testing whether letters can be scheduled to achieve a word in a regular language
Awarded Mar 1 '18 at 21:26
Smallest Boolean circuit to generate a language
Awarded Aug 29 '17 at 18:36
Determining what can be achieved by a permutation of elements of a noncommutative group
Awarded Jul 17 '17 at 11:38
“Almost sorting” integers in linear time
Awarded Apr 25 '17 at 18:53
Complexity of checking if two words have an interleaving in a language
Awarded Apr 4 '17 at 8:27
Lexicographically minimal topological sort of a labeled DAG
Awarded Jan 17 '17 at 11:14
Enumerating topological sorts of a vertex-labeled DAG
Awarded Jan 3 '17 at 8:49
Which convex polytopes have volumes of polynomial bit-length?
Awarded Sep 15 '16 at 11:08
Complexity of the homomorphism problem parameterized by treewidth
Awarded Jun 2 '16 at 20:21
Is it #P-hard to compute the number of antichains of a distributive lattice?
Awarded Nov 19 '15 at 18:22
What are bounded-treewidth circuits good for?
Awarded Nov 12 '15 at 1:01
Monotone bijections between lists of intervals
Awarded Nov 10 '15 at 21:33
Is it still open to determine the complexity of computing the treewidth of planar graphs?
Awarded Sep 11 '15 at 22:16
Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences
Awarded May 22 '15 at 10:33
Which monotone Boolean functions are representable as thresholds on sums?
Awarded May 14 '15 at 16:06
Complexity of counting the number of edge covers of a graph
Awarded Nov 20 '14 at 4:03
Identifying useless edges for shortest path
Awarded Jun 24 '14 at 14:28
Languages recognized by polynomial-size DFAs
Awarded May 6 '14 at 12:54
Complexity of topological sort with constrained positions
Awarded Sep 19 '13 at 17:30
Worst number of questions needed to learn a monotonic predicate over a poset
Awarded Jan 29 '13 at 6:39
Minimal elements of a monotonic predicate over the powerset $2^{|n|}$
Awarded Dec 21 '12 at 12:00
Smallest set not included in a collection of sets
Awarded Dec 21 '12 at 4:45
Find items that are in at least $k$ of $n$ sets
Awarded Jul 19 '12 at 18:32
Imperfect subgraph isomorphism
Awarded Jun 4 '12 at 21:38
Proof of the pumping lemma for context-free languages using pushdown automata
Awarded Apr 25 '12 at 16:01

Others with this badge