Théorie de la démonstration | EPFL Graph Search

La théorie de la démonstration, aussi connue sous le nom de théorie de la preuve (de l'anglais proof theory), est une branche de la logique mathématique. Elle a été fondée par David Hilbert au début du . Hilbert a proposé cette nouvelle discipline mathématique lors de son célèbre exposé au congrès international des mathématiciens en 1900 avec pour objectif de démontrer la cohérence des mathématiques. Cet objectif a été invalidé par le non moins célèbre théorème d'incomplétude de Gödel en 1931, ce qui n'a toutefois pas empêché la théorie de la démonstration de se développer, notamment grâce aux travaux de Jacques Herbrand et de Gerhard Gentzen. Ce dernier a démontré l'un des résultats principaux de la théorie de la démonstration, connu sous le nom de Hauptsatz (théorème principal) ou théorème d'élimination des coupures. Gentzen a ensuite utilisé ce théorème pour donner la première démonstration purement syntaxique de la cohérence de l'arithmétique. Après une période de calme, qui

NP Satisfiability for Arrays as Powers

Viktor Kuncak, Rodrigo Raya

We show that the satisfiability problem for the quantifier-free theory of product structures with the equicardinality relation is inNP. As an application, we extend the combinatory array logic fragmentto handle cardinality constraints. The resulting fragment is independentof the base element and index set theories.

Springer, Cham2022

Simple topological graphs

Andres Jacinto Ruiz Vargas

This thesis is devoted to the understanding of topological graphs. We consider the following four problems: 1. A \emph{simple topological graph} is a graph drawn in the plane so that its edges are represented by continuous arcs with the property that any two of them meet at most once, at endpoint or at a crossing. Let

G

be a complete simple topological graph on

n

vertices. The three edges induced by any triplet of vertices in

G

form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an \emph{empty triangle}. In 1998, Harborth proved that

G

has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least

2n/3

. We settle Harborth's conjecture in the affirmative. 2. A \emph{monotone cylindrical} graph is a topological graph drawn on an open cylinder with an infinite vertical axis satisfying the condition that every vertical line intersects every edge at most once. It is called \emph{simple} if any pair of its edges have at most one point in common: an endpoint or a point at which they properly cross. We say that two edges are \emph{disjoint} if they do not intersect. We show that every simple complete monotone cylindrical graph on

n

vertices contains

\Omega(n^{1-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. As a consequence, we show that every simple complete topological graph (drawn in the plane) with

n

vertices contains

\Omega(n^{\frac 12-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. By extending some of the ideas here we are then able to get rid of the

\epsilon

term in the exponent, showing that in fact we can always guarantee a set with

\Omega(n^{\frac 12})

pairwise disjoint edges. This improves the previous lower bound of

\Omega(n^\frac 13)

by Suk and independently by Fulek. We remark that our proof implies a polynomial time algorithm for finding this set of pairwise disjoint edges. 3. A {\em tangle} is a graph drawn in the plane such that its edges are represented by continuous arcs, and any two edges share precisely one point, which is either a common endpoint or an interior point at which the two edges are tangent to each other. These points of tangencies are assumed to be distinct. If we drop the last assumption, that is, more than two edges may touch one another at the same point, then the drawing is called a {\em degenerate tangle}. We settle a problem of Pach, Radoi\v ci'c, and T'oth \cite{TTpaper}, by showing that every degenerate tangle has at most as many edges as vertices. We also give a complete characterization of tangles. 4. We show that for a constant

t\in \NN

, every simple topological graph on

n

vertices has

O(n)

edges if the graph has no two sets of

t

edges each such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is

K_{t,t}

-free). As an application, we settle the \emph{tangled-thrackle} conjecture formulated by Pach, Radoi\v{c}i'c, and T'oth: Every

n

-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most

O(n)

edges.

EPFL2016

Provable Robustness of ReLU networks via Maximization of Linear Regions

Maksym Andriushchenko

It has been shown that neural network classifiers are not robust. This raises concerns about their usage in safety-critical systems. We propose in this paper a regularization scheme for ReLU networks which provably improves the robustness of the classifier by maximizing the linear regions of the classifier as well as the distance to the decision boundary. Our techniques allow even to find the minimal adversarial perturbation for a fraction of test points for large networks. In the experiments we show that our approach improves upon adversarial training both in terms of lower and upper bounds on the robustness and is comparable or better than the state-of-the-art in terms of test error and robustness.

2019

Simple topological graphs

Andres Jacinto Ruiz Vargas

G

be a complete simple topological graph on

n

vertices. The three edges induced by any triplet of vertices in

G

form a simple closed curve. If this curve contains no vertex in its interior (exterior), then we say that the triplet forms an \emph{empty triangle}. In 1998, Harborth proved that

G

has at least 2 empty triangles, and he conjectured that the number of empty triangles is at least

2n/3

n

vertices contains

\Omega(n^{1-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. As a consequence, we show that every simple complete topological graph (drawn in the plane) with

n

vertices contains

\Omega(n^{\frac 12-\epsilon})

pairwise disjoint edges for any

\epsilon>0

. By extending some of the ideas here we are then able to get rid of the

\epsilon

term in the exponent, showing that in fact we can always guarantee a set with

\Omega(n^{\frac 12})

pairwise disjoint edges. This improves the previous lower bound of

\Omega(n^\frac 13)

t\in \NN

, every simple topological graph on

n

vertices has

O(n)

edges if the graph has no two sets of

t

edges each such that every edge in one set is disjoint from all edges of the other set (i.e., the complement of the intersection graph of the edges is

K_{t,t}

-free). As an application, we settle the \emph{tangled-thrackle} conjecture formulated by Pach, Radoi\v{c}i'c, and T'oth: Every

n

-vertex graph drawn in the plane such that every pair of edges have precisely one point in common, where this point is either a common endpoint, a crossing, or a point of tangency, has at most

O(n)

edges.

EPFL2016