user avatar
user avatar
user avatar
András Salamon
  • Member for 11 years, 10 months
  • Last seen more than a month ago
55 votes
2 answers
4k views

Can one amplify P=NP beyond P=PH?

53 votes
21 answers
4k views

Dinner-table description of theoretical computer science?

46 votes
4 answers
4k views

Generalized Ladner's Theorem

42 votes
8 answers
3k views

Rigour leading to insight

41 votes
1 answer
633 views

Does Rabin/Yao exist (at least in a form that can be cited)?

39 votes
5 answers
1k views

Is there a logic without induction that captures much of P?

36 votes
3 answers
2k views

NC = P consequences?

31 votes
1 answer
791 views

Can graph isomorphism be decided with square root bounded nondeterminism?

28 votes
4 answers
1k views

Maximal classes for which largest independent set can be found in polynomial time?

27 votes
4 answers
2k views

What specific evidence is there for P = RP?

24 votes
1 answer
2k views

How does the BosonSampling paper avoid easy classes of complex matrices?

23 votes
2 answers
952 views

Best current space lower bound for SAT?

22 votes
1 answer
464 views

Are there natural separations in the nondeterministic time hierarchy?

20 votes
1 answer
486 views

Are there efficient general Bonferroni-style bounds known?

20 votes
5 answers
457 views

Reducing space usage of st-connectivity with multiple passes?

20 votes
5 answers
2k views

Version control for collaboration (with word-level diffs)?

20 votes
0 answers
499 views

Model-checking for three-variable logics and restricted structures

20 votes
1 answer
914 views

How to prove that USTCONN requires logarithmic space?

19 votes
1 answer
892 views

Context-sensitive grammar for SAT?

18 votes
3 answers
3k views

How do models of hypercomputation overcome the Halting Problem?

17 votes
2 answers
699 views

Hardness of parameterized CLIQUE?

17 votes
0 answers
864 views

Deeper look at Algorithmica?

17 votes
1 answer
954 views

Quadratic relationship between nondeterministic and deterministic space?

16 votes
1 answer
830 views

Reference for (odd-hole,antihole)-free graphs?

15 votes
6 answers
498 views

Global properties of hereditary classes?

15 votes
1 answer
244 views

2FA state complexity of k-Clique?

14 votes
1 answer
684 views

What are the historical roots of Milner's bigraphs?

14 votes
0 answers
264 views

AC0 many-one reduction of Mod_3 to PRIMES?

13 votes
1 answer
268 views

Elementary bounds on parameter in fixed-parameter tractability?

13 votes
3 answers
339 views

Can limit of hard languages be easy?