Skip to main content
Joshua Grochow's user avatar
Joshua Grochow's user avatar
Joshua Grochow's user avatar
Joshua Grochow
  • Member for 13 years, 10 months
  • Last seen this week
77 votes

Funny TCS-related papers etc?

48 votes

Prerequisite for learning GCT

43 votes

Information Theory used to prove neat combinatorial statements?

40 votes

Funny TCS-related papers etc?

40 votes
Accepted

Wikipedia-style explanation of Geometric Complexity Theory

37 votes
Accepted

References for TCS proof techniques

34 votes
Accepted

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

31 votes
Accepted

Hard-looking algorithmic problems made easy by theorems

31 votes
Accepted

Where to learn more about what Theoretical Computer Science is?

30 votes

Problems Between P and NPC

29 votes
Accepted

Provable statements about genetic algorithms

28 votes

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

27 votes
Accepted

Does Karp reducibility yield a total order?

26 votes
Accepted

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

26 votes

Everyday encounters with NP-complete problems

25 votes

Can it be determined if language L lies in NP?

25 votes

What would be the consequences of PH=PSPACE?

25 votes

Algebra oriented branch of theoretical computer science

25 votes
Accepted

EXPSPACE-complete problems

24 votes

Obituaries of dead conjectures

23 votes
Accepted

Graph Isomorphism and hidden subgroups

23 votes
Accepted

Mulmuley's GCT program

23 votes
Accepted

coNP certificate for Graph Isomorphism

23 votes

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

22 votes

Example where equivalence is easy but finding class representative is hard

22 votes

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

22 votes

Consequences of NP=PSPACE

22 votes

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

21 votes
Accepted

Entropy and computational complexity

21 votes

Obituaries of dead conjectures

1
2 3 4 5
13