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

56th Annual ACM Symposium on Theory of Computing (STOC)

作者： Ghadiri, Mehrdad Lee, Yin Tat Padmanabhan, Swati Swartworth, William Woodru, David P. Ye, Guanghao MIT Cambridge MA 02139 USA Univ Washington Seattle WA USA Microsoft Res Redmond WA USA Carnegie Mellon Univ Pittsburgh PA USA

ISBN: (纸本)9798400703836

We consider the communication complexity of some fundamental convex optimization problems in the point-to-point (coordinator) and blackboard communication models. We strengthen known bounds for approximately solving linear regression, p -norm regression (for 1 <= p <= 2), linear programming, minimizing the sum of finitely many convex nonsmooth functions with varying supports, and low rank approximation;for a number of these fundamental problems our bounds are optimal, as proven by our lower bounds. For example, for solving least squares regression in the coordinator model with B servers, n examples, d dimensions, and coefficients specified using at most L bits, we improve the prior communication bound of Vempala, Wang, and Woodruff (SODA, 2020) from (O) over tilde (sd(2)L) to (O) over tilde (sdL + d(2)epsilon L-1), which is optimal up to logarithmic factors. We also study the problem of solving least squares regression in the coordinator model to high accuracy, for which we provide an algorithm with a communication complexity of (O) over tilde (sd(L + log k) log (epsilon(-1)) + d(2)L), matching our improved lower bound for well-conditioned matrices up to a log (epsilon(-1)) factor. Among our techniques, we use the notion of block leverage scores, which have been relatively unexplored in this context, as well as dropping all but the "middle" bits in Richardson-style algorithms. We also introduce a new communication problem for accurately approximating inner products and establish a lower bound using the spherical Radon transform. Our lower bound can be used to show the first separation of linear programming and linear systems in the distributed model when the number of constraints is polynomial, addressing an open question in prior work.

关键词： bit complexity communication complexity distributed optimization convex optimization

来源：评论

学校读者我要写书评

暂无评论

bit complexity of computing solutions for symmetric hyperbolic systems of PDEs with guaranteed precision

引用

COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE 2021年第2期10卷 123-140页

作者： Selivanova, Svetlana Selivanov, Victor Korea Adv Inst Sci & Technol Sch Comp 291 Daehak Ro Daejeon 34141 South Korea AP Ershov Inst Informat Syst SB RAS Theoret Programming Lab 6 Acad Lavrentjev Pr Novosibirsk 630090 Russia

We establish upper bounds on bit complexity of computing solution operators for symmetric hyperbolic systems of PDEs, combining symbolic and approximate algorithms to obtain the solutions with guaranteed prescribed pr... 详细信息

关键词： Symmetric hyperbolic system bit complexity solution operator guaranteed precision symbolic computations algebraic real approximation symmetric matrix spectral decomposition difference scheme

来源：评论

学校读者我要写书评

暂无评论

Multilinear polynomial systems: Root isolation and bit complexity

引用

JOURNAL OF SYMBOLIC COMPUTATION 2021年 105卷 145-164页

作者： Emiris, Ioannis Z. Mantzaflaris, Angelos Tsigaridas, Elias P. Natl & Kapodistrian Univ Athens Athens Greece ATHENA Res & Innovat Ctr Maroussi Greece Univ Cote dAzur Inria Sophia Antipolis Mediterranee Nice France Sorbonne Univ CNRS INRIA Equipe PolSysLab Informat Paris 6LIP6 4 Pl Jussieu F-75005 Paris France

