András Salamon's user avatar
András Salamon's user avatar
András Salamon's user avatar
András Salamon
  • Member for 13 years, 8 months
  • Last seen more than 2 years ago
55 votes
2 answers
4k views

Can one amplify P=NP beyond P=PH?

54 votes
21 answers
4k views

Dinner-table description of theoretical computer science?

48 votes
4 answers
5k views

Generalized Ladner's Theorem

44 votes
8 answers
3k views

Rigour leading to insight

41 votes
1 answer
653 views

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

40 votes
5 answers
2k views

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

36 votes
3 answers
2k views

NC = P consequences?

32 votes
5 answers
1k views

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

31 votes
1 answer
826 views

Can graph isomorphism be decided with square root bounded nondeterminism?

27 votes
4 answers
2k views

What specific evidence is there for P = RP?

26 votes
1 answer
2k views

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

23 votes
2 answers
1k views

Best current space lower bound for SAT?

22 votes
1 answer
496 views

Are there natural separations in the nondeterministic time hierarchy?

20 votes
1 answer
499 views

Are there efficient general Bonferroni-style bounds known?

20 votes
5 answers
470 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
502 views

Model-checking for three-variable logics and restricted structures

20 votes
3 answers
3k views

How do models of hypercomputation overcome the Halting Problem?

20 votes
1 answer
1k views

How to prove that USTCONN requires logarithmic space?

18 votes
1 answer
958 views

Context-sensitive grammar for SAT?

17 votes
2 answers
743 views

Hardness of parameterized CLIQUE?

17 votes
0 answers
953 views

Deeper look at Algorithmica?

17 votes
1 answer
970 views

Quadratic relationship between nondeterministic and deterministic space?

16 votes
1 answer
903 views

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

15 votes
6 answers
511 views

Global properties of hereditary classes?

15 votes
1 answer
247 views

2FA state complexity of k-Clique?

14 votes
1 answer
712 views

What are the historical roots of Milner's bigraphs?

14 votes
0 answers
273 views

AC0 many-one reduction of Mod_3 to PRIMES?

13 votes
1 answer
273 views

Elementary bounds on parameter in fixed-parameter tractability?

13 votes
3 answers
345 views

Can limit of hard languages be easy?