Top Network Posts

• 17 Fine-grained complexity of BPP
• 16 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
• 8 Complexity of fractional SAT
• View more network posts →