Skip to main content
Share Your Experience: Take the 2024 Developer Survey
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, 9 months
  • Last seen more than 2 years ago
11 votes
2 answers
5k views

2DFA that requires many states in equivalent DFA?

48 votes
4 answers
5k views

Generalized Ladner's Theorem

54 votes
21 answers
4k views

Dinner-table description of theoretical computer science?

55 votes
2 answers
4k views

Can one amplify P=NP beyond P=PH?

44 votes
8 answers
3k views

Rigour leading to insight

20 votes
3 answers
3k views

How do models of hypercomputation overcome the Halting Problem?

13 votes
1 answer
3k views

Improving Cook's generic reduction for Clique to SAT?

36 votes
3 answers
2k views

NC = P consequences?

27 votes
4 answers
2k views

What specific evidence is there for P = RP?

20 votes
5 answers
2k views

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

26 votes
1 answer
2k views

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

41 votes
6 answers
2k views

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

32 votes
5 answers
1k views

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

21 votes
1 answer
1k views

How to prove that USTCONN requires logarithmic space?

23 votes
2 answers
1k views

Best current space lower bound for SAT?

17 votes
1 answer
971 views

Quadratic relationship between nondeterministic and deterministic space?

18 votes
1 answer
962 views

Context-sensitive grammar for SAT?

17 votes
0 answers
959 views

Deeper look at Algorithmica?

16 votes
1 answer
911 views

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

31 votes
1 answer
827 views

Can graph isomorphism be decided with square root bounded nondeterminism?

17 votes
2 answers
743 views

Hardness of parameterized CLIQUE?

15 votes
1 answer
715 views

What are the historical roots of Milner's bigraphs?

41 votes
1 answer
655 views

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

10 votes
3 answers
579 views

Is embedding a solution feasible for SAT?

6 votes
1 answer
557 views

Nondeterministic communication complexity of set disjointness?

10 votes
2 answers
517 views

ETH: k-SAT vs. SAT?

5 votes
1 answer
515 views

Is graph connectivity definable in existential MSO with vertices and edges?

15 votes
6 answers
511 views

Global properties of hereditary classes?

20 votes
0 answers
502 views

Model-checking for three-variable logics and restricted structures

20 votes
1 answer
501 views

Are there efficient general Bonferroni-style bounds known?