2 papers
cs.CC2005
Simple extractors via constructions of cryptographic pseudo-random generators
Marius Zimand
Trevisan has shown that constructions of pseudo-random generators from hard functions (the Nisan-Wigderson approach) also produce extractors. We show that constructions of pseudo-r…
quant-ph1999
Almost-Everywhere Superiority for Quantum Computing
Edith Hemaspaandra, Lane A. Hemaspaandra, Marius Zimand
Simon as extended by Brassard and Høyer shows that there are tasks on which polynomial-time quantum machines are exponentially faster than each classical machine infinitely often.…