检索结果-内蒙古大学图书馆

15th Australasian Conference, ACISP 2010

作者： Chaabouni, Rafik Lipmaa, Helger Shelat, Abhi Ecole Polytech Fed Lausanne Lausanne Switzerland Cybernetica AS Tallinn Estonia Tallinn Univ Tallinn Estonia Univ Virginia Charlottesville VA USA

ISBN: (纸本)9783642140808

We show how to express an arbitrary integer interval I = [0, H] as a sumset I = Sigma(l)(i=1) G(i) * [0, u - 1] + [0, H'] of smaller integer intervals for some small values l, u, and H' < u - 1, where b * A = {ba: a is an element of A} and A + B = {a + b : a is an element of A boolean AND b is an element of B}. We show how to derive such expression of I as a sumset for any value of 1 < u < H, and in particular, how the coefficients G(i) can be found by using a nontrivial but efficient algorithm. This result may be interesting by itself in the context of additive combinatorics. Given the sumset-representation of I, we show how to decrease both the communication complexity and the computational complexity of the recent pairing-based range proof of Camenisch, Chaabouni and shelat from ASIACRYPT 2008 by a factor of 2. Our results are important ill applications like e-voting where a voting server has to verify thousands of proofs of e-vote correctness per hour. Therefore, our new result in additive combinatorics has direct relevance in practice.

关键词： additive combinatorics cryptographic range proof sumset zero knowledge

来源：评论

学校读者我要写书评

暂无评论

Characterizing Degrees of Freedom Through additive combinatorics

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2016年第11期62卷 6423-6435页

作者： Stotz, David Bolcskei, Helmut Swiss Fed Inst Technol Dept Informat Technol & Elect Engn Zurich Switzerland

We establish a formal connection between the problem of characterizing degrees of freedom (DoF) in constant single-antenna interference channels (ICs) with general channel matrix and the field of additive combinatorics. The theory we develop is based on a recent breakthrough result by Hochman, 2014, in fractal geometry. Our first main contribution is an explicit condition on the channel matrix to admit full, i.e., K/2 DoF;this condition is satisfied for almost all channel matrices. We also provide a construction of corresponding full DoF-achieving input distributions. The second main result is a new DoF-formula exclusively in terms of Shannon entropy. This formula is more amenable to both analytical statements and numerical evaluations than the DoF-formula by Wu et al., 2015, which is in terms of Renyi information dimension. We then use the new DoF-formula to shed light on the hardness of finding the exact number of DoF in ICs with rational channel coefficients, and to improve the best known bounds on the DoF of a well-studied channel matrix.

关键词： Interference channel degrees of freedom additive combinatorics sumset theory Renyi information dimension

来源：评论

学校读者我要写书评

暂无评论

A FASTER EXPONENTIAL TIME ALGORITHM FOR BIN PACKING WITH A CONSTANT NUMBER OF BINS VIA additive combinatorics

引用

SIAM JOURNAL ON COMPUTING 2023年第6期52卷 1369-1412页

作者： Nederlof, Jesper Pawlewicz, Jakub Swennenhuis, Celine M. F. Wegrzycki, Karol Univ Utrecht Dept Informat & Comp Sci Utrecht Netherlands Univ Warsaw Fac Math Informat & Mech IDEAS NCBR Warsaw Poland Univ Warsaw Fac Math Informat & Mech Warsaw Poland Eindhoven Univ Technol Dept Math & Comp Sci Eindhoven Netherlands Saarland Univ Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany Max Planck Inst Informat Saarland Informat Campus Saarbrucken Germany

In the Bin Packing problem one is given n items with weights w(1),... ,w(n) and m bins with capacities c1 , . . . , cm. The goal is to partition the items into sets S1 , . . . , Sm such that w(S-j)<= c(j) for every bin j, where w(X) denotes & sum;(i is an element of X )w(i) Bjorklund, Husfeldt, and Koivisto [SIAM J. Comput. , 39 (2009), pp. 546--563] presented an O-star(2(n)) time algorithm for Bin Packing (the O-star(.) notation omits factors polynomial in the input size). In this paper, we show that for every m is an element of N there exists a constant sigma(m) > 0 such that an instance of Bin Packing with m bins can be solved in O(2((1-sigma m)n)) randomized time. Before our work, such improved algorithms were not known even for m = 4. A key step in our approach is the following new result in Littlewood--Offord theory on the additive combinatorics of subset sums: For every delta> 0 there exists an epsilon > 0 such that if |{X subset of{1,& mldr;,n}:w(X)=v}|>= 2((1-epsilon)n) for some v then |{w(X):X subset of{1,& mldr;,n}}|<= 2(delta n)

关键词： Bin Packing additive combinatorics Littlewood--Offord theory algorithms

来源：评论

学校读者我要写书评

暂无评论

EVALUATION OF POLYNOMIALS OVER FINITE RINGS VIA additive combinatorics

引用

PUBLICACIONS MATEMATIQUES 2022年第1期66卷 197-205页

作者： Karolyi, Gyula Szabo, Csaba Alfred Renyi Inst Math 13-15 Realtanoda Utca H-1053 Budapest Hungary Eotvos Lorand Univ Inst Math 1-C Pazmany Peter Setany H-1117 Budapest Hungary

We give an improved polynomial bound on the complexity of the equation solvability problem, or more generally, of finding the value sets of polynomials over finite nilpotent rings. Our proof depends on a result in add... 详细信息

关键词： additive combinatorics Chevalley's theorem dichotomy nilpotent rings Olson's theorem polynomial method equation solvability problem

来源：评论

学校读者我要写书评

暂无评论

Some additive combinatorics problems in matrix rings

引用

REVISTA MATEMATICA COMPLUTENSE 2010年第2期23卷 501-513页

作者： Ferguson, Ron Hoffman, Corneliu Luca, Florian Ostafe, Alina Shparlinski, Igor E. Macquarie Univ Dept Comp Sydney NSW 2109 Australia Univ Vlora Dept Math Vlora Albania Univ Birmingham Sch Math Birmingham B15 2TT W Midlands England UNAM Inst Matemat Morelia 58089 Michoacan Mexico Univ Zurich Inst Math CH-8057 Zurich Switzerland

We study the distribution of singular and unimodular matrices in sumsets in matrix rings over finite fields. We apply these results to estimate the largest prime divisor of the determinants in sumsets in matrix rings ... 详细信息

关键词： Matrices Finite fields additive combinatorics

来源：评论

学校读者我要写书评

暂无评论

NON-MALLEABLE CODES FROM additive combinatorics

引用

SIAM JOURNAL ON COMPUTING 2018年第2期47卷 524-546页

作者： Aggarwal, Divesh Dodis, Yevgeniy Lovett, Shachar Natl Univ Singapore Sch Comp Singapore Singapore Natl Univ Singapore Ctr Quantum Technol Singapore Singapore NYU Dept Comp Sci 550 1St Ave New York NY 10012 USA Univ Calif San Diego Dept Comp Sci La Jolla CA 92093 USA

Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection) is impossible, for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message or a completely unrelated value. Although such codes do not exist if the family of "tampering functions" F is completely unrestricted, they are known to exist for many broad tampering families F. One such natural family is the family of tampering functions in the so-called split-state model. Here the message m is encoded into two shares L and R, and the attacker is allowed to arbitrarily tamper with L and R individually. The split-state tampering arises in many realistic applications, such as the design of non-malleable secret sharing schemes, motivating the question of designing efficient nonmalleable codes in this model. Prior to this work, non-malleable codes in the split-state model received considerable attention in the literature but either (1) were constructed in the random oracle model, or (2) relied on advanced cryptographic assumptions (such as noninteractive zero-knowledge proofs and leakage-resilient encryption), or (3) could only encode 1-bit messages. As our main result, we build the first efficient, multi-bit, information-theoretically-secure non-malleable code in the split-state model. The heart of our construction uses the following new property of the inner-product function < L, R > over the vector space F-p(n) (for a prime p and large enough dimension n): if L and R are uniformly random over F-p(n), and f,g : F-p(n ) -> F(p)(n )are two arbitrary functions on L and R, then the joint distribution (< L, R >, < f (L), g(R)>) is "close" to the convex combination of "affine distributions" {(U, aU + b) vertical bar a, b is an element of F-p}, where U is uniformly random in F-p. In turn, the proof of this su

