Publications associées à Oracle (machine de Turing)

On Succinct Non-interactive Arguments in Relativized Worlds

Succinct non-interactive arguments of knowledge (SNARKs) are cryptographic proofs with strong efficiency properties. Applications of SNARKs often involve proving computations that include the SNARK verifier, a technique called recursive composition. Unfort ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Zero-Knowledge IOPs with Linear-Time Prover and Polylogarithmic-Time Verifier

Alessandro Chiesa, Siqi Liu

Interactive oracle proofs (IOPs) are a multi-round generalization of probabilistically checkable proofs that play a fundamental role in the construction of efficient cryptographic proofs. We present an IOP that simultaneously achieves the properties of zer ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

A Toolbox for Barriers on Interactive Oracle Proofs

Alessandro Chiesa

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

A PCP Theorem for Interactive Proofs and Applications

Alessandro Chiesa

The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multi ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

Extra Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods

Volkan Cevher, Kimon Antonakopoulos, Ali Kavis

This work proposes a universal and adaptive second-order method for minimizing second-order smooth, convex functions. Our algorithm achieves O(σ/T‾‾√) convergence when the oracle feedback is stochastic with variance σ2, and improves its convergence to O(1/ ...

2022

Gemini: Elastic SNARKs for Diverse Environments

Alessandro Chiesa

We introduce a new class of succinct arguments, that we call elastic. Elastic SNARKs allow the prover to allocate different resources (such as memory and time) depending on the execution environment and the statement to prove. The resulting output is indep ...

SPRINGER INTERNATIONAL PUBLISHING AG2022

A Novel Method for Detecting Unidentified Falling Object Loss Patterns in the LHC

Frédéric Blanc, Davide Di Croce, Tatiana Pieloni, Jorg Wenninger, Loïc Thomas Davies Coyle

Understanding and mitigating particle losses in the Large Hadron Collider (LHC) is essential for both machine safety and efficient operation. Abnormal loss distributions are tell- tale signs of abnormal beam behaviour or incorrect machine configuration. By ...

Journals of Accelerator Conferences Website (JACoW) 2022

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Lars Rohwedder

Weighted flow time is a fundamental and very well-studied objective function in scheduling. In this paper, we study the setting of a single machine with preemptions. The input consists of a set of jobs, characterized by their processing times, release time ...

ASSOC COMPUTING MACHINERY2021

Scalable and Efficient Comparison-based Search without Features

Matthias Grossglauser, Lucas Maystre, Daniyar Chumbalov

We consider the problem of finding a target object t using pairwise comparisons, by asking an oracle questions of the form “Which object from the pair (i, j) is more similar to t?”. Objects live in a space of latent features, from which the oracle generate ...

2020

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.

Oracle (machine de Turing)

On Succinct Non-interactive Arguments in Relativized Worlds

Zero-Knowledge IOPs with Linear-Time Prover and Polylogarithmic-Time Verifier

A Toolbox for Barriers on Interactive Oracle Proofs

A PCP Theorem for Interactive Proofs and Applications

Extra Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods

Gemini: Elastic SNARKs for Diverse Environments

A Novel Method for Detecting Unidentified Falling Object Loss Patterns in the LHC

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

Scalable and Efficient Comparison-based Search without Features

Program compilation for large-scale quantum computers

Graph Chatbot

Chattez avec Graph Search

Zero-Knowledge IOPs with Linear-Time Prover and Polylogarithmic-Time Verifier

On Succinct Non-interactive Arguments in Relativized Worlds

Program compilation for large-scale quantum computers

Gemini: Elastic SNARKs for Diverse Environments

Extra Newton: A First Approach to Noise-Adaptive Accelerated Second-Order Methods

Scalable and Efficient Comparison-based Search without Features

A Toolbox for Barriers on Interactive Oracle Proofs

A PCP Theorem for Interactive Proofs and Applications

A (2+epsilon)-Approximation Algorithm for Preemptive Weighted Flow Time on a Single Machine

A Novel Method for Detecting Unidentified Falling Object Loss Patterns in the LHC