Approximating Sumset Size
Approximating Sumset Size
复制标题
近似总集大小
DOI：
10.1137/1.9781611977073.94
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Servedio, Rocco A.
中科院分区：
文献类型：
--
作者：
De, Anindya;Nadimpali, Shivam;Servedio, Rocco A.
给定当时维布尔超立方体的一个子集A，集A+A是集{a+a‘：A，a’∊A}中的加法。和集在加性组合数学中起着重要的作用，在该领域的许多核心结果中都具有重要作用。本文的主要结果是求和集大小估计问题的一个次线性时间算法。更详细地，我们的算法被给予先知访问任意和精度参数∊>；0的(指示函数)，并且它很可能输出一个值0≤v≤1，该值对于某些扰动A‘∊Aof满足性Vol(A\A’)≤∊是±∊-接近Vol(A‘+A’)。很容易看出，如果不放松对a‘rather Thana的处理，任何将Vol(A+A)估计为任何非平凡精度的算法都必须进行2次Ω(N)查询。相反，我们给出了一个算法，它的查询复杂度只依赖于∊，与环境维度n完全无关。
Given a subsetAof then-dimensional Boolean hypercube , thesumset A+Ais the set {a + a′ : a, a′∊A} where addition is in . Sumsets play an important role in additive combinatorics, where they feature in many central results of the field.The main result of this paper is a sublinear-time algorithm for the problem ofsumset size estimation. In more detail, our algorithm is given oracle access to (the indicator function of) an arbitrary and an accuracy parameter∊> 0, and with high probability it outputs a value 0 ≤v≤ 1 that is ±∊-close to Vol (A′+A′) for some perturbationA′⊆AofAsatisfying Vol (A \ A′) ≤∊. It is easy to see that without the relaxation of dealing withA′rather thanA, any algorithm for estimating Vol (A+A) to any nontrivial accuracy must make 2Ω(n)queries. In contrast, we give an algorithm whose query complexity depends only on∊and is completely independent of the ambient dimensionn.
登录
查看更多内容
近似单调布尔函数对 $O(sqrt{n})$ 查询复杂度的影响
DOI：
10.1007/978-3-642-22935-0_56
发表时间：
2011
期刊：
ArXiv
影响因子：
--
作者：
D. Ron;R. Rubinfeld;S. Safra;Omri Weinstein
通讯作者：
Omri Weinstein
阿贝尔群中的 Szemerédi 型正则引理及其应用
DOI：
10.1007/s00039-005-0509-8
发表时间：
2003
期刊：
Geometric & Functional Analysis GAFA
影响因子：
--
作者：
B. Green
通讯作者：
B. Green
线性形式的一般系统：均分布和真实复杂性
DOI：
--
发表时间：
2014
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Hamed Hatami;Pooya Hatami;Shachar Lovett
通讯作者：
Shachar Lovett
不知情决策的艺术：性能测试入门
DOI：
--
发表时间：
2004
期刊：
影响因子：
--
作者：
E. Fischer
通讯作者：
E. Fischer
测试低复杂度仿射不变属性
DOI：
10.1137/1.9781611973105.97
发表时间：
2012
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
Arnab Bhattacharyya;E. Fischer;Shachar Lovett
通讯作者：
Shachar Lovett