graffe
  • Member for 11 years, 3 months
  • Last seen more than a month ago
13 answers
38 votes
3k views
22 bookmarks
Inspirational talk for final year high school pupils
10 answers
30 votes
2k views
14 bookmarks
Great algorithms, machine learning and no linear algebra
0 answers
27 votes
689 views
5 bookmarks
Is Hankelability NP-hard?
3 answers
25 votes
2k views
14 bookmarks
Hardness of approximation - additive error
5 answers
23 votes
2k views
4 bookmarks
Packing rectangles into convex polygons but without rotations
1 answers
22 votes
1k views
2 bookmarks
Binary multiplication and parity convolution
0 answers
20 votes
691 views
3 bookmarks
Partial circulant matrices: Is there a non-zero vector $v\in \{-1,0,1\}^n$ such that $Mv=0$?
1 answers
18 votes
840 views
5 bookmarks
Edit distance in sublinear space
5 answers
18 votes
1k views
3 bookmarks
Fast treewidth algorithms
0 answers
17 votes
920 views
8 bookmarks
Longest geometrically increasing subsequence
3 answers
16 votes
1k views
1 bookmarks
Subgraph isomorphism with a tree
0 answers
15 votes
365 views
4 bookmarks
Complexity of approximating the range of a matrix
1 answers
14 votes
1k views
1 bookmarks
The minimum number of arithmetic operations to compute the determinant
3 answers
11 votes
479 views
1 bookmarks
How to iterate over vectors in order of probability in small space
2 answers
10 votes
875 views
3 bookmarks
Problems with no known quantum advantage
1 answers
10 votes
788 views
3 bookmarks
Is it in NP to check if the convex hull contains the unit ball?
2 answers
9 votes
1k views
2 bookmarks
Big gaps between RAM and Turing machine complexity
1 answers
8 votes
287 views
1 bookmarks
Time complexity for a variant of edit distance
3 answers
8 votes
794 views
1 bookmarks
One way randomised communication complexity of disjointness
2 answers
8 votes
718 views
2 bookmarks
Reference for the number of samples needed to distinguish two probability distributions
1 answers
8 votes
407 views
2 bookmarks
Are there poly time algorithms to determine if a graph is almost bipartite?
2 answers
8 votes
859 views
Estimating the rank of a large sparse matrix
2 answers
7 votes
200 views
1 bookmarks
One way communication complexity of multi exact matching
1 answers
5 votes
179 views
Complexity of finding the most likely edge
1 answers
5 votes
702 views
5 bookmarks
Consequences of BPP=BQP
6 answers
5 votes
469 views
1 bookmarks
Is there a linear space lower bound for streaming set equality?
2 answers
5 votes
639 views
1 bookmarks
One-way randomized communication complexity of approximate Hamming distance
1 answers
5 votes
219 views
Lower bounds for formulae sizes for addition
1 answers
5 votes
229 views
Comparison versus RAM models
1 answers
4 votes
142 views
Batch membership testing for convex polyhedron specified in vertex representation