Publication

In Medio Stat Virtus: Combining Boolean and Pattern Matching

Publications associées (38)

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search

Majority-Inverter Graph: A Novel Data-Structure and Algorithms for Efficient Logic Optimization

Giovanni De Micheli, Pierre-Emmanuel Julien Marc Gaillardon, Luca Gaetano Amarù

In this paper, we present Majority-Inverter Graph (MIG), a novel logic representation structure for efficient optimization of Boolean functions. An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented e ...

2014

A Bayesian Method for Matching Two Similar Graphs without Seeds

Matthias Grossglauser, Pedram Pedarsani

Approximate graph matching (AGM) refers to the problem of mapping the vertices of two structurally similar graphs, which has applications in social networks, computer vision, chemistry, and biology. Given its computational cost, AGM has mostly been limited ...

2013

Graph-Constrained Group Testing

Amin Karbasi, Mahdi Cheraghchi Bashi Astaneh, Soheil Mohajerzefreh

Non-adaptive group testing involves grouping arbitrary subsets of

n

items into different pools. Each pool is then tested and defective items are identified. A fundamental question involves minimizing the number of pools required to identify at most

d

d ...

2012

Finite graphs and amenability

Gábor Elek

Hyperfiniteness or amenability of measurable equivalence relations and group actions has been studied for almost fifty years. Recently, unexpected applications of hyperfiniteness were found in computer science in the context of testability of graph propert ...

Academic Press Inc Elsevier Science2012

Space crossing numbers

We define the crossing number for an embedding of a graph G into R^3, and prove a lower bound on it which almost implies the classical crossing lemma. We also give sharp bounds on the space crossing numbers of pseudo-random graphs. ...

2011

A Global Version Of The Darboux Theorem With Optimal Regularity And Dirichlet Condition

Bernard Dacorogna, Olivier Kneuss

Let n > 2 be even; r >= 1 be an integer; 0 < alpha < 1; Omega be a bounded, connected, smooth, open set in R-n; and nu be its exterior unit normal. Let f, g is an element of C-r,C-alpha((Omega) over bar; Lambda(2)) be two symplectic forms (i.e., closed and ...

2011

Complexity of the critical node problem over trees

Marco Di Summa

In this paper we deal with the critical node problem (CNP), i.e., the problem of searching for a given number K of nodes in a graph G, whose removal minimizes the (weighted or unweighted) number of connections between pairs of nodes in the residual graph. ...

2011

Graph-Constrained Group Testing

Amin Karbasi, Mahdi Cheraghchi Bashi Astaneh, Soheil Mohajerzefreh

Non-adaptive group testing involves grouping arbitrary subsets of

n

items into different pools and identifying defective items based on tests obtained for each pool. Motivated by applications in network tomography, sensor networks and infection propagati ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010

A bipartite strengthening of the Crossing Lemma

János Pach

Let G = (V, E) be a graph with n vertices and m >= 4n edges drawn in the plane. The celebrated Crossing Lemma states that G has at least Omega(m(3)/n(2)) pairs of crossing edges; or equivalently, there is an edge that crosses Omega(m(2)/n(2)) other edges. ...

2010

Bio-Inspired Self-Testing and Self-Organizing Processing Arrays

Joël Rossier

Inspired by the basic processes of molecular biology, our previous studies resulted in defining a configurable molecule implementing self-replication and self-repair mechanisms made up of simple processes. The goal of our paper is to add error detection fe ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010

Graph-Constrained Group Testing

Amin Karbasi, Mahdi Cheraghchi Bashi Astaneh, Soheil Mohajerzefreh

Non-adaptive group testing involves grouping arbitrary subsets of

n

items into different pools. Each pool is then tested and defective items are identified. A fundamental question involves minimizing the number of pools required to identify at most

d

d ...

2012

Graph-Constrained Group Testing

Amin Karbasi, Mahdi Cheraghchi Bashi Astaneh, Soheil Mohajerzefreh

Non-adaptive group testing involves grouping arbitrary subsets of

n

items into different pools and identifying defective items based on tests obtained for each pool. Motivated by applications in network tomography, sensor networks and infection propagati ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010