We exploit structure in polynomial system solving by considering polynomials that are linear in subsets of the variables. We focus on algorithms and their Boolean complexity for computing isolating hyperboxes for all the isolated complex roots of well-constrained, unmixed systems of multilinear polynomials based on resultant methods. We enumerate all expressions of the multihomogeneous (or multigraded) resultant of such systems as a determinant of Sylvester-like matrices, aka generalized Sylvester matrices. We construct these matrices by means of Weyman homological complexes, which generalize the Cayley-Koszul complex. The computation of the determinant of the resultant matrix is the bottleneck for the overall complexity. We exploit the quasi-Toeplitz structure to reduce the problem to efficient matrix-vector multiplication, which corresponds to multivariate polynomial multiplication, by extending the seminal work on Macaulay matrices of Canny, Kaltofen, and Yagati Canny et al. (1989) to the multihomogeneous case. We compute a rational univariate representation of the roots, based on the primitive element method. In the case of 0-dimensional systems we present a Monte Carlo algorithm with probabil- ity of success 1 - 1/2(rho), for a given rho >= 1, and bit complexity (O) over tilde (B) (n(2)D(4+epsilon)(n(N+1) + tau) + nD(2+epsilon) rho(D + rho)) for any epsilon > 0, where n is the number of variables, D equals the multilinear Bezout bound, N is the number of variable subsets, and tau is the maximum coefficient bitsize. We present an algorithmic variant to compute the isolated roots of overdetermined and positive-dimensional systems. Thus our algorithms and complexity analysis apply in general with no assumptions on the input. (C) 2020 Published by Elsevier Ltd.

关键词： Multilinear polynomial DMM separation bound Resultant matrix Cayley-Koszul complex Primitive element Rational univariate representation bit complexity

来源：评论

学校读者我要写书评

暂无评论

On the bit complexity of polynomial system solving

引用

JOURNAL OF complexity 2019年第Apr.期51卷 20-67页

作者： Gimenez, Nardo Matera, Guillermo Univ Nacl Gen Sarmiento Inst Desarrollo Humano JM Gutierrez 1150 B1613GSX Los Polvorines Buenos Aires Argentina Consejo Nacl Invest Cient & Tecn Natl Council Sci & Technol Buenos Aires DF Argentina

We describe and analyze a randomized algorithm which solves a polynomial system over the rationals defined by a reduced regular sequence outside a given hypersurface. We show that its bit complexity is roughly quadratic in the Bezout number of the system and linear in its bit size. The algorithm solves the input system modulo a prime number p and applies p-adic lifting. For this purpose, we establish a number of results on the bit length of a "lucky" prime p. namely one for which the reduction of the input system modulo p preserves certain fundamental geometric and algebraic properties of the original system. These results rely on the analysis of Chow forms associated to the set of solutions of the input system and effective arithmetic Nullstellensatze. (C) 2018 Elsevier Inc. All rights reserved.

关键词： Polynomial system solving over Q bit complexity Reduced regular sequence Chow form Lifting fibers Lucky primes

来源：评论

学校读者我要写书评

暂无评论

Maximum Entropy Distributions: bit complexity and Stability 32

Maximum Entropy Distributions: Bit Complexity and Stability

引用

32nd Conference on Learning Theory (COLT) part of the ACM Federated Computing Research Conference

作者： Straszak, Damian Vishnoi, Nisheeth K. Aleph Zero Fdn Zug Switzerland Yale Univ New Haven CT 06520 USA

Maximum entropy distributions with discrete support in m dimensions arise in machine learning, statistics, information theory, and theoretical computer science. While structural and computational properties of max-entropy distributions have been extensively studied, basic questions such as: Do max-entropy distributions over a large support (e.g., 2(m)) with a specified marginal vector have succinct descriptions (polynomial-size in the input description)? and: Are entropy maximizing distributions "stable" under the perturbation of the marginal vector? have resisted a rigorous resolution. Here we show that these questions are related and resolve both of them. Our main result shows a poly(m, log 1/epsilon) bound on the bit complexity of epsilon-optimal dual solutions to the maximum entropy convex program - for very general support sets and with no restriction on the marginal vector. Applications of this result include polynomial time algorithms to compute max-entropy distributions over several new and old polytopes for any marginal vector in a unified manner, a polynomial time algorithm to compute the Brascamp-Lieb constant in the rank-1 case. The proof of this result allows us to show that changing the marginal vector by delta changes the max-entropy distribution in the total variation distance roughly by a factor of poly(m, log 1/delta)root delta - even when the size of the support set is exponential. Together, our results put max-entropy distributions on a mathematically sound footing - these distributions are robust and computationally feasible models for data.

