User David Harris

4 answers

16 votes

3k views

1 bookmarks

Definition of matrix-multiplication exponent $\omega$

ds.algorithms linear-algebra

Nov 29 '11 at 15:43

2 answers

15 votes

398 views

1 bookmarks

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

cc.complexity-theory asymptotics

Oct 20 '12 at 18:23

2 answers

12 votes

2k views

1 bookmarks

Memory requirement for fast matrix multiplication

ds.algorithms linear-algebra

Aug 12 '16 at 17:58

3 answers

10 votes

703 views

2 bookmarks

Computational hardness of "real" computer programs

computability

Sep 28 '11 at 11:22

0 answers

9 votes

531 views

Exponential time hypothesis for random algorithms

cc.complexity-theory randomized-algorithms

Sep 21 '15 at 11:50

1 answers

9 votes

364 views

1 bookmarks

$k$-wise independent probability spaces

pr.probability limited-independence

Apr 2 '14 at 19:44

2 answers

9 votes

411 views

2 bookmarks

A subset lookup algorithm

ds.algorithms ds.data-structures

Jan 3 '12 at 17:17

1 answers

8 votes

1k views

1 bookmarks

Algorithms for finding clique in bounded-degree graph

graph-algorithms

Jul 12 '13 at 14:28

0 answers

8 votes

153 views

RAM simulating another RAM

cc.complexity-theory

Jul 15 '11 at 10:50

1 answers

7 votes

760 views

Numerically stable fast convolution algorithm?

ds.algorithms na.numerical-analysis

Aug 8 '12 at 12:37

2 answers

6 votes

198 views

1 bookmarks

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

graph-algorithms

Feb 19 '14 at 13:09

0 answers

6 votes

105 views

Evaluate polynomial involving nearly-minimal graph cuts

ds.algorithms graph-theory graph-algorithms

Jan 10 '12 at 19:35

0 answers

5 votes

126 views

Truncated convolution algorithm

ds.algorithms fourier-analysis

Aug 15 '12 at 11:29

1 answers

5 votes

749 views

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

ds.algorithms terminology asymptotics

Aug 13 '12 at 22:38

1 answers

4 votes

407 views

2 bookmarks

Parallel (NC) replacements for Gaussian elimination?

cc.complexity-theory complexity-classes linear-algebra dc.parallel-comp matrices

Mar 21 '14 at 12:38

1 answers

4 votes

333 views

Algorithms with multiple right answers --- complexity theory terminology

cc.complexity-theory

Jul 25 '13 at 18:03

0 answers

3 votes

124 views

1 bookmarks

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

approximation-hardness set-cover

May 18 '15 at 12:58

0 answers

3 votes

171 views

1 bookmarks

Algorithm (parallel and serial) for Gram-Schmidt

ds.algorithms linear-algebra dc.parallel-comp

Aug 1 '14 at 15:06

0 answers

2 votes

83 views

Complexity of counting codeword length distribution

coding-theory

Mar 22 '14 at 13:27

1 answers

2 votes

265 views

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

ds.algorithms randomized-algorithms pr.probability

Mar 12 '12 at 11:21

1 answers

1 votes

95 views

Inequality for p-norm of probability distributions

pr.probability

Jul 14 '15 at 10:37

0 answers

1 votes

57 views

NC algorithm for rank of skinny matrix

linear-algebra dc.parallel-comp

Oct 17 '14 at 18:16

0 answers

1 votes

144 views

Unwinding a data structure to a previous state

ds.algorithms

Jul 14 '11 at 17:05

0 answers

0 votes

132 views

Approximation algorithms based on relaxing a feasible to infeasible solution?

ds.algorithms approximation-algorithms

Feb 9 '12 at 20:47

Stack Exchange Network

current community

your communities

more stack exchange communities

24 Questions