Theoretical Computer Science

Nice Question

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

earned this badge 32 times.
Graphs with minimal-size induced subgraphs
Awarded Jan 19 at 12:36
Regular languages accepted by an automaton with at most one transition per letter
Awarded Nov 2 '20 at 12:25
Reconstructing labeled poset from linear extensions
Awarded Jul 7 '20 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