Network Correlated Data Gathering with Explicit Communication: NP-Completeness and Algorithms
Related publications (373)
Graph Chatbot
Chat with Graph Search
Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.
DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.
Understanding epidemic propagation in large networks is an important but challenging task, especially since we usually lack information, and the information that we have is often counter-intuitive. An illustrative example is the dependence of the final siz ...
Network information theory studies the communication of information in a network and considers its fundamental limits. Motivating from the extensive presence of the networks in the daily life, the thesis studies the fundamental limits of particular network ...
We consider high-dimensional random optimization problems where the dynamical variables are subjected to nonconvex excluded volume constraints. We focus on the case in which the cost function is a simple quadratic cost and the excluded volume constraints a ...
Internet ranking algorithms play a crucial role in information technologies and numerical analysis due to their efficiency in high dimensions and wide range of possible applications, including scientometrics and systemic risk in finance (SinkRank, DebtRank ...
We survey lower-bound results in complexity theory that have been obtained via newfound interconnections between propositional proof complexity, boolean circuit complexity, and query/communication complexity. We advocate for the theory of total search prob ...
Despite the high number of investments for data-based models in the expansion of Industry 4.0, too little effort has been made to ensure the maintenance of those models. In a data-streaming environment, data-based models are subject to concept drifts. A co ...
It is known that the agreement property of the Byzantine consensus problem among n processes can be violated in a non-synchronous system if the number of faulty processes exceeds t0 = ┌n/3┐ − 1 [10], [19]. In this paper, we investigate the accountable Byza ...
Knapsack and Subset Sum are fundamental NP-hard problems in combinatorial optimization. Recently there has been a growing interest in understanding the best possible pseudopolynomial running times for these problems with respect to various parameters. In t ...
Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021
Active Debris Removal missions consist of sending a satellite in space and removing one or more debris from their current orbit. A key challenge is to obtain information about the uncooperative target. By gathering the velocity, position, and rotation of t ...
Curie's principle states that "when effects show certain asymmetry, this asymmetry must be found in the causes that gave rise to them." We demonstrate that symmetry equivariant neural networks uphold Curie's principle and can be used to articulate many sym ...