user avatar
user avatar
user avatar
Joshua Grochow
  • Member for 11 years, 11 months
  • Last seen this week
75 votes

Funny TCS-related papers etc?

46 votes

Prerequisite for learning GCT

42 votes

Information Theory used to prove neat combinatorial statements?

39 votes

Funny TCS-related papers etc?

38 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

Where to learn more about what Theoretical Computer Science is?

31 votes
Accepted

Hard-looking algorithmic problems made easy by theorems

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

Algebra oriented branch of theoretical computer science

25 votes
Accepted

EXPSPACE-complete problems

24 votes

Obituaries of dead conjectures

24 votes

Can it be determined if language L lies in NP?

23 votes
Accepted

Mulmuley's GCT program

23 votes
Accepted

coNP certificate for Graph Isomorphism

23 votes

Consequences of NP=PSPACE

23 votes

What would be the consequences of PH=PSPACE?

22 votes

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

22 votes

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

22 votes
Accepted

Graph Isomorphism and hidden subgroups

21 votes

Obituaries of dead conjectures

21 votes

Example where equivalence is easy but finding class representative is hard

21 votes

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

20 votes

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

1
2 3 4 5
13