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

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

作者： Abboud, Amir Bringmann, Karl Fischer, Nick Weizmann Inst Sci Rehovot Israel Saarland Univ Max Planck Inst Informat Saarbrucke Germany

ISBN: (纸本)9781450399135

The short cycle removal technique was recently introduced by Abboud, Bringmann, Khoury and Zamir (STOC 22) to prove fine-grained hardness of approximation. Its main technical result is that listing all triangles in an n(1/2)-regular graph is n(2-o(1))-hard even when the number of short cycles is small;namely, when the number of k-cycles is O(n(k/2+gamma)) for gamma < 1/2. Its corollaries are based on the 3-SUM conjecture and their strength depends on gamma, i.e. on how effectively the short cycles are removed. Abboud et al. achieve gamma >= 1/4 by applying structure versus randomness arguments on graphs. In this paper, we take a step back and apply conceptually similar arguments on the numbers of the 3-SUM problem, from which the hardness of triangle listing is derived. Consequently, we achieve the best possible gamma=0 and the following lower bound corollaries under the 3-SUM conjecture: * Approximate distance oracles: The seminal Thorup-Zwick distance oracles achieve stretch 2k +/- O(1) after preprocessing a graph in O(m n(1/k)) time. For the same stretch, and assuming the query time is n(o(1)) Abboud et al. proved an Omega(m(1+1/12.7552 center dot k)) lower bound on the preprocessing time;we improve it to Omega(m(1+1/2k)) which is only a factor 2 away from the upper bound. Additionally, we obtain tight bounds for stretch 2+o(1) and 3-epsilon and higher lower bounds for dynamic shortest paths. * Listing 4-cycles: Abboud et al. proved the first super-linear lower bound for listing all 4-cycles in a graph, ruling out (m(1.1927)+t)(1+o(1)) time algorithms where t is the number of 4-cycles. We settle the complexity of this basic problem by showing that the (min(m(4/3),n(2)) +t) upper bound is tight up to n(o(1)) factors. Our results exploit a rich tool set from additive combinatorics, most notably the Balog-Szemeredi-Gowers theorem and Ruszas covering lemma. A key ingredient that may be of independent interest is a truly subquadratic algorithm for 3-SUM if one of the

关键词： Distance Oracles Fine-Grained Complexity 3SUM additive combinatorics

来源：评论

学校读者我要写书评

暂无评论

Several Problems In Linear Algebraic And additive combinatorics

Several Problems In Linear Algebraic And Additive Combinator...

引用

作者： Daniel Scheinerman Rutgers University

学位级别：博士

This thesis studies three problems in linear algebraic and additive combinatorics. Our first result gives new upper bounds for the determinant of an $nimes n$ zero-one matrix containing $kn$ ones. Our results improve upon a result of Ryser for $k=o(n^{1/3})$. For fixed $kge 3$ it was an open question~cite{bruhn} whether Hadamard's inequality could be exponentially improved. We answer this in the affirmative. Our approach revolves around studying $mimes n$ matrices whose rows sum to $k$ and bounding their Gram determinants. For the class of $nimes n$ matrices whose rows sum to $k$ we show that Ryser's result can be improved for $kle sqrt{n/10}$. Our technique also allows us to give upper bounds when these matrices are perturbed. Our second result concerns a question in additive combinatorics. For a prime $p>2$, we say a nonempty set $Asubseteq F_p$ is emph{unique sum free} (USF) if every element of the sumset $A+A$ can be written as a sum of two elements from $A$ in at least two different ways. That is for any $s in A+A$ there exist $a,b,c,d$ with ${a,b}e{c,d}$ such that $s=a+b=c+d$. If $mu(p)$ is the size of the smallest USF set in $F_p$ it is straightforward to show that $mu(p) = O(sqrt{p}).$ Kopparty~cite{koppartyconference} conjectured that $mu(p)=Theta(sqrt{p})$. However, we show constructively that $mu(p)=O(log^2 p)$. Our third result concerns a graph theoretic problem on the Hamming cube, $Q_n$. For a graph, $G$, we say a proper $k$-coloring of $G$ is a fall $k$-coloring if each vertex is adjacent to a vertex in each of the $k-1$ other color classes. A result of Laskar and Lyle~cite{laskar} shows that for $ke 3$ and $n$ sufficiently large $Q_n$ has a fall $k$-coloring. It is natural to identify the Hamming cube, $Q_n$, with the vector space $F_2^n$. In this context we may seek fall $k$-colorings of $F_2^n$ in which each color class is an affine subspace. Our main result is that for even $k$ and $n$ sufficiently large there exist affine fall $k$-colorings of $F

