Anonymous's user avatar
Anonymous's user avatar
Anonymous's user avatar
Anonymous
  • Member for 12 years, 9 months
  • Last seen more than 2 years ago
39 votes
2 answers
3k views

Mulmuley's GCT program

31 votes
3 answers
2k views

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

25 votes
4 answers
4k views

Arguments for existence of one-way functions

25 votes
2 answers
2k views

Sum-of-squares proof system

25 votes
4 answers
2k views

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

21 votes
2 answers
1k views

Can addition be carried out in less than depth 5?

20 votes
6 answers
931 views

SAT algorithms not based on DPLL

18 votes
2 answers
792 views

How many tautologies are there?

18 votes
4 answers
856 views

Automated theorem proving in linear logic

16 votes
3 answers
1k views

When can we say that two programs are different?

14 votes
1 answer
701 views

Complexity class associated with exhaustive search

14 votes
4 answers
1k views

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

14 votes
0 answers
452 views

Manuel Blum's supervisory style

14 votes
9 answers
1k views

Counterintuitive results for undergraduates

14 votes
2 answers
714 views

How many negations do we need to compute monotone functions?

11 votes
2 answers
558 views

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

11 votes
1 answer
675 views

Is bitcoin cryptographically secure

11 votes
2 answers
2k views

Worst case to average case reductions

7 votes
0 answers
1k views

Does L=P imply any new complexity class separations?

7 votes
0 answers
230 views

Minimum weight expander

7 votes
1 answer
351 views

How hard is it to learn a linear modular function?

7 votes
1 answer
149 views

Lower bounds for nonuniform circuits and oracles separating complexity classes

7 votes
1 answer
321 views

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

5 votes
1 answer
713 views

Modern distributed computing book

4 votes
2 answers
1k views

Transition Diagram of a Universal Turing Machine

3 votes
1 answer
316 views

Can we efficiently distinguish between P and BPP?

2 votes
2 answers
133 views

Polynomial time construction of families of pairwise nonhomomorphic graphs

-1 votes
1 answer
198 views

Invariance in Property Testing