Publications associées à NP Satisfiability for Arrays as Powers

Succinct ordering and aggregation constraints in algebraic array theories

We discuss two extensions to a recently introduced theory of arrays, which are based on considerations coming from the model theory of power structures. First, we discuss how the ordering relation on the index set can be expressed succinctly by referring t ...

Elsevier Science Inc2024

Orthologic with Axioms

Viktor Kuncak, Simon Guilloud

We study the proof theory and algorithms for orthologic, a logical system based on ortholattices, which have shown practical relevance in simplification and normalization of verification conditions. Ortholattices weaken Boolean algebras while having polyno ...

Association for Computing Machinery2024

Approximation Algorithms for Allocation and Network Design

Etienne Michel François Bamas

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

EPFL2023

Extractable Witness Encryption for the Homogeneous Linear Equations Problem

Serge Vaudenay, Bénédikt Minh Dang Tran

Witness encryption is a cryptographic primitive which encrypts a message under an instance of an NP language and decrypts the ciphertext using a witness associated with that instance. In the current state of the art, most of the witness encryption construc ...

Springer2023

Scaling Language Features for Program Verification

Georg Stefan Schmid

Formal verification of real-world software systems remains challenging for a number of reasons, including lack of automation, friction in specifying properties, and limited support for the diverse programming paradigms used in industry. In this thesis we m ...

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

Automating cutting planes is NP-hard

Mika Tapani Göös

We show that Cutting Planes (CP) proofs are hard to find: Given an unsatisfiable formula F, It is -hard to find a CP refutation of F in time polynomial in the length of the shortest such refutation; and unless Gap-Hitting-Set admits a nontrivial algorithm, ...

ACM2021

Learning from survey propagation: a neural network for MAX-E-3-SAT

Raffaele Marino

Many natural optimization problems are NP-hard, which implies that they are probably hard to solve exactly in the worst-case. However, it suffices to get reasonably good solutions for all (or even most) instances in practice. This paper presents a new algo ...

IOP PUBLISHING LTD2021

Modelling the Intracellular Environment under Uncertainty, from Post-translational Modification to Metabolic Networks

Robin Alexander Denhardt-Eriksson

Modelling and analysis of biological systems is crucial in order to quantitatively explain and predict their behaviour. The importance of modelling in systems biology becomes even more evident when tackling complex, large systems. Approaches that rely on ...

EPFL2021

Boolean satisfiability in quantum compilation

Giovanni De Micheli, Giulia Meuli, Mathias Soeken, Bruno Schmitt Antunes, Heinz Riener, Fereshte Mozafari Ghoraba

Quantum compilation is the task of translating a quantum algorithm implemented in a high-level quantum programming language into a technology-dependent instructions flow for a physical quantum computer. To tackle the large gap between the quantum program a ...

ROYAL SOC2020

Symbolic Algorithms for Token Swapping

Giovanni De Micheli, Mathias Soeken, Bruno Schmitt Antunes

We study different symbolic algorithms to solve two related reconfiguration problems on graphs: the token swapping problem and the permutation routing via matchings problem. Input to both problems is a connected graph with labeled vertices and a token in e ...

2020

Experimental study of impulse waves generated by viscoplastic fluid

Zhenzhu Meng

Landslide-generated waves, also called impulse waves, occur as a result of the intrusion of landslides (such as rock falls, debris flows, and avalanches) into bodies of water (such as lakes, reservoirs, and seas). The objective of this thesis was to study ...

EPFL2020

Exact Synthesis of Boolean Functions in Majority-of-five Forms

Giovanni De Micheli, Winston Jason Haaswijk, Mathias Soeken, Zhufei Chu

Recent studies show that majority-based logic synthesis is beneficial for both traditional and nanotechnology digital designs. However, most of the existing synthesis algorithms for majority logic generate majority-of-three (M-3) networks. The optimization ...

IEEE2019

SAT-Based Exact Synthesis for Multi-Level Logic Networks

Winston Jason Haaswijk

Today, the design of electronic systems is largely automated. The practice of using software automation technologies for the design of electronic hardware is commonly referred to as Electronic Design Automation (EDA). EDA comprises a large set of tools, fr ...

EPFL2019

Verified Functional Programming

Nicolas Charles Yves Voirol

In this thesis, we present Stainless, a verification system for an expressive subset of the Scala language. Our system is based on a dependently-typed language and an algorithmic type checking procedure which ensures total correctness. We rely on SMT solve ...

EPFL2019

Graph fragmentation problem: analysis and synthesis

Manuel Francesco Aprile, Pablo Romero Gómez

Vulnerability metrics play a key role in the understanding of cascading failures and target/random attacks to a network. The graph fragmentation problem (GFP) is the result of a worst-case analysis of a random attack. We can choose a fixed number of indivi ...

WILEY2019

Satisfiability-Based Methods for Digital Circuit Design, Debug, and Optimization

Andrew James Becker

Designing digital circuits well is notoriously difficult. This difficulty stems in part from the very many degrees of freedom inherent in circuit design, typically coupled with the need to satisfy various constraints. In this thesis, we demonstrate how for ...

EPFL2018

Canonical Computation without Canonical Representation

Ana Petkovska, Luca Gaetano Amarù, Mathias Soeken

A representation of a Boolean function is canonical if, given a variable order, only one instance of the representation is possible for the function. A computation is canonical if the result depends only on the Boolean function and a variable order, and do ...

IEEE2018

Practical Exact Synthesis

Giovanni De Micheli, Luca Gaetano Amarù, Winston Jason Haaswijk, Eleonora Testa, Mathias Soeken

In this paper, we discuss recent advances in exact synthesis, considering both their efficient implementation and various applications in which they can he employed. We emphasize on solving exact synthesis through Boolean satisfiability (SAT) encodings. Di ...

IEEE2018

New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials

Damian Mateusz Straszak

Optimization is a fundamental tool in modern science. Numerous important tasks in biology, economy, physics and computer science can be cast as optimization problems. Consider the example of machine learning: recent advances have shown that even the most s ...

EPFL2018