Publication

Variable space search for graph coloring

Publications associées (32)

The Role of Adaptivity in Source Identification with Time Queries

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

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

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

Minimum Cost Intervention Design for Causal Effect Identification

Seyed Jalal Etesami, Negar Kiyavash, Sina Akbari

Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the ...

PMLR2022

Policy-based Exploration of Equilibrium Representations (PEER): A topology grammar for generative conceptual structural design

Ioannis Mirtsopoulos

Design exploration is a creative process that consists of the incremental generation of design candidates. Supported by digital means or not, the process handles the ill-structured nature of design and allows creativity to flourish through diversity of des ...

EPFL2022

Beyond Local Optimality of Buffer and Splitter Insertion for AQFP Circuits

Giovanni De Micheli, Heinz Riener, Siang-Yun Lee

Adiabatic quantum-flux parametron (AQFP) is an energy-efficient superconducting technology. Buffer and splitter (B/S) cells must be inserted to an AQFP circuit to meet the technology-imposed constraints on path balancing and fanout branching. These cells a ...

ACM2022

Sketches, metrics and fast algorithms

Navid Nouri

As it has become easier and cheaper to collect big datasets in the last few decades, designing efficient and low-cost algorithms for these datasets has attracted unprecedented attention. However, in most applications, even storing datasets as acquired has ...

EPFL2022

Differentially Private Multi-Agent Constraint Optimization

Boi Faltings, Aleksei Triastcyn, Sujit Prakash Gujar, Sankarshan Damle

Several optimization scenarios involve multiple agents that desire to protect the privacy of their preferences. There are distributed algorithms for constraint optimization that provide improved privacy protection through secure multiparty computation. How ...

ACM2022

Geometrical Treatise on the Modelling of 3D Particulate Inclusion-Matrix Microstructures with an Application to Historical Stone Masonry Walls

Mahmoud S. M. Shaqfa

As historical stone masonry structures are vulnerable and prone to damage in earthquakes, investigating their structural integrity is important to reduce injuries and casualties while preserving their historical value. Stone masonry is a composite material ...

EPFL2022

Large-scale traffic signal control and multimodal network design

Dimitrios Tsitsokas

Traffic congestion constitutes one of the most frequent, yet challenging, problems to address in the urban space. Caused by the concentration of population, whose mobility needs surpass the serving capacity of urban networks, congestion cannot be resolved ...

EPFL2022

DG-Mix: Domain Generalization for Anomalous Sound Detection Based on Self-Supervised Learning

Ismail Nejjar, Olga Fink, Gaëtan Michel Frusque

Detecting anomalies in sound data has recently received significant attention due to the increasing number of implementations of sound condition monitoring solutions for critical assets. In this context, changing operating conditions impose significant dom ...

2022

Space-Efficient Representations of Graphs

Jakab Tardos

With the increasing prevalence of massive datasets, it becomes important to design algorithmic techniques for dealing with scenarios where the input to be processed does not fit in the memory of a single machine. Many highly successful approaches have emer ...

EPFL2022