2022 Developer Survey is open! Take survey.
user avatar
user avatar
user avatar
András Salamon
  • Member for 11 years, 9 months
  • Last seen more than a month ago
7 votes
Accepted

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

1 vote

Reduction from independent set in hypergraphs to independent set in graphs

6 votes

How many tautologies are there?

2 votes
Accepted

Packing $n$ objects into $m$ bins whose size is variable

6 votes
Accepted

Fully linear time regular expression matching

4 votes

Problems Between P and NPC

10 votes

Can a hereditary graph class contain almost all, but not all, n-vertex graphs?

4 votes
Accepted

Evidence that UniqueSat is dense

7 votes

Lipton's most influential results

23 votes
Accepted

Complexity zoo for unary languages

6 votes

Research problems in communication complexity

51 votes

Constraint satisfaction problem (CSP) vs. satisfiability modulo theory (SMT); with a coda on constraint programming

2 votes

Low space computation and branching program

3 votes
Accepted

Best current space lower bound for SAT?

10 votes

The unreasonable power of non-uniformity

9 votes
Accepted

Planted Clique in G(n,p), varying p

6 votes

Learnability of constraint satisfaction problems CSPs?

7 votes

Deterministic communication complexity vs partition number

1 vote

Major unsolved problems in theoretical computer science?

4 votes

Using Kolmogorov complexity as input "size"

4 votes

Nontrivial membership in NP

13 votes

Nontrivial membership in NP

7 votes

Why are so few natural candidates for NP-intermediate status?

7 votes

Justifying asymptotic worst-case analysis to scientists

15 votes

Is Almost-2-SAT NP-hard?

1 vote

Questions about special types of partial assignments

14 votes

Overarching reasons why problems are in P or BPP

19 votes

Overarching reasons why problems are in P or BPP

19 votes

A simple decision problem whose decidability is not known

10 votes

Examples of hardness phase transitions