User András Salamon

147 votes

Major unsolved problems in theoretical computer science?

big-list open-problem

answered Aug 17, 2010 at 17:43

52 votes

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

answered Feb 9, 2015 at 16:04

41 votes

Major unsolved problems in theoretical computer science?

big-list open-problem

answered Aug 23, 2010 at 16:29

32 votes

Accepted

Where do I turn for help with research/publishing?

sat soft-question proofs

answered Oct 6, 2010 at 22:57

25 votes

Accepted

Circuit lower bounds over arbitrary sets of gates

lower-bounds circuit-complexity circuit-families

answered Oct 2, 2010 at 14:43

23 votes

Accepted

what is easy for minor-excluded graphs?

ds.algorithms graph-theory graph-minor

answered Oct 22, 2010 at 19:21

23 votes

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

cc.complexity-theory reference-request pcp

answered Aug 17, 2010 at 0:16

23 votes

Accepted

Complexity zoo for unary languages

cc.complexity-theory reference-request big-list

answered May 11, 2015 at 15:00

22 votes

Accepted

What does one mean by heuristic statistical physics arguments?

sat pr.probability physics statistical-physics

answered Sep 13, 2010 at 2:33

22 votes

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

ds.algorithms graph-theory graph-algorithms

answered Nov 5, 2010 at 16:22

21 votes

Hardness jumps in computational complexity?

cc.complexity-theory

answered Oct 26, 2010 at 17:38

20 votes

Why is 2SAT in P?

cc.complexity-theory np-hardness big-picture polynomial-time

answered Jun 6, 2011 at 23:10

19 votes

Hardness jumps in computational complexity?

cc.complexity-theory

answered Oct 24, 2010 at 22:18

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?

cc.complexity-theory sat lower-bounds upper-bounds phase-transition

answered Oct 22, 2010 at 17:59

19 votes

A simple decision problem whose decidability is not known

computability decidability

answered Sep 4, 2013 at 22:00

19 votes

Overarching reasons why problems are in P or BPP

big-list big-picture

answered Oct 3, 2013 at 16:38

18 votes

Problems Between P and NPC

cc.complexity-theory np-hardness big-list np-intermediate

answered Sep 27, 2010 at 21:19

18 votes

Dinner-table description of theoretical computer science?

big-list soft-question

answered Sep 20, 2010 at 0:36

17 votes

Limits to Parallel Computing

cc.complexity-theory complexity-classes big-picture

answered Oct 8, 2010 at 3:13

17 votes

Current tightest bounds for critical 3-SAT density

pr.probability random-k-sat

answered Jan 6, 2013 at 15:33

16 votes

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

cc.complexity-theory time-complexity descriptive-complexity db.databases

answered Apr 26, 2011 at 15:23

15 votes

Accepted

Ladner's Theorem vs. Schaefer's Theorem

cc.complexity-theory np-hardness complexity-classes sat csp

answered Feb 27, 2012 at 0:00

15 votes

Complexity of "is a graph a product"

cc.complexity-theory graph-algorithms

answered Apr 1, 2012 at 16:58

15 votes

Accepted

Barriers and Monotone Circuit Complexity

cc.complexity-theory circuit-complexity barriers natural-proofs

answered Sep 20, 2010 at 14:31

15 votes

Is Almost-2-SAT NP-hard?

np-hardness sat upper-bounds

answered Dec 20, 2013 at 13:05

14 votes

Overarching reasons why problems are in P or BPP

big-list big-picture

answered Oct 4, 2013 at 16:27

14 votes

Accepted

How do database aggregations form a monoid?

soft-question machine-learning linear-algebra db.databases

answered Feb 14, 2013 at 16:58

14 votes

Accepted

Trees: complexity of counting the number of vertex covers

cc.complexity-theory graph-theory counting-complexity

answered Mar 19, 2011 at 21:32

13 votes

Accepted

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

soft-question computability

answered Nov 10, 2010 at 0:30

13 votes

References for TCS proof techniques

reference-request proof-techniques

answered Aug 19, 2010 at 2:47

Stack Exchange Network

current community

your communities

more stack exchange communities

113 Answers

Major unsolved problems in theoretical computer science?

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

Major unsolved problems in theoretical computer science?

Where do I turn for help with research/publishing?

Circuit lower bounds over arbitrary sets of gates

what is easy for minor-excluded graphs?

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

Complexity zoo for unary languages

What does one mean by heuristic statistical physics arguments?

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

Hardness jumps in computational complexity?

Why is 2SAT in P?

Hardness jumps in computational complexity?

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

A simple decision problem whose decidability is not known

Overarching reasons why problems are in P or BPP

Problems Between P and NPC

Dinner-table description of theoretical computer science?

Limits to Parallel Computing

Current tightest bounds for critical 3-SAT density

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

Ladner's Theorem vs. Schaefer's Theorem

Complexity of "is a graph a product"

Barriers and Monotone Circuit Complexity

Is Almost-2-SAT NP-hard?

Overarching reasons why problems are in P or BPP

How do database aggregations form a monoid?

Trees: complexity of counting the number of vertex covers

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

References for TCS proof techniques