关键词： additive combinatorics

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal Fault Tolerance for Efficient Batch Matrix Multiplication via an additive combinatorics Lens 31st

Near-Optimal Fault Tolerance for Efficient Batch Matrix Mult...

引用

31st International Colloquium on Structural Information and Communication Complexity (SIROCCO)

作者： Censor-Hillel, Keren Machino, Yuka Soto, Pedro Technion Haifa Israel MIT Cambridge MA USA Univ Oxford Oxford England

ISBN: (纸本)9783031606021;9783031606038

Fault tolerance is a major concern in distributed computational settings. In the classic master-worker setting, a server (the master) needs to perform some heavy computation which it may distribute to m other machines (workers) in order to speed up the time complexity. In this setting, it is crucial that the computation is made robust to failed workers, in order for the master to be able to retrieve the result of the joint computation despite failures. A prime complexity measure is thus the recovery threshold, which is the number of workers that the master needs to wait for in order to derive the output. This is the counterpart to the number of failed workers that it can tolerate. In this paper, we address the fundamental and well-studied task of matrix multiplication. Specifically, our focus is on when the master needs to multiply a batch of n pairs of matrices. Several coding techniques have been proven successful in reducing the recovery threshold for this task, and one approach that is also very efficient in terms of computation time is called Rook Codes. The previously best known recovery threshold for batch matrix multiplication using Rook Codes is O(n(log2 )) = O(n(1.585)). Our main contribution is a lower bound proof that says that any Rook Code for batch matrix multiplication must have a recovery threshold that is at least omega(n). Notably, we employ techniques from additive combinatorics in order to prove this, which may be of further interest. Moreover, we show a Rook Code that achieves a recovery threshold of n(1+o(1)), establishing a near-optimal answer to the fault tolerance of this coding scheme.

关键词： Master-Worker Computation Matrix Multiplication additive combinatorics

来源：评论

学校读者我要写书评

暂无评论

A Walk Through Some Newer Parts of additive combinatorics 1

引用

53rd Southeastern International Conference on combinatorics, Graph Theory, and Computing, SEICCGTC 2022

作者： Bajnok, Béla Department of Mathematics Gettysburg College GettysburgPA United States

In this survey chapter we discuss some recent results and related open questions in additive combinatorics, in particular, questions about sumsets in finite abelian groups. © The Author(s), under exclusive licens... 详细信息

ISBN: (数字)9783031621666

ISBN: (纸本)9783031621659

关键词： additive combinatorics Finite abelian groups Sumsets

来源：评论

学校读者我要写书评

暂无评论

THE UNIFORMITY CONJECTURE IN additive combinatorics

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2021年第1期35卷 307-321页

作者： Shkredov, Ilya Solymosi, Jozsef Steklov Math Inst Div Number Theory Moscow 119991 Russia Univ British Columbia Dept Math Vancouver BC V6T 1Z2 Canada

In this paper we show examples for applications of the Bombieri-Lang conjecture in additive combinatorics, giving bounds on the cardinality of sumsets of squares and higher powers of integers.

关键词： uniformity conjecture additive combinatorics arithmetic progressions incidences

来源：评论

学校读者我要写书评

暂无评论

An additive combinatorics Approach Relating Rank to Communication Complexity

引用

JOURNAL OF THE ACM 2014年第4期61卷 22-22页

作者： Ben-Sasson, Eli Lovett, Shachar Ron-Zewi, Noga Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel Microsoft Res New England Cambridge MA USA Univ Calif San Diego Dept Comp Engn & Sci San Diego CA 92103 USA

