Skip to main content
Share Your Experience: Take the 2024 Developer Survey
Demi's user avatar
Demi's user avatar
Demi's user avatar
Demi
  • Member for 9 years, 10 months
  • Last seen more than a month ago
8 votes
1 answer
417 views

Resource-bounded variant of Kolmogorov complexity

7 votes
1 answer
193 views

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

7 votes
1 answer
361 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?

4 votes
1 answer
75 views

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

3 votes
1 answer
476 views

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

2 votes
1 answer
135 views

Is it possible to encrypt quantum states under reasonable assumptions?

2 votes
1 answer
113 views

Is a "complete" cipher possible?

1 vote
0 answers
68 views

Natural problems believed to be in EQP but not BPP

1 vote
0 answers
102 views

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

0 votes
1 answer
91 views

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