user avatar
user avatar
user avatar
Lieuwe Vinkhuijzen
  • Member for 6 years, 10 months
  • Last seen this week
141 votes
30 answers
24k views

Problems Between P and NPC

  • 11.8k
66 votes
5 answers
6k views

The origin of the notion of treewidth

  • 1,933
62 votes
13 answers
8k views

Open problems on the frontiers of TCS

35 votes
1 answer
3k views

Consequences of $\mathsf{NP}$ containing $\mathsf{BPP}$

  • 21.3k
34 votes
2 answers
3k views

NTIME(n^k) ≠ DTIME(n^k) ?

  • 4,400
31 votes
1 answer
792 views

Can graph isomorphism be decided with square root bounded nondeterminism?

26 votes
4 answers
2k views

Proofs, Barriers and P vs NP

20 votes
0 answers
455 views

Interesting PCP characterization of classes smaller than P?

  • 2,271
20 votes
0 answers
779 views

Weighted Hamming distance

20 votes
2 answers
686 views

For a random oracle R, does BPP equal the set of computable languages in P^R?

17 votes
2 answers
2k views

Gentle introduction to graph isomorphism for bounded valance graphs

  • 1,261
14 votes
0 answers
339 views

Fourier spectrum of the parity of two monotone Boolean functions

  • 4,341
13 votes
2 answers
2k views

Sources of open problems?

10 votes
2 answers
1k views

Is it known whether $BPP\cap NP\subseteq RP$?

1 vote
1 answer
150 views

Is $CAPP \in P$ known to collapse some quantum complexity classes to classical ones?