Concept

Nombre de Liouville

Publications associées (42)

Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems

Rüdiger Urbanke, Nicolas Macris, Seyed Hamed Hassani

We consider chains of random constraint satisfaction models that are spatially coupled across a finite window along the chain direction. We investigate their phase diagram at zero temperature using the survey propagation formalism and the interpolation met ...

Springer Verlag2013

Synthesis Modulo Recursive Functions

Viktor Kuncak, Etienne Kneuss, Ivan Kuraj, Philippe Paul Henri Suter

We describe techniques for synthesis and verification of recursive functional programs over unbounded domains. Our techniques build on top of an algorithm for satisfiability modulo recursive functions, a framework for deductive synthesis, and complete synt ...

2013

On Integrating Deductive Synthesis and Verification Systems

Viktor Kuncak, Etienne Kneuss, Ivan Kuraj, Philippe Paul Henri Suter

2013

Infinite labeled trees: From rational to Sturmian trees

Nicolas Gabriel Gast

This paper studies infinite unordered d-ary trees with nodes labeled by {0,1}. We introduce the notions of rational and Sturmian trees along with the definitions of (strongly) balanced trees and mechanical trees, and study the relations among them. In part ...

Elsevier2010

EDF-schedulability of synchronous periodic task systems is coNP-hard

Friedrich Eisenbrand, Thomas Rothvoss

In the synchronous periodic task model, a set \tau_1,...,\tau_n of tasks is given, each releasing jobs of running time c_i with relative deadline d_i, at each integer multiple of the period p_i. It is a classical result that Earliest Deadline First (EDF) i ...

2010

New Hardness Results for Diophantine Approximation

Friedrich Eisenbrand, Thomas Rothvoss

We revisit simultaneous diophantine approximation, a classical problem from the geometry of numbers which has many applications in algorithms and complexity. The input of the decision version of this problem consists of a rational vector \alpha, an error b ...

Springer2009

Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures

Rachid Guerraoui, Eric Ruppert

We introduce a new theoretical model of ad hoc mobile computing in which agents have severely restricted memory, highly unpredictable movement and no initial knowledge of the system. Each agent’s memory can store O(1) bits, plus a unique identiﬁer, and O(1 ...

2009

Efficient Protocols for Set Membership and Range Proofs

Rafik Chaabouni

We consider the following problem: Given a commitment to a value σ, prove in zero-knowledge that σ belongs to some discrete set Φ. The set Φ can perhaps be a list of cities or clubs; often Φ can be a numerical range such as [1, 220]. This problem arises in ...

Springer2008

Propriétés fines des trajectoires du mouvement brownien fractionnaire

Driss Baraka

Let X = {X(t); t ∈ RN} be a (N,d) fractional Brownian motion in Rd of index H ∈ (0,1). We study the local time of X for all temporal dimensions N and spatial dimensions d for which local time exist. We obtain two main results : R1. If we denote by Lx(I) th ...

EPFL2008

Virtual Infrastructure for Collision-Prone Wireless Networks

Seth Gilbert

Wireless ad hoc networks pose several significant challenges: devices are unreliable; deployments are unpredictable; and communication is erratic. One proposed solution is Virtual Infrastructure, an abstraction in which unpredictable and unreliable devices ...

2008

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Connectez-vous pour utiliser Chat avec Graph Search