Bussiness ManagementMBAstrategyHuman ResourceMarketingHospitalityE-commerceInternational Tradingproject managementmedia managementLogisticsFinanceAccountingadvertisingLawBusiness LawEducationEconomicsBusiness Reportbusiness planresearch proposal
英语论文题目英语教学英语论文商务英语英语论文格式商务英语翻译广告英语商务英语商务英语教学英语翻译论文英美文学英语语言学文化交流中西方文化差异英语论文范文英语论文开题报告初中英语教学英语论文文献综述英语论文参考文献
ResumeRecommendation LetterMotivation LetterPSapplication letterMBA essayBusiness Letteradmission letter Offer letter
澳大利亚论文英国论文加拿大论文芬兰论文瑞典论文澳洲论文新西兰论文法国论文香港论文挪威论文美国论文泰国论文马来西亚论文台湾论文新加坡论文荷兰论文南非论文西班牙论文爱尔兰论文
小学英语教学初中英语教学英语语法高中英语教学大学英语教学听力口语英语阅读英语词汇学英语素质教育英语教育毕业英语教学法
英语论文开题报告英语毕业论文写作指导英语论文写作笔记handbook英语论文提纲英语论文参考文献英语论文文献综述Research Proposal代写留学论文代写留学作业代写Essay论文英语摘要英语论文任务书英语论文格式专业名词turnitin抄袭检查
temcet听力雅思考试托福考试GMATGRE职称英语理工卫生职称英语综合职称英语职称英语
经贸英语论文题目旅游英语论文题目大学英语论文题目中学英语论文题目小学英语论文题目英语文学论文题目英语教学论文题目英语语言学论文题目委婉语论文题目商务英语论文题目最新英语论文题目英语翻译论文题目英语跨文化论文题目
日本文学日本语言学商务日语日本历史日本经济怎样写日语论文日语论文写作格式日语教学日本社会文化日语开题报告日语论文选题
职称英语理工完形填空历年试题模拟试题补全短文概括大意词汇指导阅读理解例题习题卫生职称英语词汇指导完形填空概括大意历年试题阅读理解补全短文模拟试题例题习题综合职称英语完形填空历年试题模拟试题例题习题词汇指导阅读理解补全短文概括大意
论文作者:留学生论文论文属性:硕士毕业论文 thesis登出时间:2011-01-27编辑:anterran点击率:22269
论文字数:10395论文编号:org201101271015032946语种:英语 English地区:英国价格:免费论文
关键词:decision treeshelp bitsAMSsubject classi cations数学建模英文论文
PRODUCTS AND HELP BITS IN DECISION TREES
NOAM NISANy, STEVEN RUDICHz, AND MICHAEL SAKSx
SIAM J. COMPUT. c° 1999 Society for Industrial and Applied Mathematics
Vol. 28, No. 3, pp. 1035{1050
Abstract. We investigate two problems concerning the complexity of evaluating a function fon k distinct inputs by k parallel decision-tree algorithms.In the product problem, for some xed depth bound d, we seek 代写留学生硕士毕业论文to maximize the fraction of inputk-tuples for which all k decision trees are correct. Assume that for a single input to f, the bestdepth-d decision tree is correct on a fraction p of inputs. We prove that the maximum fraction ofk-tuples on which k depth-d algorithms are all correct is at most pk, which is the trivial lower bound.
We show that if we replace the restriction to depth d by \expected depth d," then this result neednot hold.
In the help-bits problem, before the decision-tree computations begin, up to k¡1 arbitrary binary
questions (help-bit queries) can be asked about the k-tuple of inputs. In the second stage, for each
possible (k¡1)-tuple of answers to the help-bit queries, there is a k-tuple of decision trees where the
ith tree is supposed to correctly compute the value of the function on the ith input, for any inputthat is consistent with the help bits. The complexity here is the maximum depth of any of the treesin the algorithm. We show that for all k suciently large, this complexity isequal to degs(f), whichis the minimum degree of a multivariate polynomial whose sign is equal to f.
Key words. decision trees, help bits
AMS subject classi cations. 68Q05, 68Q25, 68R99, 05D99
PII. S0097539795282444
1. Introduction. Pick your favorite computation model and complexity measure,e.g., Boolean circuit size, communication complexity, decision-tree depth, interactiveproof length, tensor rank, etc. Any attempt to understand such a model andcomplexity measure requires understanding the ways that an \unreasonable" computationcan be more ecient than a \reasonable" one. Of course, what is reasonablechanges as our understanding of the model improves.Suppose we are given several unrelated instances of a problem to solve. The \reasonable"approach is to solve each instance separately; intuitively, any computation
that is useful for solving one instance is irrelevant to any of the others. To what extentis this intuition valid in a given model? The following question is the most commonway of formalizing this.
The direct-sum problem. Suppose that the complexity of computing somefunctionf is c. Is it true that computing f twice, on two unrelated inputs, requires complexity
2c? How about computing f on k unrelated inputs?Versions of this question were rst studied in the context of Boolean circuits
[Ulig, Paul, GF]. Subsequent work has concerned bilinear circuits [JT, Bsh], Booleancircuits [FKN], communication complexity [KRW, KKN], and interactive proofs (seeReceived by the editors March 6, 1995; accepted for publication (in revised form) March 13,1997; published electronically January 29, 1999. A preliminary version of this paper appeared inProceedings of the 35th Annual Symposium on Foundations of Computer Science, IEEE, 1994.
https://www.siam.org/journals/sicomp/28-3/28244.html
yComputer Science Department, Hebrew University, Jerusalem, Israel (noam@cs.huji.ac.il). This
research was supported by BSF grant 92-00043 and by a Wolfson award administered by the Isr本论文由英语论文网提供整理,提供论文代写,英语论文代写,代写论文,代写英语论文,代写留学生论文,代写英文论文,留学生论文代写相关核心关键词搜索。