The Holt-Klee condition for oriented matroids

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

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

Various forms of real-world data, such as social, financial, and biological networks, can be represented using graphs. An efficient method of analysing this type of data is to extract subgraph patterns, such as cliques, cycles, and motifs, from graphs. For ...

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

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

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

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

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

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

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

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

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

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

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

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

This paper is devoted to the distributed complexity of finding an approximation of the maximum cut (MAXCUT) in graphs. A classical algorithm consists in letting each vertex choose its side of the cut uniformly at random. This does not require any communica ...

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

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

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

Deterministic protocols are well-known tools to obtain extended formulations, with many applications to polytopes arising in combinatorial optimization. Although constructive, those tools are not output-efficient, since the time needed to produce the exten ...

The Holt-Klee condition for oriented matroids

Chat with Graph Search

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

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

Acceleration of graph pattern mining and applications to financial crime

Better Trees for Santa Claus

Bias Cancellation of MixColumns

Motif Cut Sparsifiers

Unambiguous DNFs and Alon-Saks-Seymour

Streaming and Matching Problems with Submodular Functions

A Unified Experiment Design Approach for Cyclic and Acyclic Causal Models

Toward Mobile Distributed Ledgers

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

Collapse-invariant properties of spaces equipped with signals or directions

Estimating an extreme Bayesian network via scalings

Representation Learning for Multi-relational Data

A minimalistic cyclic ice-binding peptide from phage display

Local approximation of the Maximum Cut in regular graphs

Property FW, differentiable structures and smoothability of singular actions

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

Mneme: A Mobile Distributed Ledger

Extended Formulations from Communication Protocols in Output-Efficient Time