Cyriac Antony
  • Member for 4 years, 1 month
  • Last seen this week
  • India
3 answers
26 votes
830 views
10 bookmarks
The complexity of determining if a fixed graph is a minor of another
3 answers
19 votes
929 views
4 bookmarks
NP-Complete problems that admit an efficient algorithm under the promise of a unique solution
72 answers
480 votes
175k views
974 bookmarks
What papers should everyone read?
2 answers
9 votes
413 views
1 bookmarks
NP-hardness of a planar SAT variant
3 answers
24 votes
1k views
3 bookmarks
NP complete graph problems about structural properties
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
12 votes
301 views
3 bookmarks
Why is the reduction from 3-SAT to 3-dimensional Matching Parsimonious?
39 answers
265 votes
132k views
633 bookmarks
What Books Should Everyone Read?
42 answers
82 votes
17k views
75 bookmarks
Funny TCS-related papers etc?
9 answers
82 votes
10k views
52 bookmarks
Are research papers hard to read?
0 answers
13 votes
382 views
2 bookmarks
What percentage of SODA papers are galactic algorithms?
5 answers
65 votes
2k views
28 bookmarks
Problems that can be used to show polynomial-time hardness results
1 answers
10 votes
743 views
2 bookmarks
Relationship between two graph optimization problems
12 answers
63 votes
3k views
24 bookmarks
Parameterized complexity from P to NP-hard and back again
20 answers
50 votes
8k views
21 bookmarks
NP-hard problems on trees
1 answers
2 votes
169 views
2 bookmarks
Is balanced Hamiltonian cycle NP complete on maximal plane graphs?
4 answers
8 votes
408 views
3 bookmarks
In-approximability results in severely restricted graph classes
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?
5 answers
65 votes
6k views
32 bookmarks
The origin of the notion of treewidth
17 answers
35 votes
2k views
19 bookmarks
Hardness jumps in computational complexity?
1 answers
1 votes
115 views
1 bookmarks
Color shifting in a bipartite graph
1 answers
7 votes
182 views
2 bookmarks
Complexity of finding semi-ordered Eulerian tours in a 4-regular graph
13 answers
122 votes
12k views
133 bookmarks
Advice on good research practices
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
5 answers
21 votes
782 views
3 bookmarks
Easy problems with hard counting versions
1 answers
3 votes
799 views
2 bookmarks
Complexity of 3SAT where each pair of 3-clauses share at most one variable
13 answers
31 votes
4k views
19 bookmarks
Are there any counterintuitive results in theoretical computer science?
2 answers
11 votes
2k views
6 bookmarks
On the provability of P versus NP
4 answers
14 votes
971 views
4 bookmarks
Are there any known NP problems which are conjectured to be exponentially hard on average?