user avatar
user avatar
user avatar
David Harris
  • Member for 11 years, 2 months
  • Last seen more than a month ago
16 votes
4 answers
3k views

Definition of matrix-multiplication exponent $\omega$

15 votes
2 answers
405 views

Under what circumstances do $O(n^{a + \epsilon})$ algorithms imply $O(n^{a+o(1)})$ algorithms?

12 votes
2 answers
2k views

Memory requirement for fast matrix multiplication

10 votes
3 answers
703 views

Computational hardness of "real" computer programs

9 votes
2 answers
413 views

A subset lookup algorithm

9 votes
1 answer
377 views

$k$-wise independent probability spaces

9 votes
0 answers
550 views

Exponential time hypothesis for random algorithms

8 votes
1 answer
2k views

Algorithms for finding clique in bounded-degree graph

8 votes
0 answers
155 views

RAM simulating another RAM

7 votes
1 answer
794 views

Numerically stable fast convolution algorithm?

6 votes
2 answers
201 views

Testing $H$ a topological minor of $G$ --- algorithms that scale with $H$?

6 votes
0 answers
105 views

Evaluate polynomial involving nearly-minimal graph cuts

5 votes
1 answer
810 views

$O(m+n)$ really necessary for graph algorithms?

5 votes
0 answers
127 views

Truncated convolution algorithm

4 votes
1 answer
334 views

Algorithms with multiple right answers --- complexity theory terminology

4 votes
1 answer
427 views

Parallel (NC) replacements for Gaussian elimination?

3 votes
0 answers
175 views

Algorithm (parallel and serial) for Gram-Schmidt

3 votes
0 answers
129 views

Set cover approximation ratio as a function of m (number of sets)

2 votes
0 answers
83 views

Complexity of counting codeword length distribution

2 votes
1 answer
273 views

Generate random permutation via iid uniforms --- is inverse transformation possible?

1 vote
0 answers
144 views

Unwinding a data structure to a previous state

1 vote
0 answers
58 views

NC algorithm for rank of skinny matrix

1 vote
1 answer
98 views

Inequality for p-norm of probability distributions

0 votes
0 answers
132 views

Approximation algorithms based on relaxing a feasible to infeasible solution?