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

Memory requirement for fast matrix multiplication

9 votes
0 answers
556 views

Exponential time hypothesis for random algorithms

1 vote
1 answer
99 views

Inequality for p-norm of probability distributions

4 votes
0 answers
132 views

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

1 vote
0 answers
58 views

NC algorithm for rank of skinny matrix

3 votes
0 answers
175 views

Algorithm (parallel and serial) for Gram-Schmidt

9 votes
1 answer
381 views

$k$-wise independent probability spaces

2 votes
0 answers
83 views

Complexity of counting codeword length distribution

4 votes
1 answer
430 views

Parallel (NC) replacements for Gaussian elimination?

6 votes
2 answers
202 views

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

4 votes
1 answer
334 views

Algorithms with multiple right answers --- complexity theory terminology

8 votes
1 answer
2k views

Algorithms for finding clique in bounded-degree graph

15 votes
2 answers
405 views

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

5 votes
0 answers
127 views

Truncated convolution algorithm

5 votes
1 answer
826 views

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

7 votes
1 answer
797 views

Numerically stable fast convolution algorithm?

2 votes
1 answer
275 views

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

0 votes
0 answers
132 views

Approximation algorithms based on relaxing a feasible to infeasible solution?

6 votes
0 answers
105 views

Evaluate polynomial involving nearly-minimal graph cuts

9 votes
2 answers
413 views

A subset lookup algorithm

16 votes
4 answers
3k views

Definition of matrix-multiplication exponent $\omega$

10 votes
3 answers
703 views

Computational hardness of "real" computer programs

8 votes
0 answers
155 views

RAM simulating another RAM

1 vote
0 answers
144 views

Unwinding a data structure to a previous state