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

15th Innovations in Theoretical Computer Science Conference (ITCS)

作者： Pratt, Kevin NYU Courant Inst Math Sci Dept Comp Sci New York NY 10012 USA

Suppose that S subset of [n](2) contains no three points of the form (x, y), (x, y + delta), (x + delta, y'), where delta not equal 0. How big can S be? Trivially, n 0, and a construction due to Petrov [19], whic... 详细信息

ISBN: (纸本)9783959773096

Suppose that S subset of [n](2) contains no three points of the form (x, y), (x, y + delta), (x + delta, y'), where delta not equal 0. How big can S be? Trivially, n <= vertical bar S vertical bar <= n(2). Slight improvements on these bounds are obtained from Shkredov's upper bound for the corners problem [23], which shows that vertical bar S vertical bar <= O(n(2)/(log log n)(c)) for some small c > 0, and a construction due to Petrov [19], which shows that vertical bar S vertical bar >= Omega(n log n/root log log n). Could it be that for all epsilon > 0, vertical bar S vertical bar = O(n(1+epsilon))? We show that if so, this would rule out obtaining omega = 2 using a large family of abelian groups in the group-theoretic framework of [12, 11] (which is known to capture the best bounds on. to date), for which no barriers are currently known. Furthermore, an upper bound of O(n(4/3-epsilon)) for any fixed epsilon > 0 would rule out a conjectured approach to obtain omega = 2 of [11]. Along the way, we encounter several problems that have much stronger constraints and that would already have these implications.

关键词： Algebraic computation fast matrix multiplication additive combinatorics

来源：评论

学校读者我要写书评

暂无评论

Sparse Graph Counting and Kelley-Meka Bounds for Binary Systems 65

Sparse Graph Counting and Kelley-Meka Bounds for Binary Syst...

引用

65th Symposium on Foundations of Computer Science

作者： Filmus, Yuval Hatami, Hamed Hosseini, Kaave Kelman, Esty Technion Haifa Israel McGill Univ Montreal PQ Canada Univ Rochester Rochester NY USA Boston Univ Boston MA 02215 USA MIT 77 Massachusetts Ave Cambridge MA 02139 USA

ISBN: (纸本)9798331516758;9798331516741

In a recent breakthrough, Kelley and Meka (FOCS 2023) obtained a strong upper bound on the density of sets of integers without non-trivial three-term arithmetic progressions. In this work, we extend their result, establishing similar bounds for all linear patterns defined by binary systems of linear forms, where "binary" indicates that every linear form depends on exactly two variables. Prior to our work, no strong bounds were known for such systems even in the finite field model setting. A key ingredient in our proof is a graph counting lemma. The classical graph counting lemma, developed by Thomason (Random Graphs 1985) and Chung, Graham, and Wilson (Combinatorica 1989), is a fundamental tool in combinatorics. For a fixed graph H, it states that the number of copies of H in a pseudorandom graph G is similar to the number of copies of H in a purely random graph with the same edge density as G. However, this lemma is only non-trivial when G is a dense graph. In this work, we prove a graph counting lemma that is also effective when G is sparse. Moreover, our lemma is well-suited for density increment arguments in additive number theory. As an immediate application, we obtain a strong bound for the Turan problem in abelian Cayley sum graphs: let Gamma be a finite abelian group with odd order. If a Cayley sum graph on Gamma does not contain any r-clique as a subgraph, it must have at most 2(-Omega r(log1/16 vertical bar Gamma vertical bar)) . vertical bar Gamma vertical bar(2) edges. These results hinge on the technology developed by Kelley and Meka and the follow-up work by Kelley, Lovett, and Meka (STOC 2024).

关键词： sparse graph counting lemma Kelley-Meka bounds Density increment additive combinatorics pseudorandomness and derandomization

来源：评论

学校读者我要写书评

暂无评论

A MAXIMAL EXTENSION OF THE BLOOM-MAYNARD BOUND FOR SETS WITHOUT SQUARE DIFFERENCES

引用

FUNCTIONES ET APPROXIMATIO COMMENTARII MATHEMATICI 2024年第2期71卷 271-296页

作者： Arala, Nuno Univ Warwick Math Inst Zeeman Bldg Coventry CV4 7AL England

We show that if h is an element of Z[x] is a polynomial of degree k such that the congruence h(x) equivalent to 0 (mod q) has a solution for every positive integer q, then any subset of {1, 2,.. ., N} with no two distinct elements with difference of the form h(n), with n positive integer, has density at most (log N)-clog log log N , for some constant c that depends only on k. This improves on the best bound in the literature, due to Rice, and generalizes a recent result of Bloom and Maynard.

关键词： additive combinatorics density increment circle method.

来源：评论

学校读者我要写书评

暂无评论

An Improved Pseudopolynomial Time Algorithm for Subset Sum 65

An Improved Pseudopolynomial Time Algorithm for Subset Sum

引用

65th Symposium on Foundations of Computer Science

作者： Chen, Lin Lian, Jiayi Mao, Yuchen Zhang, Guochuan Zhejiang Univ Hangzhou Peoples R China

ISBN: (纸本)9798331516758;9798331516741

We investigate pseudo-polynomial time algorithms for Subset Sum. Given a multi-set X of n positive integers and a target t, Subset Sum asks whether some subset of X sums to t. Bringmann proposes an (O) over tilde (n + t)-time algorithm [Bringmann SODA'17], and an open question has naturally arisen: can Subset Sum be solved in O(n+w) time? Here w is the maximum integer in X. We make a progress towards resolving the open question by proposing an (O) over tilde (n + root wt)-time algorithm.

关键词： subset sum pseudo-polynomial time algorithms additive combinatorics

来源：评论

学校读者我要写书评

暂无评论

Removing additive Structure in 3SUM-Based Reductions 2023

Removing Additive Structure in 3SUM-Based Reductions

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Jin, Ce Xu, Yinzhan MIT Cambridge MA 02139 USA

ISBN: (纸本)9781450399135

Our work explores the hardness of 3SUM instances without certain additive structures, and its applications. As our main technical result, we show that solving 3SUM on a size-n integer set that avoids solutions to a+b=c+d for {a, b} not equal {c, d} still requires n2-o(1) time, under the 3SUM hypothesis. Such sets are called Sidon sets and are well-studied in the field of additive combinatorics. Combined with previous reductions, this implies that the All-Edges Sparse Triangle problem on n-vertex graphs with maximum degree root n and at most n(k/2) k-cycles for every k >= 3 requires n(2-o(1)) time, under the 3SUM hypothesis. This can be used to strengthen the previous conditional lower bounds by Abboud, Bringmann, Khoury, and Zamir [STOC22] of 4-Cycle Enumeration, Offline Approximate Distance Oracle and Approximate Dynamic Shortest Path. In particular, we show that no algorithm for the 4-Cycle Enumeration problem on n-vertex m-edge graphs with n(o(1)) delays has O(n(2-epsilon)) or O(m(4/3-epsilon)) pre-processing time for epsilon >0. We also present a matching upper bound via simple modifications of the known algorithms for 4-Cycle Detection. A slight generalization of the main result also extends the result of Dudek, Gawrychowski, and Starikovskaya [STOC20] on the 3SUM hardness of nontrivial 3-Variate Linear Degeneracy Testing (3-LDTs): we show 3SUM hardness for all nontrivial 4-LDTs. The proof of our main technical result combines a wide range of tools: Balog-Szemeredi-Gowers theorem, sparse convolution algorithm, and a new almost-linear hash function with almost 3-universal guarantee for integers that do not have small-coefficient linear relations.

关键词： fine-grained complexity 3SUM additive combinatorics graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Parallel Repetition for the GHZ Game: Exponential Decay 64

Parallel Repetition for the GHZ Game: Exponential Decay

引用

64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS)

作者： Braverman, Mark Khot, Subhash Minzer, Dor Princeton Univ Princeton NJ 08544 USA New York Univ New York NY USA MIT Cambridge MA 02139 USA

We show that the value of the n-fold repeated GHZ game is at most 2(-Omega)(n), improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup ty... 详细信息

ISBN: (纸本)9798350318944

关键词： Parallel Repetition GHZ game Abelian Embeddings Analysis of Boolean functions additive combinatorics

来源：评论

学校读者我要写书评

暂无评论

Random Gap Processes and Asymptotically Complete Sequences

引用

JOURNAL OF THEORETICAL PROBABILITY 2022年第2期35卷 801-818页

作者： Brow, Erin Crossen Mkrtchyan, Sevak Pakianathan, Jonathan Univ Rochester Dept Math 500 Joseph C Wilson Blvd Rochester NY 14627 USA

We study a process of generating random positive integer weight sequences {W-n} where the gaps between the weights {X-n = W-n - Wn-1} are i.i.d. positive integer-valued random variables. The main result of the paper is that if the gap distribution has a moment generating function with large enough radius of convergence, then the weight sequence is almost surely asymptotically m-complete for every m >= 2, i.e. every large enough multiple of the greatest common divisor (gcd) of gap values can be written as a sum of m distinct weights for any fixed m >= 2. Under the weaker assumption of finite 1/2-moment for the gap distribution, we also show the simpler result that, almost surely, the resulting weight sequence is asymptotically complete, i.e. all large enough multiples of the gcd of the possible gap values can be written as a sum of distinct weights.

关键词： Complete sequences additive combinatorics additive number theory Random gap processes

来源：评论

学校读者我要写书评

暂无评论

Canonical Conditions for K/2 Degrees of Freedom

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2022年第3期68卷 1716-1730页

作者： Guel, Recep Stotz, David Jafar, Syed Ali Boelcskei, Helmut Shamai (Shitz), Shlomo Swiss Fed Inst Technol Chair Math Informat Sci CH-8092 Zurich Switzerland Kantonsschule Schaffhausen CH-8200 Schaffhausen Switzerland Univ Calif Irvine Dept Elect Engn & Comp Sci Irvine CA 92697 USA Technion Israel Inst Technol Dept Elect & Comp Engn IL-3200003 Haifa Israel

We present a condition for 1/2 degree of freedom for each user in constant K-user single-antenna interference channels. This condition is sufficient for all and necessary for almost all channel matrices. Moreover, it applies to all channel topologies, i.e., to fully-connected channels as well as channels that have individual links absent, reflected by corresponding zeros in the channel matrix. Moreover, it captures the essence of interference alignment by virtue of being expressed in terms of a generic injectivity condition that guarantees separability of signal and interference. Finally, we provide codebook constructions achieving 1/2 degree of freedom for each user for all channel matrices satisfying the condition we identified.

关键词： Integrated circuits Interference Transmitters Topology Receivers Entropy Random variables Interference channels (ICs) degrees of freedom (DoF) self-similar distributions additive combinatorics Renyi information dimension

来源：评论

学校读者我要写书评

暂无评论

A Formalisation of the Balog-Szemeredi-Gowers Theorem in Isabelle/HOL 2023

A Formalisation of the Balog-Szemeredi-Gowers Theorem in Isa...

引用

12th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP)

作者： Koutsoukou-Argyraki, Angeliki Baksys, Mantas Edmonds, Chelsea Univ Cambridge Cambridge England

ISBN: (纸本)9798400700262

We describe our formalisation in the interactive theorem prover Isabelle/HOL of the Balog-Szemeredi-Gowers Theorem, a profound result in additive combinatorics which played a central role in Gowers's proof deriving the first effective bounds for Szemeredi's Theorem. The proof is of great mathematical interest given that it involves an interplay between different mathematical areas, namely applications of graph theory and probability theory to additive combinatorics involving algebraic objects. This interplay is what made the process of the formalisation, for which we had to develop formalisations of new background material in the aforementioned areas, more rich and technically challenging. We demonstrate how locales, Isabelle's module system, can be employed to handle such interplays in mathematical formalisations. To treat the graph-theoretic aspects of the proof, we make use of a new, more general undirected graph theory library developed by Edmonds, which is both flexible and extensible. In addition to the main theorem, which, following our source, is formulated for difference sets, we also give an alternative version for sumsets which required a formalisation of an auxiliary triangle inequality. We moreover formalise a few additional results in additive combinatorics that are not used in the proof of the main theorem. This is the first formalisation of the Balog-Szemeredi-Gowers Theorem in any proof assistant to our knowledge.

关键词： interactive theorem proving proof assistant formalisation of mathematics Isabelle/HOL additive combinatorics graph theory probabilistic method

来源：评论

学校读者我要写书评

暂无评论

Part I: Uniform Estimates for Operators Involving Polynomial Curves. Part II: Decoupling Estimates for Fractal and Product Sets

Part I: Uniform Estimates for Operators Involving Polynomial...

引用

作者： de Dios Pont, Jaume University of California Los Angeles

学位级别：Ph.D., Doctor of Philosophy

The first part of the thesis focuses on the uniformity of harmonic analysis estimates on curves. We first show a decomposition theorem for polynomial curves on local fields as a bounded number of perturbations of monomial curves. Using this theorem, we extend uniform restriction estimates for real curves to the endpoint case, show uniform decoupling for those curves, and show novel uniform restriction estimates for curves over C, and Qp. We then show uniform estimates for the discrete analog to this problem in a restricted range of exponent. The second part focuses on decoupling estimates for sets with a product or self-similar structure. A recurring phenomenon for those sets is that functions with constant Fourier transform on their support are far from extremizers. As applications we will show a de- coupling estimate for fractal subsets of the parabola, and study subsets of cubes with high additive energy compared to their cardinality.

关键词： additive combinatorics additive energies Decoupling Fourier analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：