user avatar
user avatar
user avatar
András Salamon
  • Member for 11 years, 10 months
  • Last seen more than a month ago
147 votes

Major unsolved problems in theoretical computer science?

52 votes

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

41 votes

Major unsolved problems in theoretical computer science?

32 votes
Accepted

Where do I turn for help with research/publishing?

25 votes
Accepted

Circuit lower bounds over arbitrary sets of gates

23 votes
Accepted

what is easy for minor-excluded graphs?

23 votes

What are good references to understanding the proof of the PCP theorem?

23 votes
Accepted

Complexity zoo for unary languages

22 votes
Accepted

What does one mean by heuristic statistical physics arguments?

22 votes

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

21 votes

Hardness jumps in computational complexity?

20 votes

Why is 2SAT in P?

19 votes

Hardness jumps in computational complexity?

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?

19 votes

A simple decision problem whose decidability is not known

19 votes

Overarching reasons why problems are in P or BPP

18 votes

Problems Between P and NPC

18 votes

Dinner-table description of theoretical computer science?

17 votes

Limits to Parallel Computing

17 votes

Current tightest bounds for critical 3-SAT density

16 votes

Why do relational databases work at all, given the theoretical exponential complexity of answer finding (in the size of the query)?

15 votes
Accepted

Ladner's Theorem vs. Schaefer's Theorem

15 votes

Complexity of "is a graph a product"

15 votes
Accepted

Barriers and Monotone Circuit Complexity

15 votes

Is Almost-2-SAT NP-hard?

14 votes

Overarching reasons why problems are in P or BPP

14 votes
Accepted

How do database aggregations form a monoid?

14 votes
Accepted

Trees: complexity of counting the number of vertex covers

13 votes
Accepted

Is one definition of the word paradox, "something that can be used to prove the halting problem undecidable?"

13 votes

References for TCS proof techniques