User David Harris

1

16

votes

2

answers

385

views

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

cc.complexity-theory asymptotics

Oct 24 '12 at 5:18 Yuval Filmus 14k

1

16

votes

4

answers

2k

views

Definition of matrix-multiplication exponent $\omega$

ds.algorithms linear-algebra

Nov 29 '11 at 23:16 Robin Kothari 13k

1

12

votes

2

answers

1k

views

Memory requirement for fast matrix multiplication

ds.algorithms linear-algebra

Nov 23 '16 at 11:29 Community♦ 1

2

10

votes

3

answers

698

views

Computational hardness of “real” computer programs

computability

Sep 29 '11 at 9:03 Neel Krishnaswami 30.1k

9

votes

0

answers

478

views

Exponential time hypothesis for random algorithms

cc.complexity-theory randomized-algorithms

Sep 21 '15 at 11:50 David Harris 3,400

2

9

votes

2

answers

406

views

A subset lookup algorithm

ds.algorithms ds.data-structures

Mar 5 '12 at 16:17 A T 556

1

8

votes

1

answer

282

views

$k$-wise independent probability spaces

pr.probability limited-independence

Apr 3 '14 at 9:54 Marc Bury 1,338

1

8

votes

1

answer

1k

views

Algorithms for finding clique in bounded-degree graph

graph-algorithms

Oct 19 '13 at 5:39 Austin Buchanan 2,161

8

votes

0

answers

152

views

RAM simulating another RAM

cc.complexity-theory

Jul 15 '11 at 10:50 David Harris 3,400

1

7

votes

2

answers

174

views

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

graph-algorithms

Feb 19 '14 at 18:04 Dibyayan 1,006

7

votes

1

answer

662

views

Numerically stable fast convolution algorithm?

ds.algorithms na.numerical-analysis

Aug 9 '12 at 21:05 Raphael 151

6

votes

0

answers

104

views

Evaluate polynomial involving nearly-minimal graph cuts

ds.algorithms graph-theory graph-algorithms

Jan 10 '12 at 19:35 David Harris 3,400

5

votes

0

answers

125

views

Truncated convolution algorithm

ds.algorithms fourier-analysis

Aug 16 '12 at 13:11 David Harris 3,400

5

votes

1

answer

595

views

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

ds.algorithms terminology asymptotics

Aug 14 '12 at 6:28 SamM 1,407

1

3

votes

0

answers

118

views

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

approximation-hardness set-cover

May 18 '15 at 12:58 David Harris 3,400

1

3

votes

0

answers

159

views

Algorithm (parallel and serial) for Gram-Schmidt

ds.algorithms linear-algebra dc.parallel-comp

Aug 1 '14 at 16:03 Community♦ 1

1

3

votes

1

answer

356

views

Parallel (NC) replacements for Gaussian elimination?

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

Mar 21 '14 at 15:51 Kaveh 20.9k

3

votes

1

answer

323

views

Algorithms with multiple right answers — complexity theory terminology

cc.complexity-theory

Jul 25 '13 at 19:10 Kaveh 20.9k

2

votes

0

answers

79

views

Complexity of counting codeword length distribution

coding-theory

Mar 22 '14 at 13:27 David Harris 3,400

2

votes

1

answer

254

views

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

ds.algorithms randomized-algorithms pr.probability

Mar 12 '12 at 15:46 Suresh Venkat 31.4k

1

vote

1

answer

92

views

Inequality for p-norm of probability distributions

pr.probability

Jul 15 '15 at 0:55 usul 6,619

1

vote

0

answers

56

views

NC algorithm for rank of skinny matrix

linear-algebra dc.parallel-comp

Oct 17 '14 at 18:16 David Harris 3,400

1

vote

0

answers

143

views

Unwinding a data structure to a previous state

ds.algorithms

Jul 14 '11 at 18:04 David Harris 3,400

0

votes

0

answers

131

views

Approximation algorithms based on relaxing a feasible to infeasible solution?

ds.algorithms approximation-algorithms

Feb 9 '12 at 22:06 David Harris 3,400

Stack Exchange Network

current community

your communities

more stack exchange communities

Next privilege

Next badge

24 Questions

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

Definition of matrix-multiplication exponent $\omega$

Memory requirement for fast matrix multiplication

Computational hardness of “real” computer programs

Exponential time hypothesis for random algorithms

A subset lookup algorithm

$k$-wise independent probability spaces

Algorithms for finding clique in bounded-degree graph

RAM simulating another RAM

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

Numerically stable fast convolution algorithm?

Evaluate polynomial involving nearly-minimal graph cuts

Truncated convolution algorithm

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

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

Algorithm (parallel and serial) for Gram-Schmidt

Parallel (NC) replacements for Gaussian elimination?

Algorithms with multiple right answers — complexity theory terminology

Complexity of counting codeword length distribution

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

Inequality for p-norm of probability distributions

NC algorithm for rank of skinny matrix

Unwinding a data structure to a previous state

Approximation algorithms based on relaxing a feasible to infeasible solution?