user avatar
user avatar
user avatar
SamiD
  • Member for 11 years, 10 months
  • Last seen this week
24 votes

Problems with big open complexity gaps

13 votes

How to prove that USTCONN requires logarithmic space?

13 votes
Accepted

Can addition be carried out in less than depth 5?

12 votes

Complexity of matrix powering

10 votes

Efficient logspace algorithms

7 votes

complexity of greatest common divisor (gcd)

6 votes

Intermediate problems between L and NL

5 votes
Accepted

Reference for Dyck languages being $\mathsf{TC}_0$-complete

4 votes

Counting words accepted by a regular grammar

4 votes

Complexity of counting paths in a graph

4 votes

How quickly can we perform base extension in a residue number system?

3 votes

Any algorithmic problem has a time complexity dominated by counting?

3 votes

Boolean formula balancing in $\mathsf{AC^0}$

3 votes

XOR-SAT to Horn-SAT reduction

2 votes

What are interesting algorithmic questions for groups in table representation?

2 votes

Easy decision problem, hard search problem

1 vote

Is there any time efficient way of achieving the result of FKS hashing lemma?