András Salamon's user avatar
András Salamon's user avatar
András Salamon's user avatar
András Salamon
  • Member for 12 years, 3 months
  • Last seen more than a month ago
19 votes
Accepted

What are the current best known upper and lower bounds on the (un)satisfiability threshold for random k-sat and/or 3-sat?

9 votes
Accepted

Graph classes for which the diameter can be computed in linear time

21 votes

Hardness jumps in computational complexity?

14 votes
Accepted

How do database aggregations form a monoid?

53 votes

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

8 votes
Accepted

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

8 votes
Accepted

CSPs with unbounded fractional hypertree width

1 vote

Reduction from independent set in hypergraphs to independent set in graphs

22 votes

What is the best exact algorithm to compute the core of a graph?

6 votes

How many tautologies are there?

8 votes

"All-different hypergraph coloring" - known problem?

9 votes

What hierarchies and/or hierarchy theorems do you know?

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

7 votes

Deterministic communication complexity vs partition number

6 votes

Research problems in communication complexity

147 votes

Major unsolved problems in theoretical computer science?

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?

1 vote

Major unsolved problems in theoretical computer science?

12 votes

Gröbner bases in TCS?

4 votes

Using Kolmogorov complexity as input "size"