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 AG2022

Un 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 ...

2021

What graph neural networks cannot learn: depth vs width

Andreas Loukas

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 ...

2020

Verification of Software Network Functions with No Verification Expertise

Arseniy Zaostrovnykh

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 ...

EPFL2020

The Simple Essence of Algebraic Subtyping: Principal Type Inference with Subtyping Made Easy

Lionel Emile Vincent Parreaux

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 ...

2020

Adhesion of a tape loop

Harmeet Singh

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 CHEMISTRY2020

Quasiconvexity and Relaxation in Optimal Transportation of Closed Differential Forms

Bernard Dacorogna

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 ...

SPRINGER2019

Controlling 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 ...

RSC2019

Block Oriented Programming: Automating Data-Only Attacks

Mathias Josef Payer

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 MACHINERY2018

Network 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

Graph Chatbot

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.