user avatar
user avatar
user avatar
SamiD
  • Member for 11 years, 10 months
  • Last seen more than a week ago
18 votes
2 answers
1k views

Time complexity of counting triangles in planar graphs

17 votes
1 answer
1k views

The complexity of counting simple paths in a directed graph

13 votes
2 answers
493 views

Minimum Tree-width of circuit for MAJORITY

9 votes
1 answer
402 views

What is wrong with this $\mathsf{L} \subseteq \mathsf{L}-$uniform $\mathsf{NC}^1$ argument?

9 votes
2 answers
226 views

Exact complexity of a problem in $\cap_{m \geq 2}\mathsf{AC}^0[m]$

8 votes
1 answer
1k views

Complexity of Polynomial Division

7 votes
0 answers
127 views

Deterministic Parallel Algorithm for ILP with small number of variables and small coefficients

5 votes
1 answer
316 views

Sparser Bipartite graphs?

4 votes
1 answer
165 views

k-outerplanar graphs are subgraphs of bounded diameter planar graphs? of bounded diameter bounded genus graphs?

4 votes
1 answer
182 views

Dual Barnette's Conjecture

3 votes
0 answers
242 views

$NC^i \subseteq DSPACE[\log^i{n}]$?

3 votes
1 answer
130 views

Shortest cycle separator for biconnected planar graphs

1 vote
1 answer
80 views

Existence of graphs of every order related to Barnette’s conjecture

0 votes
0 answers
19 views

2-connectivity of dual of a minimal cut in a bounded genus graph

0 votes
1 answer
73 views

Counting sum of parities of cycle covers in cubic, planar, bipartite graphs