Skip to main content
Theoretical Computer Science
Antoine Amarilli 'a3nm''s user avatar
Antoine Amarilli 'a3nm''s user avatar
Antoine Amarilli 'a3nm''s user avatar
Antoine Amarilli 'a3nm'
  • Member for 13 years, 8 months
  • Last seen this week
Profile Activity

47 Answers

Score Activity Newest
22 votes
Accepted

Is the 3-coloring problem NP-hard on graphs of maximal degree 3?

17 votes
Accepted

Proof of the pumping lemma for context-free languages using pushdown automata

14 votes
Accepted

Complexity of 1-or-3-in-3-SAT (odd-3-SAT)

12 votes

Why most of the top TCS conferences are not double-blind?

12 votes
Accepted

Number of permutations that satisfy a given set of comparisons

10 votes
Accepted

Converting 2-ambiguous NFA to unambiguous NFA

9 votes
Accepted

Is it NP-hard to find an order on a set of strings so that the concatenation is a given string?

9 votes
Accepted

Characterization of lengths of words accepted by DFAs

9 votes
Accepted

What are bounded-treewidth circuits good for?

9 votes
Accepted

Minimum cost topological ordering

9 votes

Journals with quick reviewing

9 votes

A split-consistency property of a formal language

7 votes

Open access journals

7 votes

Generalization of Dilworth's theorem for labeled DAGs

7 votes
Accepted

Worst number of questions needed to learn a monotonic predicate over a poset

5 votes

Binary search generalizations for posets?

4 votes
Accepted

Complexity of counting the number of edge covers of a graph

4 votes

Arranging letters to make a word in a regular language

3 votes

Are research papers hard to read?

3 votes
Accepted

A variant of #POSITIVE-2-DNF

3 votes
Accepted

"Almost sorting" integers in linear time

3 votes

Monotone circuit representations of paths in a graph?

3 votes
Accepted

Constrained Topological Sorting with bounded number of chains

3 votes
Accepted

Proving #P-hardness for the number of subsets of a set of positive integers with a sum of at most T?

2 votes

Can you compute in PTIME a weighted version of deficiency on a bipartite graph?

2 votes

Testing whether letters can be scheduled to achieve a word in a regular language

2 votes

Determining what can be achieved by a permutation of elements of a noncommutative group

2 votes
Accepted

Generalizing linear interpolation to posets

2 votes
Accepted

Hardness of XSAT

2 votes
Accepted

Find items that are in at least $k$ of $n$ sets

1
2