Skip to main content
Mike Battaglia's user avatar
Mike Battaglia's user avatar
Mike Battaglia's user avatar
Mike Battaglia
  • Member for 10 years, 8 months
  • Last seen this week
13 votes
1 answer
567 views

Random Access Machines with only addition, multiplication, equality

10 votes
2 answers
539 views

Do there exist "O(1)-complete" problems?

7 votes
1 answer
3k views

In a bloom filter, why does the optimal number of hashes *increase* with the number of bits in the filter?

6 votes
1 answer
1k views

Do "Type-2" Turing machines with infinite length inputs have more computational power?

5 votes
1 answer
458 views

How hard is random SAT?

4 votes
1 answer
290 views

How many "compressible" strings are there?

4 votes
0 answers
85 views

Real RAMs with "reasonable" operations

3 votes
1 answer
93 views

"Insensitive" CNF/DNF SAT always satisfying same number of clauses

3 votes
1 answer
509 views

Infinite Boolean circuits as a model of computation

3 votes
1 answer
33 views

Variance of MAXSAT clause satisfiability

3 votes
1 answer
47 views

General structure of solutions to 3-SAT circuits

2 votes
2 answers
902 views

Proving that a sentence in first-order logic is not valid

2 votes
1 answer
194 views

The "complexity" of the Turing machine state specification

2 votes
1 answer
408 views

Turing machine with a countably infinite alphabet

2 votes
1 answer
2k views

Intuition behind straight-line programs

2 votes
0 answers
29 views

Complexity class BPP, but with only expected polynomial running time

2 votes
1 answer
49 views

Looking for all "valid" combinations taken from a set of things, where subsets of "valid" things are always "valid"

1 vote
2 answers
78 views

Estimating the number of elements shared in two sets using a random sample

1 vote
0 answers
65 views

Networks and data flow - graph algorithms for propagating updates from nodes correctly

1 vote
0 answers
20 views

How difficult are lattice algorithms for low-dimensional lattices?

1 vote
0 answers
516 views

Does FNP-complete = NP-complete?

1 vote
1 answer
316 views

The sorting problem for partially ordered sets

1 vote
1 answer
298 views

NTM's and the halting problem

1 vote
1 answer
216 views

Complexity of 1-in-3 SAT variant with restrictions on "unique" variables per clause

1 vote
1 answer
960 views

NP-completeness and reduction of MAX-XOR-SAT and MAX-2-XOR-SAT [duplicate]

1 vote
1 answer
178 views

Lack of time hierarchy theorem for probabilistic machines