User Joshua Grochow

75 votes

Funny TCS-related papers etc?

answered Nov 18, 2010 at 3:07

46 votes

Prerequisite for learning GCT

reference-request big-list survey gct

answered Jan 10, 2013 at 5:28

42 votes

Information Theory used to prove neat combinatorial statements?

co.combinatorics big-list it.information-theory

answered Nov 3, 2010 at 1:55

39 votes

Funny TCS-related papers etc?

reference-request soft-question big-list

answered Nov 18, 2010 at 3:08

38 votes

Accepted

Wikipedia-style explanation of Geometric Complexity Theory

cc.complexity-theory gct

answered May 14, 2013 at 22:41

37 votes

Accepted

References for TCS proof techniques

reference-request proof-techniques

answered Aug 18, 2010 at 14:50

34 votes

Accepted

Is P equal to the intersection of all superpolynomial time classes?

cc.complexity-theory ds.algorithms complexity-classes

answered Sep 18, 2014 at 2:13

31 votes

Accepted

Where to learn more about what Theoretical Computer Science is?

reference-request soft-question books

answered Aug 18, 2016 at 17:55

31 votes

Accepted

Hard-looking algorithmic problems made easy by theorems

cc.complexity-theory ds.algorithms graph-algorithms

answered Feb 13, 2014 at 18:59

30 votes

Problems Between P and NPC

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

answered Aug 17, 2010 at 3:12

29 votes

Accepted

Provable statements about genetic algorithms

ds.algorithms ne.neural-evol

answered Sep 1, 2010 at 19:55

28 votes

What are the compelling reasons for believing $L\neq P$?

cc.complexity-theory complexity-classes

answered Oct 8, 2013 at 14:10

27 votes

Accepted

Does Karp reducibility yield a total order?

reductions complexity

answered Feb 20, 2017 at 21:00

26 votes

Accepted

How difficult is it to use the Mulmuley-Sohoni GCT approach to show known complexity separations?

cc.complexity-theory gct

answered Sep 4, 2010 at 16:45

26 votes

Everyday encounters with NP-complete problems

np-hardness big-list

answered Aug 24, 2010 at 14:53

25 votes

Algebra oriented branch of theoretical computer science

soft-question algebra advice-request ct.category-theory

answered Sep 23, 2014 at 17:49

25 votes

Accepted

EXPSPACE-complete problems

cc.complexity-theory reference-request big-list

answered Oct 23, 2014 at 17:27

24 votes

Obituaries of dead conjectures

cc.complexity-theory ds.algorithms

answered Oct 5, 2015 at 20:50

24 votes

Can it be determined if language L lies in NP?

cc.complexity-theory computability turing-machines

answered Aug 17, 2010 at 16:16

23 votes

Accepted

Mulmuley's GCT program

cc.complexity-theory big-picture algebraic-complexity p-vs-np gct

answered Jun 12, 2011 at 1:01

23 votes

Accepted

coNP certificate for Graph Isomorphism

cc.complexity-theory graph-isomorphism

answered Nov 16, 2010 at 20:52

23 votes

Consequences of NP=PSPACE

cc.complexity-theory complexity-classes conditional-results

answered Feb 14, 2014 at 1:06

23 votes

What would be the consequences of PH=PSPACE?

cc.complexity-theory complexity-classes conditional-results

answered Feb 21, 2014 at 15:19

22 votes

Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

cc.complexity-theory ho.history-overview exp-time-algorithms

answered Jan 26, 2021 at 17:42

22 votes

Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?

reference-request soft-question big-list topology

answered Oct 5, 2010 at 16:13

22 votes

Accepted

Graph Isomorphism and hidden subgroups

cc.complexity-theory reference-request quantum-computing graph-isomorphism

answered Aug 16, 2010 at 21:46

21 votes

Obituaries of dead conjectures

cc.complexity-theory ds.algorithms

answered Oct 5, 2015 at 23:17

21 votes

Example where equivalence is easy but finding class representative is hard

cc.complexity-theory

answered Mar 13, 2012 at 23:06

21 votes

Problem in BPP but not known to be in RP or co-RP

cc.complexity-theory complexity-classes randomness

answered May 11, 2012 at 8:13

20 votes

For which problems in P is it easier to verify the result than to find it?

cc.complexity-theory ds.algorithms reference-request

answered Nov 1, 2015 at 2:47

Stack Exchange Network

current community

your communities

more stack exchange communities

361 Answers

Funny TCS-related papers etc?

Prerequisite for learning GCT

Information Theory used to prove neat combinatorial statements?

Funny TCS-related papers etc?

Wikipedia-style explanation of Geometric Complexity Theory

References for TCS proof techniques

Is P equal to the intersection of all superpolynomial time classes?

Where to learn more about what Theoretical Computer Science is?

Hard-looking algorithmic problems made easy by theorems

Problems Between P and NPC

Provable statements about genetic algorithms

What are the compelling reasons for believing $L\neq P$?

Does Karp reducibility yield a total order?

How difficult is it to use the Mulmuley-Sohoni GCT approach to show known complexity separations?

Everyday encounters with NP-complete problems

Algebra oriented branch of theoretical computer science

EXPSPACE-complete problems

Obituaries of dead conjectures

Can it be determined if language L lies in NP?

Mulmuley's GCT program

coNP certificate for Graph Isomorphism

Consequences of NP=PSPACE

What would be the consequences of PH=PSPACE?

Problems that started out with hopelessly intractable algorithms that have since been made extremely efficient

Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?

Graph Isomorphism and hidden subgroups

Obituaries of dead conjectures

Example where equivalence is easy but finding class representative is hard

Problem in BPP but not known to be in RP or co-RP

For which problems in P is it easier to verify the result than to find it?