Concept
Turing completeness
Related publications (45)
A Toolbox for Barriers on Interactive Oracle Proofs
Interactive oracle proofs (IOPs) are a proof system model that combines features of interactive proofs (IPs) and probabilistically checkable proofs (PCPs). IOPs have prominent applications in complexity theory and cryptography, most notably to constructing ...
SPRINGER INTERNATIONAL PUBLISHING AG2022Un centre d'art contemporain à la Chaux-de-fond
Le centre d’art contemporain de La Chaux-de-Fonds a pour objectif d’activer ponctuellement le quartier situé dans la partie sud du chemin de fer et de compléter l’offre artistique qui parsème la ville. Cette cité industrielle au dessein patrimonial est per ...
2021What graph neural networks cannot learn: depth vs width
This paper studies the expressive power of graph neural networks falling within the message-passing framework (GNNmp). Two results are presented. First, GNNmp are shown to be Turing universal under sufficient conditions on their depth, width, node attribut ...
2020Verification of Software Network Functions with No Verification Expertise
Software network functions (NFs), such as a network address translator, load balancer, or proxy,
promise to bring flexibility and rapid innovation to computer networks and to reduce operational costs.
However, continuous updates and flexibility typically c ...
EPFL2020The Simple Essence of Algebraic Subtyping: Principal Type Inference with Subtyping Made Easy
MLsub extends traditional Hindley-Milner type inference with subtyping while preserving compact principal types, an exciting new development. However, its specification in terms of biunification is difficult to understand, relying on the new concepts of bi ...
2020Adhesion of a tape loop
In this work, we revisit experimentally and theoretically the mechanics of a tape loop. Using primarily elastic materials (polydimethylsiloxane, PDMS, or polycarbonate, PC) and confocal microscopy, we monitor the shape as well as the applied forces during ...
ROYAL SOC CHEMISTRY2020Quasiconvexity and Relaxation in Optimal Transportation of Closed Differential Forms
This manuscript extends the relaxation theory from nonlinear elasticity to electromagnetism and to actions defined on paths of differential forms. The introduction of a gauge allows for a reformulation of the notion of quasiconvexity in Bandyopadhyay et al ...
SPRINGER2019Controlling strategies to maximize reliability of integrated photo-electrochemical devices exposed to realistic disturbances
Sophia Haussener, Saurabh Yuvraj Tembhurne
We numerically investigate the conversion of solar energy into chemical energy by integrated photo-electrochemical (IPEC) devices and assess their response to time-dependent changes in the boundary conditions and the material properties. We focus on a devi ...
RSC2019Block Oriented Programming: Automating Data-Only Attacks
With the widespread deployment of Control-Flow Integrity (CFI), control-flow hijacking attacks, and consequently code reuse attacks, are significantly more difficult. CFI limits control flow to well-known locations, severely restricting arbitrary code exec ...
ASSOC COMPUTING MACHINERY2018Network Flow Integer Programming to Track Elliptical Cells in Time-Lapse Sequences
Pascal Fua, Engin Türetken, Xinchao Wang, Carlos Joaquin Becker
We propose a novel approach to automatically tracking elliptical cell populations in time-lapse image sequences. Given an initial segmentation, we account for partial occlusions and overlaps by generating an over-complete set of competing detection hypothe ...
2017