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

推荐订阅源

量子位
博客园 - 三生石上(FineUI控件)
D
DataBreaches.Net
钛媒体:引领未来商业与生活新知
钛媒体:引领未来商业与生活新知
GbyAI
GbyAI
P
Proofpoint News Feed
Microsoft Security Blog
Microsoft Security Blog
月光博客
月光博客
I
InfoQ
V
Visual Studio Blog
罗磊的独立博客
Engineering at Meta
Engineering at Meta
Vercel News
Vercel News
Jina AI
Jina AI
L
LangChain Blog
Apple Machine Learning Research
Apple Machine Learning Research
Cyber Security Advisories - MS-ISAC
Cyber Security Advisories - MS-ISAC
B
Blog
The Cloudflare Blog
小众软件
小众软件
雷峰网
雷峰网
V
V2EX
人人都是产品经理
人人都是产品经理
Stack Overflow Blog
Stack Overflow Blog

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
Mending Partial Solutions with Few Changes
Darya Melnyk, Jukka Suomela, Neven Villani · 2022-09-13 · via cs.DC updates on arXiv.org

In this paper, we study the notion of mending, i.e. given a partial solution to a graph problem, we investigate how much effort is needed to turn it into a proper solution. For example, if we have a partial coloring of a graph, how hard is it to turn it into a proper coloring? In prior work (SIROCCO 2022), this question was formalized and studied from the perspective of mending radius: if there is a hole that we need to patch, how far do we need to modify the solution? In this work, we investigate a complementary notion of mending volume: how many nodes need to be modified to patch a hole? We focus on the case of locally checkable labeling problems (LCLs) in trees, and show that already in this setting there are two infinite hierarchies of problems: for infinitely many values $0 < α\le 1$, there is an LCL problem with mending volume $Θ(n^α)$, and for infinitely many values $k \ge 1$, there is an LCL problem with mending volume $Θ(\log^k n)$. Hence the mendability of LCL problems on trees is a much more fine-grained question than what one would expect based on the mending radius alone. We define three variants of the theme: (1) existential mending volume, i.e., how many nodes need to be modified, (2) expected mending volume, i.e., how many nodes we need to explore to find a patch if we use randomness, and (3) deterministic mending volume, i.e., how many nodes we need to explore if we use a deterministic algorithm. We show that all three notions are distinct from each other, and we analyze the landscape of the complexities of LCL problems for the respective models.