Badge
| Nice Answer | Answer score of 10 or more. This badge can be awarded multiple times. |
Joshua Grochow earned this badge 47 times |
mar 20 at 0:03
Lower bound on number of oracle calls for solving $n$ instances of the halting problem
feb 12 at 1:24
Are there any problems whose best known algorithm has run time $O\left(\frac{f(n)}{\log n}\right)$
feb 8 at 21:44
Natural candidates for the hierarchy inside NPI
jan 10 at 10:24
Prerequisite for learning GCT
dec 26 at 19:23
If P = BQP, does this imply that PSPACE (= IP) = AM?
dec 17 at 21:23
Is semantic language complexity class UP Turing equivalent to syntactic language complexity class US?
dec 10 at 12:47
What papers should everyone read?
nov 30 at 14:03
Why lower bounds for boolean Circuits does not imply arithmetic circuits lower bounds
oct 29 at 0:59
Forcing method used in Baker-Gill-Solovay Relativization paper and Cohen's Proof of Continuum Hypothesis Independence
oct 26 at 9:57
Algorithms and structural complexity theory
oct 17 at 15:51
Gaussian Elimination in terms of Group Action
jun 11 '12 at 20:17
Survey on #P and/or counting problems
may 11 '12 at 17:51
Problem in BPP but not known to be in RP or co-RP
mar 15 '12 at 18:26
Example where equivalence is easy but finding class representative is hard
feb 29 '12 at 4:32
Funny TCS-related papers etc?
nov 23 '11 at 2:23
Many-one reductions vs. Turing reductions to define NPC
jul 25 '11 at 18:27
What hierarchies and/or hierarchy theorems do you know?
jun 24 '11 at 9:01
What is the quantum computational model?
jun 12 '11 at 16:51
Mulmuley's GCT program
may 27 '11 at 16:19
What is the complexity class most closely associated with what the human mind can accomplish quickly?
may 27 '11 at 12:54
Relationship between symmetry and computational intractability?
apr 22 '11 at 14:23
what are known bounds on complexity of nontrivial graph automorphism
mar 9 '11 at 0:36
Evidence that matrix multiplication can be done in quadratic time?
dec 1 '10 at 19:24
Explicit polynomials in 1 variable with superlogarithmic circuit complexity lower bounds?
nov 30 '10 at 17:28
Does the existence of PH-complete problems relativize?
nov 22 '10 at 7:04
coNP certificate for Graph Isomorphism
nov 18 '10 at 21:41
Funny TCS-related papers etc?
nov 18 '10 at 15:45
Funny TCS-related papers etc?
nov 14 '10 at 20:57
Graph Isomorphism and hidden subgroups
nov 12 '10 at 10:20
Applications of topology to computer science
nov 4 '10 at 17:33
Where and how did computers help prove a theorem?
nov 3 '10 at 6:12
Information Theory used to prove neat combinatorial statements?
oct 31 '10 at 0:41
How does the Mulmuley-Sohoni geometric approach to producing lower bounds avoid producing natural proofs (in the Razborov-Rudich sense)?
oct 28 '10 at 17:41
Examples of “Unrelated” Mathematics Playing a Fundamental Role in TCS?
sep 11 '10 at 2:31
For which algorithms is there a large gap between the theoretical analysis and reality?
sep 6 '10 at 22:31
How difficult is it to use the Mulmuley-Sohoni GCT approach to show *known* complexity separations?
sep 2 '10 at 9:21
Provable statements about genetic algorithms
aug 30 '10 at 14:09
Everyday encounters with NP-complete problems
aug 27 '10 at 9:58
References for TCS proof techniques
aug 24 '10 at 2:02
Problems Between P and NPC
aug 19 '10 at 14:39
Can it be determined if language L lies in NP?