Identifying complexity measures that bound the communication complexity of a {0, 1}-valued matrix M is one the most fundamental problems in communication complexity. Mehlhorn and Schmidt [1982] were the first to suggest matrix-rank as one such measure. Among other things, they showed log rank(F)(M) <= CC(M) <= rank(F2) (M), where CC(M) denotes the (deterministic) communication complexity of the function associated with M, and the rank on the left-hand side is over any field F and on the right-hand side it is over the two-element field F-2. For certain matrices M, communication complexity equals the right-hand side, and this completely settles the question of "communication complexity vs. F-2-rank". Here we reopen this question by pointing out that, when M has an additional natural combinatorial property-high discrepancy with respect to distributions which are uniform over submatrices-then communication complexity can be sublinear in F-2-rank. Assuming the Polynomial Freiman-Ruzsa (PFR) conjecture in additive combinatorics, we show that CC(M) <= O(rank(F2) (M)/log rank(F2) (M)) for any matrix M which satisfies this combinatorial property. We also observe that if M has low rank over the reals, then it has low rank over F-2 and it additionally satisfies this combinatorial property. As a corollary, our results also give the first (conditional) sublinear bound on communication complexity in terms of rank over the reals, a result improved later by Lovett [2014]. Our proof is based on the study of the "approximate duality conjecture" which was suggested by Ben-Sasson and Zewi [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 matrices.

关键词： Algorithms Communication complexity log-rank conjecture additive combinatorics polynomial Freiman-Ruzsa conjecture approximate duality low-rank matrices

来源：评论

学校读者我要写书评

暂无评论

Structure theorems in additive combinatorics

引用

RUSSIAN MATHEMATICAL SURVEYS 2015年第1期70卷 113-163页

作者： Shkredov, I. D. Russian Acad Sci VA Steklov Math Inst Moscow 117901 Russia Russian Acad Sci Inst Informat Transmiss Problems Kharkevich Inst Moscow 117901 Russia

Several structure results of additive combinatorics are considered. Classical and modern problems of combinatorial number theory, higher-order Fourier analysis, inverse theorems for Gowers norms, higher energies, and ... 详细信息

关键词： additive combinatorics sets with the small doubling property Gowers norms Fourier analysis

来源：评论

学校读者我要写书评

暂无评论

Non-commutative methods in additive combinatorics and number theory

引用

RUSSIAN MATHEMATICAL SURVEYS 2021年第6期76卷 1065-1122页

作者： Shkredov, I. D. Russian Acad Sci Steklov Math Inst Moscow Russia

The survey is devoted to applications of growth in non- Abelian groups to a number of problems in number theory and additive combinatorics. We discuss Zaremba's conjecture, sum-product theory, incidence geometry, ... 详细信息

关键词： number theory additive combinatorics Zaremba's conjecture growth in groups affine sieve

来源：评论

学校读者我要写书评

暂无评论

SUMSETS IN THE HYPERCUBE

引用

SIAM JOURNAL ON DISCRETE MATHEMATICS 2025年第1期39卷 314-326页

作者： Alon, Noga Zamir, Or Princeton Univ Princeton NJ 08544 USA Tel Aviv Univ Tel Aviv Israel

A subset S of the Boolean hypercube IF2n is a sumset if S = A+ A = {a + b | a, b \in A} for some A C_IF2n. We prove that the number of sumsets in IF2n is asymptotically (2n _ 1)22n- 1. Furthermore, we show that the family of sumsets in IF2n is almost identical to the family of all subsets of IF2n that contain a complete linear subspace of co dimension 1.

关键词： sumsets combinatorics additive combinatorics

来源：评论

学校读者我要写书评

暂无评论

Sumset problem on dilated sets of integers Sumset problem on dilated sets of integers

引用

JOURNAL OF NUMBER THEORY 2025年 269卷 429-439页

作者： Singh, Sandeep Kaur, Ramandeep Verma, Mamta Akal Univ Dept Math Talwandi Sabo 151302 India Dr B R Ambedkar Natl Inst Technol Dept Math Jalandhar 144011 India

Let Abe a non-empty finite set of integers. For integers m and k, let mA +kA = {ma(1)+ka(2) : a(1), a(2) is an element of A}. Form = 2 and an odd prime k such that |A| > 8k(k), Hamidoune et al. [6] proved that |2 A +kA|> (k+2)|A|-k(2)-k+2. Ljujic [7] extended this result and obtained the same bound for k to be a power of an odd prime and product of two distinct odd primes. Balog et al. [1] proved that |pA +q A| > (p +q)|A|-(pq) ((p+q - 3)(p+q)+1 ), where p < q are relatively primes. In this article, for any odd values of k and under some certain conditions on set A, we obtain that |2 A + k A| > (k + 2)|A|- 2k|A|, where A is the projection of Ain Z /k Z . This obtained bound is better than the bound given by Balog et al. We also generalize this bound for |p A + k A|, where pis any odd prime and k be an odd positive integer with (p, k) = 1. (c) 2024 Elsevier Inc. All rights are reserved, including those for text and data mining, AI training, and similar technologies.

关键词： additive combinatorics Sumsets Dilated sumsets

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：