Publication

How to Safely Close a Discussion

Publications associées (32)

Proofs, Circuits, and Communication

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 ...

2022

Unambiguous DNFs and Alon-Saks-Seymour

Mika Tapani Göös, Siddhartha Jain

We exhibit an unambiguous k-DNF formula that requires CNF width (Omega) over tilde (k(2)), which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon-Saks-Seymour problem in graph theory (posed in 1991), which ...

IEEE COMPUTER SOC2022

Data-driven and Safe Networked Control with Applications to Microgrids

Mustafa Sahin Turan

Today, automatic control is integrated into a wide spectrum of real-world systems such as electrical grids and transportation networks. Many of these systems comprise numerous interconnected agents, perform safety-critical operations, or generate large amo ...

EPFL2022

Discrete Optimal Transport with Independent Marginals is #P-Hard

Daniel Kuhn, Soroosh Shafieezadeh Abadeh, Bahar Taskesen

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

2023

fGOT: Graph Distances Based on Filters and Optimal Transport

Pascal Frossard, Giovanni Chierchia, Hermina Petric Maretic, Mireille El Gheche

Graph comparison deals with identifying similarities and dissimilarities between graphs. A major obstacle is the unknown alignment of graphs, as well as the lack of accurate and inexpensive comparison metrics. In this work we introduce the filter graph dis ...

ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE2022

Lower Bounds for Unambiguous Automata via Communication Complexity

Mika Tapani Göös, Weiqiang Yuan

We use results from communication complexity, both new and old ones, to prove lower bounds for unambiguous finite automata (UFAs). We show three results. 1) Complement: There is a language L recognised by an n-state UFA such that the complement language ̅L ...

Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022

Scalable Multi-agent Coordination and Resource Sharing

Panayiotis Danassis

A plethora of real world problems consist of a number of agents that interact, learn, cooperate, coordinate, and compete with others in ever more complex environments. Examples include autonomous vehicles, robotic agents, intelligent infrastructure, IoT de ...

EPFL2022

Quantization for Distributed Processing and Learning of Structured Data

Isabela Cunha Maia Nobre

In the domains of machine learning, data science and signal processing, graph or network data, is becoming increasingly popular. It represents a large portion of the data in computer, transportation systems, energy networks, social, biological, and other s ...

EPFL2022

Memory of Motion for Initializing Optimization in Robotics

Teguh Santoso Lembono

Many robotics problems are formulated as optimization problems. However, most optimization solvers in robotics are locally optimal and the performance depends a lot on the initial guess. For challenging problems, the solver will often get stuck at poor loc ...

EPFL2022

The double exponential runtime is tight for 2-stage stochastic ILPs

Kim-Manuel Klein, Klaus Jansen, Alexandra Anna Lassota

We consider fundamental algorithmic number theoretic problems and their relation to a class of block structured Integer Linear Programs (ILPs) called 2-stage stochastic. A 2-stage stochastic ILP is an integer program of the form min{c(T)x vertical bar Ax = ...

SPRINGER HEIDELBERG2022

Streaming and Matching Problems with Submodular Functions

Paritosh Garg

Submodular functions are a widely studied topic in theoretical computer science. They have found several applications both theoretical and practical in the fields of economics, combinatorial optimization and machine learning. More recently, there have also ...

EPFL2022

Tight Vector Bin Packing with Few Small Items via Fast Exact Matching in Multigraphs

Adam Teodor Polak, Alexandra Anna Lassota

We solve the Bin Packing problem in O^*(2^k) time, where k is the number of items less or equal to one third of the bin capacity. This parameter measures the distance from the polynomially solvable case of only large (i.e., greater than one third) items. O ...

Schloss Dagstuhl – Leibniz-Zentrum fur Informatik2022

Publications associées (32)