关键词： additive combinatorics cryptography coding theory non-malleable codes

来源：评论

学校读者我要写书评

暂无评论

GAPS BETWEEN FRACTIONAL PARTS, AND additive combinatorics

引用

QUARTERLY JOURNAL OF MATHEMATICS 2017年第1期68卷 1-11页

作者： Balog, Antal Granville, Andrew Solymosi, Jozsef Alfred Renyi Inst Math Budapest Hungary Univ Montreal Montreal PQ Canada Univ British Columbia Vancouver BC Canada

We give bounds on the number of distinct differences N-a - a as a varies over all elements of a given finite set A subset of (R/Z)(d), d >= 1 and N-a is a nearest neighbour to a.

关键词： additive combinatorics NEAREST neighbor analysis (Statistics) IRRATIONAL numbers ISOMORPHISMS (Mathematics) REAL numbers

来源：评论

学校读者我要写书评

暂无评论

EXPONENTIAL SUMS AND additive combinatorics

引用

BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY 2021年第3期103卷 506-508页

作者： Macourt, Simon Univ New South Wales Sch Math & Stat Kensington NSW 2052 Australia

An abstract is not available for this content so a preview has been provided. As you have access to this article, a PDF of this content is available in through the ‘Save PDF’ action button. <div

An abstract is not available for this content so a preview has been provided. As you have access to this article, a PDF of this content is available in through the ‘Save PDF’ action button.

