D.W.'s user avatar
D.W.'s user avatar
D.W.'s user avatar
D.W.
  • Member for 11 years, 4 months
  • Last seen this week
31 votes

Are there any hard instances of 3-SAT when the clauses can only use literals that are "nearby" each other?

23 votes
Accepted

"Almost all objects have property P" vs. "It is easy to test whether an object has property P"

18 votes
Accepted

Password hashing using NP complete problems

16 votes

Data structure to determine if sets are disjoint in o(n) time

16 votes
Accepted

Can theoretical computer science be applied in social sciences?

16 votes

Cryptography without assumptions -- seeking an overview

15 votes
Accepted

Distinguishing between two coins

14 votes
Accepted

Complexity of the $(3,2)_s$ SAT problem?

13 votes
Accepted

Does P = NP imply NP being a strict subset of PSPACE?

11 votes
Accepted

Finding the smallest DFA that separates two words without using brute force search?

11 votes

The utility of Renyi entropies?

10 votes
Accepted

Improving Cook's generic reduction for Clique to SAT?

9 votes

Is there a fast algorithm to quickly evaluate $a^{b^c}$ mod $n$?

9 votes
Accepted

Is this a regular relation?

9 votes

Transition monoid membership for DFAs

9 votes

How hard is it to learn a linear modular function?

9 votes
Accepted

Unique $k$-SAT benchmarks

9 votes

Post correspondence problem for finite monoids

8 votes
Accepted

If only pathological cases of NP-hard problems are difficult to solve, then why isn't NP-hard defined to only include those pathological cases?

8 votes

Why is it difficult to develop a subexponential functoral approach to discrete log

8 votes

Additive combinatorics applications in algorithm design

7 votes
Accepted

Continued Fraction Algorithm in Shor's Algorithm

7 votes

Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?

7 votes
Accepted

Determining if a word of specific length exists that is not accepted by a NFA

7 votes
Accepted

How come Wikipedia says that Random Turing Machines can provide uncomputable output?

6 votes
Accepted

How long does it take to find a short cycle in a random graph?

6 votes

What is the state of the art in online voting?

6 votes
Accepted

Sets of solutions which it is hard to uniformly sample from, but easy to integrate functions over? (Or compute expectations over?)

6 votes
Accepted

SAT formula specifying that exactly $k$ of $N$ boolean variables are active using less than $N$-choose-$k$ terms

6 votes
Accepted

Generating interesting combinatorial optimization problems

1
2 3 4 5
8