graffe
  • Member for 11 years, 3 months
  • Last seen more than a month ago
11 answers
229 votes
119k views
100 bookmarks
Is Norbert Blum's 2017 proof that $P \ne NP$ correct?
3 answers
56 votes
2k views
23 bookmarks
Surprising algorithms for counting problems
2 answers
30 votes
1k views
11 bookmarks
Commonest Subsequence
4 answers
28 votes
832 views
5 bookmarks
Complexity of minimising polynomial formula size
1 answers
23 votes
818 views
7 bookmarks
Required delta between proceedings and journal versions
2 answers
22 votes
865 views
6 bookmarks
Multiplicative version of 3-SUM
1 answers
18 votes
840 views
5 bookmarks
Edit distance in sublinear space
0 answers
17 votes
920 views
8 bookmarks
Longest geometrically increasing subsequence
0 answers
15 votes
365 views
4 bookmarks
Complexity of approximating the range of a matrix
0 answers
13 votes
192 views
3 bookmarks
Complexity to compute the eigenvalue signs of the adjacency matrix
2 answers
10 votes
877 views
3 bookmarks
Problems with no known quantum advantage
2 answers
9 votes
474 views
3 bookmarks
High-level overview of Razborov's method of approximations
1 answers
6 votes
253 views
2 bookmarks
Why is the first step in the Lovasz-Vempala convex volume algorithm correct?
1 answers
5 votes
158 views
1 bookmarks
Interesting programs on small machines
2 answers
5 votes
639 views
1 bookmarks
One-way randomized communication complexity of approximate Hamming distance
0 answers
5 votes
218 views
1 bookmarks
What exactly did Lenstra prove on mixed integer linear program?
0 answers
2 votes
90 views
1 bookmarks
Is berklemap-massey works on extention field