Time hierarchies for cryptographic function inversion with advice
From MaRDI portal
Publication:843601
DOI10.1007/s10958-009-9403-5zbMath1178.94188MaRDI QIDQ843601
Edward A. Hirsch, K. V. Pervyshev, Dima Yu. Grigoriev
Publication date: 15 January 2010
Published in: Journal of Mathematical Sciences (New York) (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/21.11116/0000-0004-268E-2
94A60: Cryptography
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A Turing machine time hierarchy
- Non-deterministic exponential time has two-prover interactive protocols
- On total functions, existence theorems and computational complexity
- One way functions and pseudorandom generators
- A hierarchy for nondeterministic time complexity
- A generic time hierarchy with one bit of advice
- Pseudorandomness and average-case complexity via uniform reductions
- From Logarithmic Advice to Single-Bit Advice
- Hierarchies for semantic classes
- Separating Nondeterministic Time Complexity Classes
- Foundations of Cryptography
- On the Computational Complexity of Algorithms
- Two-Tape Simulation of Multitape Turing Machines
- The complexity theory companion