Anonymous's user avatar
Anonymous's user avatar
Anonymous's user avatar
Anonymous
  • Member for 12 years, 10 months
  • Last seen more than 2 years ago
3 votes
1 answer
318 views

Can we efficiently distinguish between P and BPP?

14 votes
0 answers
453 views

Manuel Blum's supervisory style

31 votes
3 answers
2k views

Is there a result in computability theory that does not relativize?

5 votes
1 answer
713 views

Modern distributed computing book

7 votes
1 answer
149 views

Lower bounds for nonuniform circuits and oracles separating complexity classes

14 votes
2 answers
716 views

How many negations do we need to compute monotone functions?

14 votes
9 answers
1k views

Counterintuitive results for undergraduates

7 votes
1 answer
322 views

$NP \not\subseteq BPP \implies NP_{\mathbb{C}} \not\subseteq P_{\mathbb{C}}$

2 votes
2 answers
133 views

Polynomial time construction of families of pairwise nonhomomorphic graphs

11 votes
2 answers
561 views

Is there an explanation for the difficulty of proving quadratic lower bounds for interesting NP problems?

25 votes
4 answers
2k views

Best known deterministic time complexity lower bound for a natural problem in NP

11 votes
1 answer
675 views

Is bitcoin cryptographically secure

7 votes
1 answer
351 views

How hard is it to learn a linear modular function?

14 votes
4 answers
1k views

Are there any known NP problems which are conjectured to be exponentially hard on average?

14 votes
1 answer
702 views

Complexity class associated with exhaustive search

25 votes
2 answers
2k views

Sum-of-squares proof system

7 votes
0 answers
230 views

Minimum weight expander

7 votes
0 answers
1k views

Does L=P imply any new complexity class separations?

21 votes
2 answers
1k views

Can addition be carried out in less than depth 5?

4 votes
2 answers
1k views

Transition Diagram of a Universal Turing Machine

-1 votes
1 answer
199 views

Invariance in Property Testing

16 votes
3 answers
1k views

When can we say that two programs are different?

20 votes
6 answers
937 views

SAT algorithms not based on DPLL

18 votes
4 answers
858 views

Automated theorem proving in linear logic

19 votes
2 answers
793 views

How many tautologies are there?

11 votes
2 answers
2k views

Worst case to average case reductions

25 votes
4 answers
4k views

Arguments for existence of one-way functions

39 votes
2 answers
3k views

Mulmuley's GCT program