关键词： Maximum entropy distributions bit complexity Stability Convex optimization

来源：评论

学校读者我要写书评

暂无评论

SUM OF SQUARES DECOMPOSITIONS OF POLYNOMIALS OVER THEIR GRADIENT IDEALS WITH RATIONAL COEFFICIENTS

引用

SIAM JOURNAL ON OPTIMIZATION 2023年第1期33卷 63-88页

作者： Magron, Victor El Din, Mohab Safey Vu, Trung-Hieu Lab Anal & Architecture Syst LAAS Toulouse France Sorbonne Univ LIP6 Paris France

Assessing nonnegativity of multivariate polynomials over the reals, through the computation of certificates of nonnegativity, is a topical issue in polynomial optimization. This is usually tackled through the computation of sum of squares decompositions which rely on efficient numerical solvers for semidefinite programming. This method faces two difficulties. The first one is that the certificates obtained this way are approximate and then nonexact. The second one is due to the fact that not all nonnegative polynomials are sums of squares. In this paper, we build on previous works by Parrilo and Nie, Demmel, and Sturmfels who introduced certificates of nonnegativity modulo gradient ideals. We prove that, actually, such certificates can be obtained exactly over the rationals if the polynomial under consideration has rational coefficients, and we provide exact algorithms to compute them. We analyze the bit complexity of these algorithms and deduce bitsize bounds of such certificates.

关键词： nonnegative polynomials sum of squares decomposition gradient ideal zero-dimensional and radical ideal Grobner basis bit complexity

来源：评论

学校读者我要写书评

暂无评论

Polynomial modular product verification and its implications

引用

JOURNAL OF SYMBOLIC COMPUTATION 2023年 116卷 98-129页

作者： Giorgi, Pascal Grenet, Bruno du Cray, Armelle Perret Univ Montpellier LIRMM CNRS Montpellier France

Polynomial multiplication is known to have quasi-linear complexity in both the dense and the sparse cases. Yet no truly linear algorithm has been given in any case for the problem, and it is not clear whether it is even possible. This leaves room for a better algorithm for the simpler problem of verifying a polynomial product. While finding deterministic methods seems out of reach, there exist probabilistic algorithms for the problem that are optimal in number of algebraic operations. We study the generalization of the problem to the verification of a polynomial product modulo a sparse divisor. We investigate its bit complexity for both dense and sparse multiplicands. In particular, we are able to show the primacy of the verification over modular multiplication when the divisor has a constant sparsity and a second highest-degree monomial that is not too large. We use these results to obtain new bounds on the bit complexity of the standard polynomial multiplication verification. In particular, we provide optimal algorithms in the bit complexity model in the dense case by improving a result of Kaminski and develop the first quasi-optimal algorithm for verifying sparse polynomial product. (C) 2022 Published by Elsevier Ltd.

关键词： Polynomial multiplication Modular multiplication Verification algorithm Dense and sparse polynomials bit complexity

来源：评论

学校读者我要写书评

暂无评论

PTOPO: Computing the geometry and the topology of parametric curves

引用

Journal of Symbolic Computation 2023年 115卷 427-451页

作者： Katsamaki, Christina Rouillier, Fabrice Tsigaridas, Elias Zafeirakopoulos, Zafeirakis Inria Paris IMJ-PRG Sorbonne Université Paris Université France Institute of Information Technologies Gebze Technical University Turkey

We consider the problem of computing the topology and describing the geometry of a parametric curve in Rn. We present an algorithm, PTOPO, that constructs an abstract graph that is isotopic to the curve in the embeddi... 详细信息

