Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Heuristic time hierarchies via hierarchies for sampling distributions. / Itsykson, Dmitry; Knop, Alexander; Sokolov, Dmitry.
Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings. ред. / Khaled Elbassioni; Kazuhisa Makino. Springer Nature, 2015. стр. 201-211 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 9472).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Heuristic time hierarchies via hierarchies for sampling distributions
AU - Itsykson, Dmitry
AU - Knop, Alexander
AU - Sokolov, Dmitry
PY - 2015/1/1
Y1 - 2015/1/1
N2 - We introduce a new framework for proving the time hierarchy theorems for heuristic classes. The main ingredient of our proof is a hierarchy theorem for sampling distributions recently proved by Watson [11]. Class Heur∈FBPP consists of functions with distributions on their inputs that can be computed in randomized polynomial time with bounded error on all except _ fraction of inputs. We prove that for every a, δ and integer k there exists a function F : {0, 1}∗ → {0, 1, . . . , k − 1} such that (F,U) (Formula presented.) Heur∈FBPP for all ∈ > 0 and for every ensemble of distributions Dn samplable in na steps, (F,D) ∈ Heur1−1/k −δFBPTime[na]. This extends a previously known result for languages with uniform distributions proved by Pervyshev [9] by handling the case k > 2. We also prove that P[formula presented] Heur- ∈BPTime[nk] if one-way functions exist. We also show that our technique may be extended for time hierarchies in some other heuristic classes.
AB - We introduce a new framework for proving the time hierarchy theorems for heuristic classes. The main ingredient of our proof is a hierarchy theorem for sampling distributions recently proved by Watson [11]. Class Heur∈FBPP consists of functions with distributions on their inputs that can be computed in randomized polynomial time with bounded error on all except _ fraction of inputs. We prove that for every a, δ and integer k there exists a function F : {0, 1}∗ → {0, 1, . . . , k − 1} such that (F,U) (Formula presented.) Heur∈FBPP for all ∈ > 0 and for every ensemble of distributions Dn samplable in na steps, (F,D) ∈ Heur1−1/k −δFBPTime[na]. This extends a previously known result for languages with uniform distributions proved by Pervyshev [9] by handling the case k > 2. We also prove that P[formula presented] Heur- ∈BPTime[nk] if one-way functions exist. We also show that our technique may be extended for time hierarchies in some other heuristic classes.
UR - http://www.scopus.com/inward/record.url?scp=84951927754&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-48971-0_18
DO - 10.1007/978-3-662-48971-0_18
M3 - Conference contribution
AN - SCOPUS:84951927754
SN - 9783662489703
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 201
EP - 211
BT - Algorithms and Computation - 26th International Symposium, ISAAC 2015, Proceedings
A2 - Elbassioni, Khaled
A2 - Makino, Kazuhisa
PB - Springer Nature
T2 - 26th International Symposium on Algorithms and Computation, ISAAC 2015
Y2 - 9 December 2015 through 11 December 2015
ER -
ID: 49785713