共查询到20条相似文献,搜索用时 15 毫秒
1.
2.
3.
Complexity of Hard-Core Set Proofs 总被引:1,自引:1,他引:0
We study a fundamental result of Impagliazzo (FOCS’95) known as the hard-core set lemma. Consider any function f:{0,1}n?{0,1}{f:\{0,1\}^n\to\{0,1\}} which is “mildly hard”, in the sense that any circuit of size s must disagree with f on at least a δ fraction of inputs. Then, the hard-core set lemma says that f must have a hard-core set H of density δ on which it is “extremely hard”, in the sense that any circuit of size
s¢=O(s/(\frac1e2log(\frac1ed))){s'=O(s/(\frac{1}{\epsilon^2}\log(\frac{1}{\epsilon\delta})))} must disagree with f on at least (1-e)/2{(1-\epsilon)/2} fraction of inputs from H. 相似文献
4.
Every Boolean function on n variables can be expressed as a unique multivariate polynomial modulo p for every prime p. In this work, we study how the degree of a function in one characteristic affects its complexity in other characteristics.
We establish the following general principle: functions with low degree modulo p must have high complexity in every other characteristic q. More precisely, we show the following results about Boolean functions f : {0, 1}n → {0, 1} which depend on all n variables, and distinct primes p, q:
o If f has degree o(log n) modulo p, then it must have degree Ω(n1−o(1)) modulo q. Thus a Boolean function has degree o(log n) in at most one characteristic. This result is essentially tight as there exist functions that have degree log n in every characteristic. 相似文献
5.
We prove space hierarchy and separation results for randomized and other semantic models of computation with advice where
a machine is only required to behave appropriately when given the correct advice sequence. Previous works on hierarchy and
separation theorems for such models focused on time as the resource. We obtain tighter results with space as the resource.
Our main theorems deal with space-bounded randomized machines that always halt. Let s(n) be any space-constructible monotone function that is Ω(log n) and let s′(n) be any function such that s′(n) = ω(s(n + as(n))) for all constants a.
|
设为首页 | 免责声明 | 关于勤云 | 加入收藏 |
Copyright©北京勤云科技发展有限公司 京ICP备09084417号 |