Skip to main content
Demi's user avatar
Demi's user avatar
Demi's user avatar
Demi
  • Member for 9 years, 11 months
  • Last seen more than a month ago
3 votes
1 answer
479 views

NFA to 2DFA: what are the upper and lower bounds?

8 votes
1 answer
422 views

Resource-bounded variant of Kolmogorov complexity

7 votes
1 answer
369 views

Why is the security of lattice cryptosystems not provable from $P \neq NP$?

5 votes
1 answer
246 views

Why are some classes (ALL, ELEMENTARY, R, etc) badly behaved as oracles?

7 votes
1 answer
195 views

Presburger arithmetic: is it known to be in $EXPSPACE \setminus EXP$?

2 votes
1 answer
135 views

Is it possible to encrypt quantum states under reasonable assumptions?

2 votes
1 answer
114 views

Is a "complete" cipher possible?

1 vote
0 answers
104 views

Why does the Time Hierarchy Theorem fail relative to promise problems?

0 votes
1 answer
93 views

Problems equivalent to the existence of secure cryptosystems? [closed]

4 votes
1 answer
75 views

Is it possible to MAC a quantum state with a classical key under reasonable assumption?

1 vote
0 answers
68 views

Natural problems believed to be in EQP but not BPP