Theoretical Computer Science
András Salamon
  • Member for 11 years, 5 months
  • Last seen this week
Profile Activity

53 Questions

Votes Activity Newest Views
2 answers
55 votes
4k views
13 bookmarks
Can one amplify P=NP beyond P=PH?
21 answers
52 votes
4k views
23 bookmarks
Dinner-table description of theoretical computer science?
4 answers
46 votes
4k views
15 bookmarks
Generalized Ladner's Theorem
8 answers
42 votes
3k views
31 bookmarks
Rigour leading to insight
1 answers
41 votes
624 views
2 bookmarks
Does Rabin/Yao exist (at least in a form that can be cited)?
5 answers
39 votes
1k views
16 bookmarks
Is there a logic without induction that captures much of P?
3 answers
36 votes
2k views
11 bookmarks
NC = P consequences?
1 answers
31 votes
787 views
5 bookmarks
Can graph isomorphism be decided with square root bounded nondeterminism?
4 answers
28 votes
1k views
10 bookmarks
Maximal classes for which largest independent set can be found in polynomial time?
4 answers
27 votes
2k views
6 bookmarks
What specific evidence is there for P = RP?
2 answers
23 votes
889 views
2 bookmarks
Best current space lower bound for SAT?
1 answers
22 votes
2k views
3 bookmarks
How does the BosonSampling paper avoid easy classes of complex matrices?
1 answers
22 votes
460 views
8 bookmarks
Are there natural separations in the nondeterministic time hierarchy?
1 answers
20 votes
890 views
2 bookmarks
How to prove that USTCONN requires logarithmic space?
1 answers
20 votes
485 views
7 bookmarks
Are there efficient general Bonferroni-style bounds known?
0 answers
20 votes
499 views
4 bookmarks
Model-checking for three-variable logics and restricted structures
5 answers
20 votes
2k views
11 bookmarks
Version control for collaboration (with word-level diffs)?
5 answers
20 votes
455 views
4 bookmarks
Reducing space usage of st-connectivity with multiple passes?
1 answers
19 votes
859 views
2 bookmarks
Context-sensitive grammar for SAT?
3 answers
18 votes
3k views
4 bookmarks
How do models of hypercomputation overcome the Halting Problem?
1 answers
17 votes
947 views
3 bookmarks
Quadratic relationship between nondeterministic and deterministic space?
0 answers
17 votes
825 views
5 bookmarks
Deeper look at Algorithmica?
2 answers
17 votes
696 views
7 bookmarks
Hardness of parameterized CLIQUE?
1 answers
16 votes
823 views
2 bookmarks
Reference for (odd-hole,antihole)-free graphs?
1 answers
15 votes
243 views
3 bookmarks
2FA state complexity of k-Clique?
6 answers
15 votes
492 views
4 bookmarks
Global properties of hereditary classes?
0 answers
14 votes
262 views
1 bookmarks
AC0 many-one reduction of Mod_3 to PRIMES?
1 answers
14 votes
679 views
4 bookmarks
What are the historical roots of Milner's bigraphs?
0 answers
13 votes
354 views
2 bookmarks
Consequences of bipartite perfect matching not in NL?
1 answers
13 votes
2k views
1 bookmarks
Improving Cook's generic reduction for Clique to SAT?
1
2

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.