Publications related to P-complete

Orthologic with Axioms

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

Latency Interfaces for Systems Code

Rishabh Ramesh Iyer

This thesis demonstrates that it is feasible for systems code to expose a latency interface that describes its latency and related side effects for all inputs, just like the code's semantic interface describes its functionality and related side effects. S ...

EPFL2023

IIBLAST: Speeding Up Commercial FPGA Routing by Decoupling and Mitigating the Intra-CLB Bottleneck

Mirjana Stojilovic, Stefan Nikolic, Shashwat Shrivastava

We identified that in modern commercial FPGAs, routing signals from the general interconnect to the configurable logic blocks (CLBs) through a very sparse input interconnect block (IIB) represents a significant runtime bottleneck. This is despite academic ...

IEEE2023

Formula Normalizations in Verification

Viktor Kuncak, Simon Guilloud, Mario Bucev, Dragana Milovancevic

We propose a new approach for normalization and simplification of logical formulas. Our approach is based on algorithms for lattice-like structures. Specifically, we present two efficient algorithms for computing a normal form and deciding the word problem ...

2023

Effect of Different Communication Affordances on the Emergence of Collaboration Strategies in an Online Multiplayer Game

Pierre Dillenbourg, Barbara Bruno, Hala Khodr, Aditi Kothiyal

In a group, the collective dynamics is governed by the inter- actions between individuals, which can manifest differently depending on the available means of communication. In this paper, we compare 3 conditions of communication affordances (global chat, l ...

Springer2022

Imputation of missing information in worldwide patent data

Gaétan Jean A de Rassenfosse

We present a general method for imputing missing information in the Worldwide Patent Statistical Database (PATSTAT) and make the resulting datasets publicly available. The PATSTAT database is the de facto standard for academic research using patent data. C ...

2021

Minimum-Error Classes for Matching Parts

Thomas Alois Weber

This paper examines the binning of two types of parts with random characteristics, so that a componentwise monotonic evaluation criterion exhibits a minimum deviation to a given target value over all possible realizations. The optimal matching classes are ...

2021

Complete coordination of robotic fiber positioners for massive spectroscopic surveys

Denis Gillet, Jean-Paul Richard Kneib, Matin Macktoobian

Robotic fiber positioners play a vital role in the generation of massive spectroscopic surveys. The more complete a positioners set is coordinated, the more information its corresponding spectrograph receives during an observation. The complete coordinatio ...

2019

Suitably graded THB-spline refinement and coarsening: Towards an adaptive isogeometric analysis of additive manufacturing processes

Rafael Vazquez Hernandez, Alessandro Reali

In the present work we introduce a complete set of algorithms to efficiently perform adaptive refinement and coarsening by exploiting truncated hierarchical B-splines (THB-splines) defined on suitably graded isogeometric meshes, that are called admissible ...

ELSEVIER SCIENCE SA2019

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

Four-Port Broadband Orthomode Transducer Enabling Arbitrary Interelement Spacing

Juan Ramon Mosig, Anja Skrivervik, Emile Jacques de Rijk, Tomislav Debogovic, Maria Garcia Vigueras, Santiago Capdevila Cascante, Esteban Menargues Gomez

This paper reports a novel methodology to design broadband orthomode transducers with two arbitrarily spaced ports carrying orthogonal linear polarizations. The component is based on a combination of two Boifot junctions through a series of power dividers ...

Institute of Electrical and Electronics Engineers2018

The isostatic 3-body problem: a complete solution

Simon Nessim Henein, Florent Cosandier, Ilan Vardi, François Barrot, Johannes Richard Cornelis Geerit Kruis

Kinematic couplings are used when two rigid bodies need to be repeatedly and accurately positioned with respect to each other. They allow for sub-micron positioning repeatability by suppressing play and reducing strains in the bodies. Typical applications ...

2017

Level crossings induced by a longitudinal coupling in the transverse field Ising chain

Frédéric Mila, Grégoire Vionnet

We study the effect of antiferromagnetic longitudinal coupling on the one-dimensional transverse field Ising model with nearest-neighbor couplings. In the topological phase where, in the thermodynamic limit, the ground state is twofold degenerate, we show ...

2017

The teacher in the loop: customizing MMLA in blended CSCL scenarios

Maria Jesus Rodriguez Triana

In across-spaces learning scenarios, evidence needs to be gathered from different spaces to obtain a more complete view of the teaching and learning processes. Multimodal learning analytics (MMLA) enables us to gather data from physical spaces, enriching t ...

2017

INVESTIGATION OF TURBIDITY CURRENT VENTING FOR TWO DIFFERENT RESERVOIR BED SLOPES

Anton Schleiss, Giovanni De Cesare, Sabine Chamoun

Reservoirs represent an important source of energy that should be preserved and sustained. However, the lifetime of reservoirs is being reduced due to natural processes such as sedimentation. To face this problem, different sediment mitigation techniques a ...

2017

A Comment on “Computational Complexity of Stochastic Programming Problems”

Daniel Kuhn, Grani Adiwena Hanasusanto, Wolfram Wiesemann

Although stochastic programming problems were always believed to be computationally challenging, this perception has only recently received a theoretical justification by the seminal work of Dyer and Stougie (Mathematical Programming A, 106(3):423–432, 200 ...

Springer Heidelberg2016

A Sound and Complete Axiomatization of Majority-n Logic

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

Manipulating logic functions via majority operators recently drew the attention of researchers in computer science. For example, circuit optimization based on majority operators enables superior results as compared to traditional logic systems. Also, the B ...

Institute of Electrical and Electronics Engineers2016

Optimizing Majority-Inverter Graphs with Functional Hashing

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

A Majority-Inverter Graph (MIG) is a recently introduced logic representation form whose algebraic and Boolean properties allow for efficient logic optimization. In particular, when considering logic depth reduction, MIG algorithms obtained signific ...

IEEE2016

The symmetry of partner modelling

Pierre Dillenbourg, Nicolas Nova, Séverin Lemaignan, Mirweis Sangin, Gaëlle Molinari

Collaborative learning has often been associated with the construction of a shared understanding of the situation at hand. The psycholinguistics mechanisms at work while establishing common grounds are the object of scientific controversy. We postulate tha ...

Springer2016