Cyriac Antony
  • Member for 4 years, 1 month
  • Last seen this week
  • India
16 answers
30 votes
5k views
17 bookmarks
Hard-looking algorithmic problems made easy by theorems
3 answers
12 votes
421 views
2 bookmarks
NP-complete graph property that is hereditary, but not additive?
5 answers
21 votes
3k views
8 bookmarks
Reasons for which a graph may be not $k$ colorable?
3 answers
37 votes
2k views
12 bookmarks
Techniques for showing that problem is in hardness "limbo"
6 answers
34 votes
2k views
14 bookmarks
Why are so few natural candidates for NP-intermediate status?
3 answers
26 votes
832 views
10 bookmarks
The complexity of determining if a fixed graph is a minor of another
4 answers
13 votes
4k views
7 bookmarks
Consequences of $NP=coNP$ and $P\ne NP$?
4 answers
19 votes
1k views
8 bookmarks
Applications of Complexity Theory
7 answers
28 votes
2k views
10 bookmarks
Nontrivial membership in NP
3 answers
39 votes
9k views
10 bookmarks
Is optimally solving the n×n×n Rubik's Cube NP-hard?
1 answers
14 votes
278 views
6 bookmarks
Hard extendability problems
9 answers
82 votes
10k views
52 bookmarks
Are research papers hard to read?
13 answers
122 votes
12k views
133 bookmarks
Advice on good research practices
2 answers
9 votes
413 views
1 bookmarks
NP-hardness of a planar SAT variant
5 answers
21 votes
782 views
3 bookmarks
Easy problems with hard counting versions
1 answers
5 votes
110 views
3 bookmarks
NP-Complete Convergent Reductions?
0 answers
4 votes
279 views
2 bookmarks
Bijection between NP-complete problems
1 answers
18 votes
2k views
7 bookmarks
What are the #P-complete subfamilies of #2-SAT?
2 answers
21 votes
1k views
3 bookmarks
Coloring Planar Graphs
2 answers
34 votes
4k views
9 bookmarks
Reference for NP-hardness of 3-colouring?
1 answers
7 votes
182 views
2 bookmarks
Complexity of finding semi-ordered Eulerian tours in a 4-regular graph
3 answers
19 votes
930 views
4 bookmarks
NP-Complete problems that admit an efficient algorithm under the promise of a unique solution
2 answers
35 votes
5k views
20 bookmarks
Status of Impagliazzo's Worlds?
5 answers
19 votes
2k views
9 bookmarks
(False?) proof for computability of a function?
13 answers
31 votes
4k views
19 bookmarks
Are there any counterintuitive results in theoretical computer science?
7 answers
30 votes
2k views
11 bookmarks
Proving lower bounds by proving upper bounds
2 answers
20 votes
903 views
9 bookmarks
Relationship between symmetry and computational intractability?
4 answers
8 votes
542 views
3 bookmarks
Is there a P/NP-complete dichotomy theorem for natural interesting properties of cubic graphs?
2 answers
24 votes
568 views
7 bookmarks
Relation between hardness of recognition of a graph class and forbidden subgraph characterization
42 answers
82 votes
17k views
75 bookmarks
Funny TCS-related papers etc?