Publications associées à The Holt-Klee condition for oriented matroids

The connection of the acyclic disconnection and feedback arc sets - On an open problem of Figueroa et al

We examine the connection of two graph parameters, the size of a minimum feedback arcs set and the acyclic disconnection. A feedback arc set of a directed graph is a subset of arcs such that after deletion the graph becomes acyclic. The acyclic disconnecti ...

Elsevier2024

Spatial Modeling for Building Design Evaluation: from Visual Landscape Quality Assessment to Devaluation Risk Estimation

Adam Robert Swietek

Zoning reform is a crucial tool for cities to adapt to contemporary challenges. However, its implementation remains challenging. Property owners, with a vested interest in the value of their neighborhoods, are sensitive to local developments and the potent ...

EPFL2024

Better Trees for Santa Claus

Etienne Michel François Bamas, Lars Rohwedder

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

Assoc Computing Machinery2023

Bias Cancellation of MixColumns

Francesco Regazzoni, Andrea Felice Caforio, Subhadeep Banik

At COSADE'2020, Carre et al. established a novel biascancelling property of the AES MixColumns matrix that effectively corrects any skewed output distribution of a state byte due to a faulty substitution box. Consequently, any effected byte is rendered uni ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Motif Cut Sparsifiers

Mikhail Kapralov, Jakab Tardos, Mikhail Makarov

A motif is a frequently occurring subgraph of a given directed or undirected graph G (Milo et al.). Motifs capture higher order organizational structure of G beyond edge relationships, and, therefore, have found wide applications such as in graph clusterin ...

IEEE COMPUTER SOC2022

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

A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models

Saber Salehkaleybar, Negar Kiyavash, Ehsan Mokhtarian

We study experiment design for unique identification of the causal graph of a system where the graph may contain cycles. The presence of cycles in the structure introduces major challenges for experiment design as, unlike acyclic graphs, learning the skele ...

2023

Collapse-invariant properties of spaces equipped with signals or directions

Stefania Ebli

Collapsing cell complexes was first introduced in the 1930's as a way to deform a space into a topological-equivalent subspace with a sequence of elementary moves. Recently, discrete Morse theory techniques provided an efficient way to construct deformatio ...

EPFL2022

Toward Mobile Distributed Ledgers

Boi Faltings, Sujit Prakash Gujar, Dimitrios Chatzopoulos, Anurag Jain

Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on Device-to-Device (D2D) ecosystems (e.g., crowdsensing). Sophisticated applications, like cryptocurrencies, need distr ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Selective attention involves a feature-specific sequential release from inhibitory gating

Gijs Plomp, David Pascucci

Selective attention is a fundamental cognitive mechanism that allows our brain to preferentially process relevant sensory information, while filtering out distracting information. Attention is thought to flexibly gate the communication of irrelevant inform ...

2022

Estimating an extreme Bayesian network via scalings

Mario Krali

A recursive max-linear vector models causal dependence between its components by expressing each node variable as a max-linear function of its parental nodes in a directed acyclic graph and some exogenous innovation. Motivated by extreme value theory, inno ...

ELSEVIER INC2021

Representation Learning for Multi-relational Data

Eda Bayram

Recent years have witnessed a rise in real-world data captured with rich structural information that can be better depicted by multi-relational or heterogeneous graphs. However, research on relational representation learning has so far mostly focused on th ...

EPFL2021

A minimalistic cyclic ice-binding peptide from phage display

Harm-Anton Klok, Matthew Gibson, Luciano Andres Abriata, Xudong Kong, Corey Alfred Stevens

Developing molecules that emulate the properties of naturally occurring ice-binding proteins (IBPs) is a daunting challenge. Rather than relying on the (limited) existing structure–property relationships that have been established for IBPs, here we report ...

Nature Research2021

Property FW, differentiable structures and smoothability of singular actions

Yash Lodha, Nicolas Matte Bon

We provide a smoothening criterion for group actions on manifolds by singular diffeomorphisms. We prove that if a countable group Gamma has the fixed point property FW for walls (for example, if it has property(T)), every aperiodic action of Gamma by diffe ...

WILEY2020

A Politics of Intellectual Property: Creating a Patent System in Revolutionary France

Jérôme Baudry

Economic interpretations, in particular the lens of the Industrial Revolution, have strongly influenced our understanding of the rise of intellectual property. This article examines the political origins of the 1791 patent law in France, which is usually s ...

2020

Mneme: A Mobile Distributed Ledger

Boi Faltings, Sujit Prakash Gujar, Dimitrios Chatzopoulos

Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (e.g., crowdsensing). More sophisticated applications, like cryptocurrencies, need ...

IEEE2020

Géohistoire de l'Albanie moderne. Une lecture des recensements de 1918 à 2011

Alain Nicolas Jarne

In this thesis, an original database is constituted, described and exploited in a geohistorical perspective, containing the registration of the population at the local level for the fifteen censuses conducted in Albania between 1918 and 2011. The precision ...

EPFL2020

Entropic Matroids and Their Representation

Emmanuel Abbé

This paper investigates entropic matroids, that is, matroids whose rank function is given as the Shannon entropy of random variables. In particular, we consider p-entropic matroids, for which the random variables each have support of cardinality p. We draw ...

2019

New Notions and Constructions of Sparsification for Graphs and Hypergraphs

Ola Nils Anders Svensson

A sparsifier of a graph G (Bencztir and Karger; Spielman and Teng) is a sparse weighted subgraph (G) over tilde that approximately retains the same cut structure of G. For general graphs, non-trivial sparsification is possible only by using weighted graphs ...

IEEE COMPUTER SOC2019

An Improved Analysis of Local Search for Max-Sum Diversification

Rico Zenklusen, Friedrich Eisenbrand, Alfonso Bolívar Cevallos Manzano

We present new techniques to analyze natural local search algorithms for several variants of the max-sum diversification problem which, in its most basic form, is as follows: given an n-point set X subset of R-d and an integer k, select k points in X so th ...

INFORMS2019