David Harris

Member for 12 years, 3 months
Last seen more than 1 year ago

Summary

Reputation

3,488

3.5k
3.4k
3.4k

2020
2021
2022
2023

Top tag

cc.complexity-theory

Next privilege

5,000 Rep.

Approve tag wiki edits

Badges

21

24

Newest

Yearling

Next badge

0/1

Excavator

Answers

View all 30 answers

Score Activity Newest

32

Finite automata that accept binary strings divisible by n

Jan 29, 2012

16

Is every busy beaver strictly monotonic asymptotically?

Jan 7, 2012

11

Is there a randomized complexity class analogous to $\mathsf{P/Poly}$?

Aug 15, 2015

10

Boolean as subtype of integer

Dec 3, 2011

10

On the need for a self-correcting function in the PCP theorem

Dec 5, 2011

Questions

View all 24 questions

Score Activity Newest Views

16

Definition of matrix-multiplication exponent $\omega$

Nov 29, 2011

15

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

Oct 20, 2012

12

Memory requirement for fast matrix multiplication

Aug 12, 2016

10

Computational hardness of "real" computer programs

Sep 28, 2011

9

A subset lookup algorithm

Jan 3, 2012

Tags

View all 59 tags

cc.complexity-theory

65

Score

17

posts

computability

42

Score

7

posts

automata-theory

41

Score

2

posts

turing-machines

29

Score

3

posts

complexity-classes

24

Score

4

posts

Reputation

This user has no recent positive reputation changes.

Badges

View all badges

This user doesn’t have any gold badges yet.

21

silver badges

Enthusiast

Dec 15, 2011
Good Answer

Feb 22, 2014
Notable Question

Sep 14, 2021

24

bronze badges

Curious

Jul 2, 2014
Revival

Jan 5, 2012
Citizen Patrol

Nov 23, 2011

Accounts

View all 6 accounts

Theoretical Computer Science

3,488
21
24

3,367
1
23
36

1,009
6
13

559
4
9

163
4

Active bounties (0)

Active Offered Earned

This user has no active bounties

Votes cast

60

upvotes

10

downvotes

23

question votes

47

answer votes