David Harris
  • Member for 10 years, 7 months
  • Last seen this week
4 answers
16 votes
3k views
1 bookmarks
Definition of matrix-multiplication exponent $\omega$
2 answers
15 votes
398 views
1 bookmarks
Under what circumstances do $O(n^{a + \epsilon})$ algorithms imply $O(n^{a+o(1)})$ algorithms?
2 answers
12 votes
2k views
1 bookmarks
Memory requirement for fast matrix multiplication
3 answers
10 votes
703 views
2 bookmarks
Computational hardness of "real" computer programs
0 answers
9 votes
531 views
Exponential time hypothesis for random algorithms
1 answers
9 votes
364 views
1 bookmarks
$k$-wise independent probability spaces
2 answers
9 votes
411 views
2 bookmarks
A subset lookup algorithm
1 answers
8 votes
1k views
1 bookmarks
Algorithms for finding clique in bounded-degree graph
0 answers
8 votes
153 views
RAM simulating another RAM
1 answers
7 votes
760 views
Numerically stable fast convolution algorithm?
2 answers
6 votes
198 views
1 bookmarks
Testing $H$ a topological minor of $G$ --- algorithms that scale with $H$?
0 answers
6 votes
105 views
Evaluate polynomial involving nearly-minimal graph cuts
0 answers
5 votes
126 views
Truncated convolution algorithm
1 answers
5 votes
749 views
$O(m+n)$ really necessary for graph algorithms?
1 answers
4 votes
407 views
2 bookmarks
Parallel (NC) replacements for Gaussian elimination?
1 answers
4 votes
333 views
Algorithms with multiple right answers --- complexity theory terminology
0 answers
3 votes
124 views
1 bookmarks
Set cover approximation ratio as a function of m (number of sets)
0 answers
3 votes
171 views
1 bookmarks
Algorithm (parallel and serial) for Gram-Schmidt
0 answers
2 votes
83 views
Complexity of counting codeword length distribution
1 answers
2 votes
265 views
Generate random permutation via iid uniforms --- is inverse transformation possible?
1 answers
1 votes
95 views
Inequality for p-norm of probability distributions
0 answers
1 votes
57 views
NC algorithm for rank of skinny matrix
0 answers
1 votes
144 views
Unwinding a data structure to a previous state
0 answers
0 votes
132 views
Approximation algorithms based on relaxing a feasible to infeasible solution?