We consider the problem of computing the topology and describing the geometry of a parametric curve in Rⁿ. We present an algorithm, PTOPO, that constructs an abstract graph that is isotopic to the curve in the embedding space. Our method exploits the benefits of the parametric representation and does not resort to implicitization. Most importantly, we perform all computations in the parameter space and not in the implicit space. When the parametrization involves polynomials of degree at most d and maximum bitsize of coefficients τ, then the worst case bit complexity of PTOPO is O˜_B(nd⁶+nd⁵τ+d⁴(n²+nτ)+d³(n²τ+n³)+n³d²τ). This bound matches the current record bound O˜_B(d⁶+d⁵τ) for the problem of computing the topology of a plane algebraic curve given in implicit form. For plane and space curves, if N=max⁡{d,τ}, the complexity of PTOPO becomes O˜_B(N⁶), which improves the state-of-the-art result, due to Alcázar and Díaz-Toca [CAGD'10], by a factor of N¹⁰. In the same time complexity, we obtain a graph whose straight-line embedding is isotopic to the curve. However, visualizing the curve on top of the abstract graph construction, increases the bound to O˜_B(N⁷). For curves of general dimension, we can also distinguish between ordinary and non-ordinary real singularities and determine their multiplicities in the same expected complexity of PTOPO by employing the algorithm of Blasco and Pérez-Díaz [CAGD'19]. We have implemented PTOPO in MAPLE for the case of plane and space curves. Our experiments illustrate its practical nature. © 2022 Elsevier Ltd

关键词： bit complexity Parametric curve Polynomial systems Topology

来源：评论

学校读者我要写书评

暂无评论

Every bit Counts in Consensus 37

Every Bit Counts in Consensus

引用

37th International Symposium on Distributed Computing, DISC 2023

作者： Civit, Pierre Gilbert, Seth Guerraoui, Rachid Komatovic, Jovan Monti, Matteo Vidigueira, Manuel Sorbonne University Paris France National University of Singapore Singapore Switzerland

ISBN: (纸本)9783959773010

Consensus enables n processes to agree on a common valid L-bit value, despite t 2). However, the worst-case bit complexity of the best solution is still O(n2L + n2κ) (where κ is the security parameter), far from the Ω(nL + n2) lower bound. The gap is significant given the practical use of consensus primitives, where values typically consist of batches of large size (L > n). This paper shows how to narrow the aforementioned gap. Namely, we present a new algorithm, DARE (Disperse, Agree, REtrieve), that improves upon the O(n2L) term via a novel dispersal primitive. DARE achieves O(n1.5L + n2.5κ) bit complexity, an effective √n-factor improvement over the state-of-the-art (when L > nκ). Moreover, we show that employing heavier cryptographic primitives, namely STARK proofs, allows us to devise DARE-Stark, a version of DARE which achieves the near-optimal bit complexity of O(nL + n2poly(κ)). Both DARE and DARE-Stark achieve optimal O(n) worst-case latency. © Pierre Civit, Seth Gilbert, Rachid Guerraoui, Jovan Komatovic, Matteo Monti, and Manuel Vidigueira;licensed under Creative Commons License CC-BY 4.0.

关键词： bit complexity Byzantine consensus Latency

来源：评论

学校读者我要写书评

暂无评论

A Recursive Early-Stopping Phase King Protocol 22

A Recursive Early-Stopping Phase King Protocol

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Lenzen, Christoph Sheikholeslami, Sahar CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany Ferdowsi Univ Mashhad Mashhad Iran

ISBN: (纸本)9781450392624

Early-stopping consensus protocols guarantee termination within a number of rounds that depends only on the actual number f of faulty nodes in a run, not the maximum number of faults that can be tolerated. We consider early-stopping deterministic synchronous consensus with Byzantine faults in a fully connected message passing system of n nodes. Many such protocols are known, but so far none combine early-stopping in O(f + 1) rounds with optimal resilience and a bit complexity of o(n(2)(f + 1)). We provide two solutions to the above problem. The first is fairly simple and almost matches the above goals, but has worst-case message and bit complexities of Theta(n(2) log (f + 2)). The second reduces the bit complexity further to O(n(2)) by calling itself recursively at most twice on Theta(n)-sized subsets. The result is the first protocol that is simultenously optimally resilient, asymptotically optimally early-stopping, and asymptotically bit- and message-optimal.

关键词： consensus Byzantine faults bit complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：