Generalized Hypertree Decompositions: NP-hardness and Tractable Variants

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.

We discuss two extensions to a recently introduced theory of arrays, which are based on considerations coming from the model theory of power structures. First, we discuss how the ordering relation on the index set can be expressed succinctly by referring t ...

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

Given a sequence of functions

f_1,\ldots,f_n

with

f_i:\mathcal{D}\mapsto \mathbb{R}

, finite-sum minimization seeks a point

{x}^\star \in \mathcal{D}

minimizing

\sum_{j=1}^nf_j(x)/n

. In this work, we propose a key twist into the finite-sum minimizat ...

We study the proof theory and algorithms for orthologic, a logical system based on ortholattices, which have shown practical relevance in simplification and normalization of verification conditions. Ortholattices weaken Boolean algebras while having polyno ...

Diffusion-based generative methods have proven effective in modeling trajectories with offline datasets. However, they often face computational challenges and can falter in generalization, especially in capturing temporal abstractions for long- horizon tas ...

Conventional techniques for purifying macromolecular conjugates often require complex and costly installments that are inaccessible to most laboratories. In this work, we develop a one-step micropreparative method based on a trilayered polyacrylamide gel e ...

In this paper, we propose a reduced-order modeling strategy for two-way Dirichlet-Neumann parametric coupled problems solved with domain-decomposition (DD) sub-structuring methods. We split the original coupled differential problem into two sub-problems wi ...

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

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...

An integer linear program is a problem of the form max{c^T x : Ax=b, x >= 0, x integer}, where A is in Z^(n x m), b in Z^m, and c in Z^n. Solving an integer linear program is NP-hard in general, but there are several assumptions for which it becomes fixed ...

Witness encryption is a cryptographic primitive which encrypts a message under an instance of an NP language and decrypts the ciphertext using a witness associated with that instance. In the current state of the art, most of the witness encryption construc ...

Time-sensitive networks, as in the context of IEEE Time-Sensitive Networking (TSN) and IETF Deterministic Networking (DetNet), offer deterministic services with guaranteed bounded latency in order to support safety-critical applications. In this thesis, we ...

Reducing the computational time required by high-fidelity, full-order models (FOMs) for the solution of problems in cardiac mechanics is crucial to allow the translation of patient-specific simulations into clinical practice. Indeed, while FOMs, such as th ...

We introduce contextual stochastic bilevel optimization (CSBO) -- a stochastic bilevel optimization framework with the lower-level problem minimizing an expectation conditioned on some contextual information and the upper-level decision variable. This fram ...

Control design for robotic systems is complex and often requires solving an optimization to follow a trajectory accurately. Online optimization approaches like Model Predictive Control (MPC) have been shown to achieve great tracking performance, but requir ...

Maximal subgraph mining is increasingly important in various domains, including bioinformatics, genomics, and chemistry, as it helps identify common characteristics among a set of graphs and enables their classification into different categories. Existing ...

We revisit the problem max-min degree arborescence, which was introduced by Bateni et al. [STOC'09] as a central special case of the general Santa Claus problem, which constitutes a notorious open question in approximation algorithms. In the former problem ...

We propose an image-based elastography method to measure the heterogeneous stiffness inside a cell and its nucleus. It uses a widely accessible setup consisting of plate compression imaged with fluorescence microscopy. Our framework recovers a spatial map ...

We present a robust model predictive control (MPC) framework for linear systems facing bounded parametric uncertainty and bounded disturbances. Our approach deviates from standard MPC formulations by integrating multi-step predictors, which provide reduced ...

Generalized Hypertree Decompositions: NP-hardness and Tractable Variants

Chat with Graph Search

Succinct ordering and aggregation constraints in algebraic array theories

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Efficient Continual Finite-Sum Minimization

Orthologic with Axioms

SIMPLE HIERARCHICAL PLANNING WITH DIFFUSION

Micropreparative Gel Electrophoresis for Purification of Nanoscale Bioconjugates

A Reduced Order Model for Domain Decompositions with Non-conforming Interfaces

Discrete Optimal Transport with Independent Marginals is #P-Hard

Approximation Algorithms for Allocation and Network Design

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Results on Sparse Integer Programming and Geometric Independent Sets

Extractable Witness Encryption for the Homogeneous Linear Equations Problem

Worst-Case Delay Analysis of Time-Sensitive Networks with Network Calculus

Efficient approximation of cardiac mechanics through reduced-order modeling with deep learning-based operator approximation

Contextual Stochastic Bilevel Optimization

Training Efficient Controllers via Analytic Policy Gradient

Scalable maximal subgraph mining with backbone-preserving graph convolutions

Better Trees for Santa Claus

PROBING INTRACELLULAR ELASTICITY WITH MINIMAL-HESSIAN REGISTRATION

Homothetic Tube Model Predictive Control With Multi-Step Predictors