User David Harris

16 votes

4 answers

3k views

Definition of matrix-multiplication exponent $\omega$

ds.algorithms linear-algebra

asked Nov 29, 2011 at 15:43

15 votes

2 answers

405 views

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

cc.complexity-theory asymptotics

asked Oct 20, 2012 at 18:23

12 votes

2 answers

2k views

Memory requirement for fast matrix multiplication

ds.algorithms linear-algebra

asked Aug 12, 2016 at 17:58

10 votes

3 answers

703 views

Computational hardness of "real" computer programs

computability

asked Sep 28, 2011 at 11:22

9 votes

2 answers

413 views

A subset lookup algorithm

ds.algorithms ds.data-structures

asked Jan 3, 2012 at 17:17

9 votes

1 answer

377 views

$k$-wise independent probability spaces

pr.probability limited-independence

asked Apr 2, 2014 at 19:44

9 votes

0 answers

550 views

Exponential time hypothesis for random algorithms

cc.complexity-theory randomized-algorithms

asked Sep 21, 2015 at 11:50

8 votes

1 answer

2k views

Algorithms for finding clique in bounded-degree graph

graph-algorithms

asked Jul 12, 2013 at 14:28

8 votes

0 answers

155 views

RAM simulating another RAM

cc.complexity-theory

asked Jul 15, 2011 at 10:50

7 votes

1 answer

794 views

Numerically stable fast convolution algorithm?

ds.algorithms na.numerical-analysis

asked Aug 8, 2012 at 12:37

6 votes

2 answers

201 views

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

graph-algorithms

asked Feb 19, 2014 at 13:09

6 votes

0 answers

105 views

Evaluate polynomial involving nearly-minimal graph cuts

ds.algorithms graph-theory graph-algorithms

asked Jan 10, 2012 at 19:35

5 votes

1 answer

810 views

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

ds.algorithms terminology asymptotics

asked Aug 13, 2012 at 22:38

5 votes

0 answers

127 views

Truncated convolution algorithm

ds.algorithms fourier-analysis

asked Aug 15, 2012 at 11:29

4 votes

1 answer

334 views

Algorithms with multiple right answers --- complexity theory terminology

cc.complexity-theory

asked Jul 25, 2013 at 18:03

4 votes

1 answer

427 views

Parallel (NC) replacements for Gaussian elimination?

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

asked Mar 21, 2014 at 12:38

3 votes

0 answers

175 views

Algorithm (parallel and serial) for Gram-Schmidt

ds.algorithms linear-algebra dc.parallel-comp

asked Aug 1, 2014 at 15:06

3 votes

0 answers

129 views

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

approximation-hardness set-cover

asked May 18, 2015 at 12:58

2 votes

0 answers

83 views

Complexity of counting codeword length distribution

coding-theory

asked Mar 22, 2014 at 13:27

2 votes

1 answer

273 views

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

ds.algorithms randomized-algorithms pr.probability

asked Mar 12, 2012 at 11:21

1 vote

0 answers

144 views

Unwinding a data structure to a previous state

ds.algorithms

asked Jul 14, 2011 at 17:05

1 vote

0 answers

58 views

NC algorithm for rank of skinny matrix

linear-algebra dc.parallel-comp

asked Oct 17, 2014 at 18:16

1 vote

1 answer

98 views

Inequality for p-norm of probability distributions

pr.probability

asked Jul 14, 2015 at 10:37

0 votes

0 answers

132 views

Approximation algorithms based on relaxing a feasible to infeasible solution?

ds.algorithms approximation-algorithms

asked Feb 9, 2012 at 20:47

Stack Exchange Network

current community

your communities

more stack exchange communities

24 Questions

Definition of matrix-multiplication exponent $\omega$

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

Memory requirement for fast matrix multiplication

Computational hardness of "real" computer programs

A subset lookup algorithm

$k$-wise independent probability spaces

Exponential time hypothesis for random algorithms

Algorithms for finding clique in bounded-degree graph

RAM simulating another RAM

Numerically stable fast convolution algorithm?

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

Evaluate polynomial involving nearly-minimal graph cuts

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

Truncated convolution algorithm

Algorithms with multiple right answers --- complexity theory terminology

Parallel (NC) replacements for Gaussian elimination?

Algorithm (parallel and serial) for Gram-Schmidt

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

Complexity of counting codeword length distribution

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

Unwinding a data structure to a previous state

NC algorithm for rank of skinny matrix

Inequality for p-norm of probability distributions

Approximation algorithms based on relaxing a feasible to infeasible solution?