We prove a time hierarchy theorem for inverting functions computable in polynomial time with one bit of advice. In particular, we prove that if there is a strongly one-way function, then for any k and for any polynomial p, there is a function f computable in linear time with one ... more >>>

We show that for any reasonable semantic model of computation and for any positive integer $a$ and rationals $1 \leq c < d$, there exists a language computable in time $n^d$ with $a$ bits of advice but not in time $n^c$ with $a$ bits of advice. A semantic model is ... more >>>

We study the existence of time hierarchies for heuristic (average-case) algorithms. We prove that a time hierarchy exists for heuristics algorithms in such syntactic classes as NP and co-NP, and also in semantic classes AM and MA. Earlier, Fortnow and Santhanam (FOCS'04) proved the existence of a time hierarchy for ... more >>>

We study class AvgBPP that consists of distributional problems that can be solved in average polynomial time (in terms of Levin's average-case complexity) by randomized algorithms with bounded error. We prove that there exists a distributional problem that is complete for AvgBPP under polynomial-time samplable distributions. Since we use deterministic ... more >>>