Top Network Posts

• 17 Fine-grained complexity of BPP
• 15 An algebra of complexity classes
• 15 Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?
• 11 Does $∩_{ε>0} \mathrm{DTIME}(O(n^{2+ε})) = \mathrm{DTIME}(n^{2+o(1)})$?
• 10 Sorting with an average of $\mathrm{lg}(n!)+o(n)$ comparisons
• 9 Best known asymptotic PCP sizes / 3-SAT
• 7 Complexity Class Equalities on the Edge of Inconsistency
• View more network posts →