惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
J
Java Code Geeks
I
InfoQ
V
Visual Studio Blog
M
MIT News - Artificial intelligence
H
Help Net Security
博客园_首页
Blog — PlanetScale
Blog — PlanetScale
F
Fortinet All Blogs
Apple Machine Learning Research
Apple Machine Learning Research
人人都是产品经理
人人都是产品经理
G
Google Developers Blog
A
About on SuperTechFans
腾讯CDC
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
Last Week in AI
Last Week in AI
小众软件
小众软件
aimingoo的专栏
aimingoo的专栏
罗磊的独立博客
大猫的无限游戏
大猫的无限游戏
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
云风的 BLOG
云风的 BLOG
S
SegmentFault 最新的问题
WordPress大学
WordPress大学

cs.DC updates on arXiv.org

DUAL-BLADE: Dual-Path NVMe-Direct KV-Cache Offloading for Edge LLM Inference Progressive Semantic Communication for Efficient Edge-Cloud Vision-Language Models Efficient, VRAM-Constrained xLM Inference on Clients Folding Tensor and Sequence Parallelism for Memory-Efficient Transformer Training & Inference DORA: A Scalable Asynchronous Reinforcement Learning System for Language Model Training AMMA: A Multi-Chiplet Memory-Centric Architecture for Low-Latency 1M Context Attention Serving RaMP: Runtime-Aware Megakernel Polymorphism for Mixture-of-Experts Spark Policy Toolkit: Semantic Contracts and Scalable Execution for Policy Learning in Spark Internet of Everything in the 6G Era: Paradigms, Enablers, Potentials and Future Directions PolyKV: A Shared Asymmetrically-Compressed KV Cache Pool for Multi-Agent LLM Inference A Survey on Split Learning for LLM Fine-Tuning: Models, Systems, and Privacy Optimizations ITAS: A Multi-Agent Architecture for LLM-Based Intelligent Tutoring Latency and Cost of Multi-Agent Intelligent Tutoring at Scale TACO: Efficient Communication Compression of Intermediate Tensors for Scalable Tensor-Parallel LLM Training FreeScale: Distributed Training for Sequence Recommendation Models with Minimal Scaling Cost CommFuse: Hiding Tail Latency via Communication Decomposition and Fusion for Distributed LLM Training A Taxonomy and Resolution Strategy for Client-Level Disagreements in Federated Learning Usable Agent Discovery for Decentralized AI Systems Cloud to Edge: Benchmarking LLM Inference On Hardware-Accelerated Single-Board Computers Data-Free Contribution Estimation in Federated Learning using Gradient von Neumann Entropy Shard the Gradient, Scale the Model: Serverless Federated Aggregation via Gradient Partitioning Promoting Simple Agents: Ensemble Methods for Event-Log Prediction GraphLeap: Decoupling Graph Construction and Convolution for Vision GNN Acceleration on FPGA AGNT2: Autonomous Agent Economies on Interaction-Optimized Layer 2 Infrastructure FedSIR: Spectral Client Identification and Relabeling for Federated Learning with Noisy Labels Stream-CQSA: Avoiding Out-of-Memory in Attention Computation via Flexible Workload Scheduling A Delta-Aware Orchestration Framework for Scalable Multi-Agent Edge Computing Federated Learning over Blockchain-Enabled Cloud Infrastructure Optimal Routing for Federated Learning over Dynamic Satellite Networks: Tractable or Not? Sherpa.ai Privacy-Preserving Multi-Party Entity Alignment without Intersection Disclosure for Noisy Identifiers
Ultra-Sparse Near-Additive Emulators
Michael Elkin, Shaked Matar · 2021-06-02 · via cs.DC updates on arXiv.org

Near-additive (aka $(1+ε,β)$-) emulators and spanners are a fundamental graph-algorithmic construct, with numerous applications for computing approximate shortest paths and related problems in distributed, streaming and dynamic settings. Known constructions of near-additive emulators enable one to trade between their sparsity (i.e., number of edges) and the additive stretch $β$. Specifically, for any pair of parameters $ε>0$, $ κ=1,2,\dots$, one can have a $(1+ε,β)$-emulator with $O(n^{1+1/κ})$ edges, with $β= \left(\frac{\log κ}ε\right)^{\log κ}$. At their sparsest, these emulators employ $c\cdot n$ edges, for some constant $c\geq 2$. We tighten this bound, and show that in fact precisely $n^{1+1/κ}$ edges suffice. In particular, our emulators can be \emph{ultra-sparse}, i.e., we can have an emulator with $n+o(n)$ edges and $β= \left(\frac{\log {\log n}}{ε}\right)^{\log {\log n}(1+o(1))}$. We also devise a distributed deterministic algorithm in the CONGEST model that builds these emulators in low polynomial time (i.e., in $O(n^ρ)$ time, for an arbitrarily small constant parameter $ρ>0$). Finally, we also improve the state-of-the-art distributed deterministic \congest-model construction of $(1+ε,β)$-spanners devised in the PODC'19 paper [ElkinM19]. Specifically, the spanners of [ElkinM19] have $O(β\cdot n^{1+1/κ})$ edges, i.e., at their sparsest they employ $ O\left(\frac{\log {\log n}}{ε}\right)^{\log {\log n}}\cdot n$ edges. In this paper, we devise an efficient distributed deterministic CONGEST-model algorithm that builds such spanners with $O(n^{1+1/κ})$ edges for $κ= O\left(\frac{\log n}{\log ^{(3)}n}\right)$. At their sparsest, these spanners employ only $O(n\cdot {\log {\log n}})$ edges.