Cyriac Antony
  • Member for 4 years, 1 month
  • Last seen this week
  • India
5 answers
21 votes
3k views
8 bookmarks
Reasons for which a graph may be not $k$ colorable?
5 answers
21 votes
782 views
3 bookmarks
Easy problems with hard counting versions
2 answers
20 votes
903 views
9 bookmarks
Relationship between symmetry and computational intractability?
1 answers
19 votes
1k views
2 bookmarks
Construction of graphs where every pair of vertices have an unique common neighbor
5 answers
19 votes
2k views
9 bookmarks
(False?) proof for computability of a function?
3 answers
19 votes
929 views
4 bookmarks
NP-Complete problems that admit an efficient algorithm under the promise of a unique solution
4 answers
19 votes
1k views
8 bookmarks
Applications of Complexity Theory
3 answers
19 votes
606 views
8 bookmarks
What separates easy global problems from hard global problems on graphs of bounded treewidth?
1 answers
18 votes
2k views
7 bookmarks
What are the #P-complete subfamilies of #2-SAT?
3 answers
16 votes
399 views
6 bookmarks
Any references for techniques in FPT reductions?
4 answers
14 votes
971 views
4 bookmarks
Are there any known NP problems which are conjectured to be exponentially hard on average?
1 answers
14 votes
549 views
1 bookmarks
Does PSPACE-completeness imply approximation hardness?
1 answers
14 votes
278 views
6 bookmarks
Hard extendability problems
4 answers
13 votes
4k views
7 bookmarks
Consequences of $NP=coNP$ and $P\ne NP$?
0 answers
13 votes
382 views
2 bookmarks
What percentage of SODA papers are galactic algorithms?
4 answers
13 votes
2k views
2 bookmarks
hardness of approximating the chromatic number in graphs with bounded degree
1 answers
12 votes
301 views
3 bookmarks
Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?
3 answers
12 votes
421 views
2 bookmarks
NP-complete graph property that is hereditary, but not additive?
2 answers
11 votes
484 views
6 bookmarks
Is there an explanation for the difficulty of proving quadratic lower bounds for interesting NP problems?
1 answers
11 votes
257 views
1 bookmarks
An improper planar coloring with monochromatic component size $\leq 2$
2 answers
11 votes
2k views
6 bookmarks
On the provability of P versus NP
2 answers
10 votes
1k views
2 bookmarks
A variant of Critical SAT in DP
1 answers
10 votes
743 views
2 bookmarks
Relationship between two graph optimization problems
1 answers
9 votes
887 views
4 bookmarks
Does 1-in-3 SAT remain NP-hard even if every variable occurs both positively and negatively?
2 answers
9 votes
413 views
1 bookmarks
NP-hardness of a planar SAT variant
4 answers
8 votes
542 views
3 bookmarks
Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?
4 answers
8 votes
408 views
3 bookmarks
In-approximability results in severely restricted graph classes
1 answers
7 votes
145 views
4 bookmarks
Reducing Parameterized Problems (whose solution size can be "large") to W[i]-complete problems (for fixed i)
1 answers
7 votes
182 views
2 bookmarks
Complexity of finding semi-ordered Eulerian tours in a 4-regular graph
1 answers
6 votes
314 views
3 bookmarks
Complexity of finding large grid minors