Publication:4650347

zbMath1106.68048MaRDI QIDQ4650347

Marius Zimand

Publication date: 11 February 2005

Full work available at URL: http://www.sciencedirect.com/science/book/9780444828415

zbMATH Keywords

quantum computation; hardness amplification; probabilistically checkable proofs; resource-bounded measure; pseudo-random generators; average-complexity

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

81P68: Quantum computation

68P25: Data encryption (aspects in computer science)

03D15: Complexity of computation (including implicit computational complexity)

68-02: Research exposition (monographs, survey articles) pertaining to computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

Related Items

BOX-COUNTING DIMENSION COMPUTED BY α-DENSE CURVES, Algorithmically independent sequences, Two sources are better than one for increasing the Kolmogorov complexity of infinite sequences, Quantum one-way permutation over the finite field of two elements, Simple extractors via constructions of cryptographic pseudo-random generators