A Toolbox for Barriers on Interactive Oracle Proofs
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.
Pearl's do calculus is a complete axiomatic approach to learn the identifiable causal effects from observational data. When such an effect is not identifiable, it is necessary to perform a collection of often costly interventions in the system to learn the ...
Solving the Lexicographic Bottleneck Assignment Problem (LexBAP) typically relies on centralised computation with order complexity. We consider the Sequential Bottleneck Assignment Problem (SeqBAP), which yields a greedy solution to the LexBAP and discuss ...
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 ...
We give a new characterization of the Sherali-Adams proof system, showing that there is a degree-d Sherali-Adams refutation of an unsatisfiable CNF formula C if and only if there is an ε > 0 and a degree-d conical junta J such that viol_C(x) - ε = J, where ...
Schloss Dagstuhl - Leibniz-Zentrum für Informatik2022
We give a construction of an efficient one-out-of-many proof system, in which a prover shows that he knows the pre-image for one element in a set, based on the hardness of lattice problems. The construction employs the recent zero-knowledge framework of Ly ...
With the increasing amount of available data and advances in computing capabilities, deep neural networks (DNNs) have been successfully employed to solve challenging tasks in various areas, including healthcare, climate, and finance. Nevertheless, state-of ...
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 ...
Universal quantum algorithms that prepare arbitrary n-qubit quantum states require O(2n) gate complexity. The complexity can be reduced by considering specific families of quantum states depending on the task at hand. In particular, multipartite quantum st ...
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 ...
An automatic seizure detection method from high-resolution intracranial-EEG (iEEG) signals is presented to minimize the computational complexity and realize real-time accurate seizure detection for biomedical implants. Complex signal processing on a large ...
