Publications related to The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

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.

Adventures in Monotone Complexity and TFNP

Mika Tapani Göös, Dmitrii Sokolov

Separations: We introduce a monotone variant of Xor-Sat and show it has exponential monotone circuit complexity. Since Xor-Sat is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone ...

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany2018

Delay-Power-Rate-Distortion Optimization of Video Representations for Dynamic Adaptive Streaming

Pascal Frossard, Laura Toni, Chenglin Li

Dynamic adaptive streaming addresses user heterogeneity by providing multiple encoded representations at different rates and/or resolutions for the same video content. For delay-sensitive applications, such as live streaming, there is however a stringent r ...

IEEE2018

Deterministic Algorithms for Submodular Maximization Problems

Moran Feldman

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in almost all c ...

ASSOC COMPUTING MACHINERY2018

Robust Maximization of Non-Submodular Objectives

Volkan Cevher, Ilija Bogunovic, Junyao Zhao

We study the problem of maximizing a monotone set function subject to a cardinality constraint k in the setting where some number of elements is deleted from the returned set. The focus of this work is on the worst-case adversarial setting. While there exi ...

2018

Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach

Volkan Cevher, Ilija Bogunovic, Slobodan Mitrovic, Ashkan Norouzi Fard, Jakub Tarnawski

We study the classical problem of maximizing a monotone submodular function subject to a cardinality constraint k, with two additional twists: (i) elements arrive in a streaming fashion and (ii) m items from the algorithm’s memory might be removed after th ...

2017

Distributed Rate Allocation in Switch-Based Multiparty Videoconferencing System

Pascal Frossard, Sergio Mena, Stefano D'Aronco

Multiparty videoconferences, or more generally multiparty video calls, are gaining a lot of popularity as they offer a rich communication experience. These applications have, however, large requirements in terms of both network and computational resources ...

2017

Approximation algorithms for geometric dispersion

Alfonso Bolívar Cevallos Manzano

The most basic form of the max-sum dispersion problem (MSD) is as follows: given n points in R^q and an integer k, select a set of k points such that the sum of the pairwise distances within the set is maximal. This is a prominent diversity problem, with w ...

EPFL2016

A Composition Theorem for Conical Juntas

Mika Tapani Göös

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two ...

Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH, Wadern/Saarbruecken, Germany2016

The One-Way Communication Complexity of Submodular Maximization with Applications to Streaming and Robustness

Graph Chatbot

Chat with Graph Search

Adventures in Monotone Complexity and TFNP

Delay-Power-Rate-Distortion Optimization of Video Representations for Dynamic Adaptive Streaming

Deterministic Algorithms for Submodular Maximization Problems

Robust Maximization of Non-Submodular Objectives

Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach

Distributed Rate Allocation in Switch-Based Multiparty Videoconferencing System

Approximation algorithms for geometric dispersion

A Composition Theorem for Conical Juntas

Maximizing k-Submodular Functions and Beyond

A Tight Linear Time (1/2)-Approximation For Unconstrained Submodular Maximization

Robust Maximization of Non-Submodular Objectives

Delay-Power-Rate-Distortion Optimization of Video Representations for Dynamic Adaptive Streaming

Adventures in Monotone Complexity and TFNP

Distributed Rate Allocation in Switch-Based Multiparty Videoconferencing System

Deterministic Algorithms for Submodular Maximization Problems

A Composition Theorem for Conical Juntas

Approximation algorithms for geometric dispersion

Streaming Robust Submodular Maximization: A Partitioned Thresholding Approach

A Tight Linear Time (1/2)-Approximation For Unconstrained Submodular Maximization

Maximizing k-Submodular Functions and Beyond