User Timothy Chow

5 votes

Law of the Excluded Middle in complexity theory

answered Mar 1 at 17:02

6 votes

Accepted

What are the consequences of $BPP \neq P$?

answered Sep 22, 2023 at 15:56

5 votes

Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?

answered Jul 26, 2020 at 13:59

15 votes

Accepted

The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers

answered Apr 5, 2013 at 17:38

6 votes

Examples of pedantry in TCS

answered Jul 13, 2012 at 22:29

27 votes

Does P contain languages whose existence is independent of PA or ZFC? (TCS community wiki)

answered Jun 12, 2012 at 15:15

15 votes

Accepted

What is the motivation behind the definition of fixed parameter tractability?

answered Apr 20, 2012 at 16:23

6 votes

Graph problems with good characterization but not known to be in $P$

answered Apr 19, 2012 at 19:01

11 votes

Accepted

The origin of the terms "efficient" and "feasible" computation/algorithm

answered Mar 15, 2012 at 14:39

7 votes

Application of calculus in computer science

answered Mar 13, 2012 at 15:58

6 votes

Are there decidable problems for which for no algorithm we can give time bounds?

answered Feb 16, 2012 at 16:02

23 votes

Implications of unprovability of $P\neq NP$

answered Feb 6, 2012 at 18:57

13 votes

Accepted

What's the "real" reason that IP=PSPACE is non-relativizing?

answered Jan 27, 2012 at 19:53

16 votes

Accepted

Ranking the Difficulty of NP Hard Problems in Practice

answered Nov 29, 2011 at 18:30

12 votes

SAT algorithms not based on DPLL

answered Nov 26, 2011 at 1:01

7 votes

How should one simulate self-avoiding random walks?

answered Nov 16, 2011 at 19:13

18 votes

Casual tours around proofs

answered Nov 9, 2011 at 15:53

10 votes

Accepted

Constructing uniquely satisfiable formulas

answered Oct 26, 2011 at 22:03

9 votes

Hilbert's Tenth Problem and nonrecursive Diophantine sets

answered Sep 30, 2011 at 1:59

8 votes

Complexity of computing the discrete Fourier transform?

answered Sep 13, 2011 at 15:19

27 votes

Accepted

Maximal/maximum independent sets

answered Aug 7, 2011 at 22:49

28 votes

Accepted

Cohomological approach to boolean complexity

answered Apr 6, 2011 at 14:44

9 votes

Proofs obtained only through spectral graph theory

answered Feb 24, 2011 at 23:39

75 votes

What would it mean to disprove Church-Turing thesis?

answered Feb 9, 2011 at 19:45

9 votes

Compendium of the Best Approximation and Hardness Results for NP optimization problems

answered Feb 9, 2011 at 19:04

34 votes

Accepted

Should experts in TCS charge money to read proofs that P != NP?

answered Jan 27, 2011 at 21:38

6 votes

Proofs that expose a deeper structure

answered Jan 5, 2011 at 16:56

14 votes

Accepted

Are recursive forms of Godel's statement possible?

answered Dec 30, 2010 at 22:04

51 votes

Accepted

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

answered Dec 30, 2010 at 20:10

14 votes

How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?

answered Dec 29, 2010 at 21:49

Stack Exchange Network

30 Answers

Law of the Excluded Middle in complexity theory

What are the consequences of $BPP \neq P$?

Why do people bring real-life Quantum Computing to the discussion of the Church-Turing thesis?

The complexity of computing the permanent of a matrix of zeroes and ones versus a matrix of integers

Examples of pedantry in TCS

Does P contain languages whose existence is independent of PA or ZFC? (TCS community wiki)

What is the motivation behind the definition of fixed parameter tractability?

Graph problems with good characterization but not known to be in $P$

The origin of the terms "efficient" and "feasible" computation/algorithm

Application of calculus in computer science

Are there decidable problems for which for no algorithm we can give time bounds?

Implications of unprovability of $P\neq NP$

What's the "real" reason that IP=PSPACE is non-relativizing?

Ranking the Difficulty of NP Hard Problems in Practice

SAT algorithms not based on DPLL

How should one simulate self-avoiding random walks?

Casual tours around proofs

Constructing uniquely satisfiable formulas

Hilbert's Tenth Problem and nonrecursive Diophantine sets

Complexity of computing the discrete Fourier transform?

Maximal/maximum independent sets

Cohomological approach to boolean complexity

Proofs obtained only through spectral graph theory

What would it mean to disprove Church-Turing thesis?

Compendium of the Best Approximation and Hardness Results for NP optimization problems

Should experts in TCS charge money to read proofs that P != NP?

Proofs that expose a deeper structure

Are recursive forms of Godel's statement possible?

Which interesting theorems in TCS rely on the Axiom of Choice? (Or alternatively, the Axiom of Determinacy?)

How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?