domotorp's user avatar
domotorp's user avatar
domotorp's user avatar
domotorp
  • Member for 12 years, 9 months
  • Last seen this week
34 votes
2 answers
1k views

Does LOGLOG = NLOGLOG?

31 votes
5 answers
3k views

Is there a natural problem on the naturals that is NP-complete?

31 votes
4 answers
2k views

What is simplest polynomial algorithm for PLANARITY?

27 votes
2 answers
1k views

Can we not output the Kolmogorov complexity?

23 votes
2 answers
836 views

Are shift-chains two-colorable?

23 votes
1 answer
907 views

FOCS virtual fee $600

21 votes
4 answers
1k views

What is the minimum size of a circuit that computes PARITY?

20 votes
4 answers
1k views

Positive topological ordering, take 3

20 votes
2 answers
1k views

Can any computational challenge be transformed to proof-of-work?

20 votes
1 answer
2k views

Number of words of length n in a context-free language

19 votes
2 answers
1k views

Can we decide whether a permanent has a unique term?

18 votes
3 answers
795 views

In what class are randomized algorithms that err with exactly 25% chance?

18 votes
2 answers
526 views

Is it possible to encrypt a CNF?

17 votes
2 answers
410 views

What are TCS conjectures that were proved for primes and small values but then turned out to be false?

16 votes
1 answer
263 views

Is it enough to sort for polynomially many 0-1 sequences for a sorting network?

15 votes
1 answer
259 views

Does ${\bf AC^0PAD} = {\bf PPAD}$?

15 votes
0 answers
375 views

Are there other proofs for Barrington's theorem?

14 votes
3 answers
396 views

Separation of a preprocessed polyhedron and a plane

14 votes
0 answers
243 views

Is it possible to make trapdoor board games?

14 votes
0 answers
495 views

Is it possible to find the median with a linear size sorting network?

13 votes
4 answers
631 views

Can we fast generate perfectly uniformly mod 3 or solve NP problem?

12 votes
3 answers
483 views

Is the complement of { www | … } context-free?

12 votes
1 answer
615 views

Is $\mathsf{DTIME}(n) = \mathsf{DTIME}(2n)$?

11 votes
1 answer
568 views

For what c is division by c in AC0?

11 votes
3 answers
353 views

Is there a simple game with asymmetric complexity?

11 votes
0 answers
146 views

Is RAMSEY COLORING in $NC$?

11 votes
0 answers
178 views

$\exists \mathbb R$ and IP

11 votes
0 answers
217 views

Can two-tape read-only Turing machines recognize any recursive language?

10 votes
6 answers
808 views

Can neural networks be used to devise algorithms?

10 votes
0 answers
182 views

Provable BPP Hierarchy