Publication

2D-TUCKER Is PPAD-Complete

Publications associées (31)

Effect of window glazing color and transmittance on human visual comfort

Marilyne Andersen, Jan Wienold, Sneha Jain

: Occupants’ visual comfort in an indoor space strongly depend on the quantity and quality of the daylight inside the space which can be altered with the type of window glazing. In this study, we compared the visual comfort perception of participants with ...

2022

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

A PCP Theorem for Interactive Proofs and Applications

Alessandro Chiesa

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Versatile Electroluminescence Color-Tuning Strategy of an Efficient Light-Emitting Electrochemical Cell (LEC) by an Ionic Additive

Mohammad Khaja Nazeeruddin, Narges Yaghoobi Nia

The color-tuning strategies of solid-state light-emitting devices (ss-LEDs) are mainly focused on engineering molecular structures. In this paper, for the first time, we developed a facile strategy for tuning the electroluminescence (EL) color from orange ...

AMER CHEMICAL 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

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

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

Adaptive majority problems for restricted query graphs and for weighted sets

Doemoetoer Palvoelgyi, Balázs Keszegh, Abhishek Methuku

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...

ELSEVIER2021

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Lars Rohwedder

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. ...

ASSOC COMPUTING MACHINERY2021

Faster Monotone Min-Plus Product, Range Mode, and Single Source Replacement Paths

Adam Teodor Polak

One of the most basic graph problems, All-Pairs Shortest Paths (APSP) is known to be solvable in n^{3-o(1)} time, and it is widely open whether it has an O(n^{3-ε}) time algorithm for ε > 0. To better understand APSP, one often strives to obtain subcubic t ...

Schloss Dagstuhl -- Leibniz-Zentrum für Informatik2021

Sublinear Algorithms for Spectral Graph Clustering

Aidasadat Mousavifar

This thesis focuses on designing spectral tools for graph clustering in sublinear time. With the emergence of big data, many traditional polynomial time, and even linear time algorithms have become prohibitively expensive. Processing modern datasets requir ...

EPFL2021