关键词： exponential sum additive combinatorics finite field sparse polynomial

来源：评论

学校读者我要写书评

暂无评论

An additive combinatorics approach relating rank to communication complexity

An additive combinatorics approach relating rank to communic...

引用

IEEE 53rd Annual Symposium on Foundations of Computer Science (FOCS)

作者： Ben-Sasson, Eli Lovett, Shachar Ron-Zewi, Noga Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel IAS Sch Math Princeton NJ USA Technion Dept Comp Sci Haifa Israel

ISBN: (纸本)9781467343831

For a {0, 1}-valued matrix M let CC(M) denote the deterministic communication complexity of the boolean function associated with M. It is well-known since the work of Mehlhorn and Schmidt [STOC 1982] that CC(M) is bounded from above by rank(M) and from below by log rank(M) where rank(M) denotes the rank of M over the field of real numbers. Determining where in this range lies the true worst-case value of CC(M) is a fundamental open problem in communication complexity. The state of the art is log(1.631) rank(M) <= CC(M) <= 0.415 rank(M), the lower bound is by Kushilevitz [unpublished, 1995] and the upper bound is due to Kotlov [Journal of Graph Theory, 1996]. Lovasz and Saks [FOCS 1988] conjecture that CC(M) is closer to the lower bound, i.e., CC(M) <= log(c)(rank(M)) for some absolute constant c - this is the famous "log-rank conjecture" - but so far there has been no evidence to support it, even giving a slightly non-trivial (o(rank(M))) upper bound on the communication complexity. Our main result is that, assuming the Polynomial Freiman-Ruzsa (PFR) conjecture in additive combinatorics, there exists a universal constant c such that CC(M) <= c . rank(M)/log rank(M). Although our bound is stated using the rank of M over the reals, our proof goes by studying the problem over the finite field of size 2, and there we bring to bear a number of new tools from additive combinatorics which we hope will facilitate further progress on this perplexing question. In more detail, our proof is based on the study of the "approximate duality conjecture" which was suggested by Ben-Sasson and Zewi [STOC 2011] and studied there in connection to the PFR conjecture. First we improve the bounds on approximate duality assuming the PFR conjecture. Then we use the approximate duality conjecture (with improved bounds) to get our upper bound on the communication complexity of low-rank martices.

关键词： Communication Complexity Log-rank Conjecture additive combinatorics

来源：评论

学校读者我要写书评

暂无评论

Clustered Integer 3SUM via additive combinatorics 15

Clustered Integer 3SUM via Additive Combinatorics

引用

47th Annual ACM Symposium on Theory of Computing (STOC) held as part of the Federated Computing Research Conference

作者： Chan, Timothy M. Lewenstein, Moshe Univ Waterloo Cheriton Sch Comp Sci Waterloo ON Canada Bar Ilan Univ Dept Comp Sci Ramat Gan Israel

ISBN: (纸本)9781450335362

We present a collection of new results on problems related to 3SUM, including: The first truly subquadratic algorithm for computing the (min,+) convolution for monotone increasing sequences with integer values bounded by O(n), solving 3SUM for monotone sets in 2D with integer coordinates bounded by O(n), and preprocessing a binary string for histogram indexing (also called jumbled indexing). The running time is O(n((9+root 177)/12) polylogn) = O(n(1.859)) with randomization, or O(n(1.864)) deterministically. This greatly improves the previous n(2)/2(Omega()root(log n)) time bound obtained from Williams' recent result on all pairs shortest paths [STOC'14], and answers an open question raised by several researchers studying the histogram indexing problem. The first algorithm for histogram indexing for any constant alphabet size that achieves truly subquadratic preprocessing time and truly sublinear query time. A truly subquadratic algorithm for integer 3SUM in the case when the given set can be partitioned into n(1-delta) clusters each covered by an interval of length n, for any constant delta > 0. An algorithm to preprocess any set of n integers so that subsequently 3SUM on any given subset can be solved in O(n(13/7) polylogn) time. All these results are obtained by a surprising new technique, based on the Balog-Szemeredi-Gowers Theorem from additive combinatorics.

关键词： 3SUM convolution additive combinatorics histogram indexing fast Fourier transform matrix multiplication

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：