A PCP Theorem for Interactive Proofs and Applications

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.

We study the proof theory and algorithms for orthologic, a logical system based on ortholattices, which have shown practical relevance in simplification and normalization of verification conditions. Ortholattices weaken Boolean algebras while having polyno ...

It is well-known that for any integral domain R, the Serre conjecture ring R(X), i.e., the localization of the univariate polynomial ring R[X] at monic polynomials, is a Bezout domain of Krull dimension

The Lizorkin space is well suited to the study of operators like fractional Laplacians and the Radon transform. In this paper, we show that the space is unfortunately not complemented in the Schwartz space. In return, we show that it is dense in C0(Double- ...

In this thesis, we give new approximation algorithms for some NP-hard problems arising in resource allocation and network design. As a resource allocation problem, we study the Santa Claus problem (also known as the MaxMin Fair Allocation problem) in which ...

Self-attention mechanisms and non-local blocks have become crucial building blocks for state-of-the-art neural architectures thanks to their unparalleled ability in capturing long-range dependencies in the input. However their cost is quadratic with the nu ...

A shift from fossil-based energy and products to more sustainable alternatives is essential to reduce greenhouse gas emissions and associated climate change impacts. Biomass represents a promising alternative for providing fuels and carbon-based products w ...

Minimising the longest travel distance for a group of mobile robots with interchangeable goals requires knowledge of the shortest length paths between all robots and goal destinations. Determining the exact length of the shortest paths in an environment wi ...

We study three convolutions of polynomials in the context of free probability theory. We prove that these convolutions can be written as the expected characteristic polynomials of sums and products of unitarily invariant random matrices. The symmetric addi ...

Polynomial neural networks (PNNs) have been recently shown to be particularly effective at image generation and face recognition, where high-frequency information is critical. Previous studies have revealed that neural networks demonstrate a spectral bias ...

In this paper we study the problem of social learning under multiple true hypotheses and self-interested agents. In this setup, each agent receives data that might be generated from a different hypothesis (or state) than the data other agents receive. In c ...

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

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

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

This paper presents explicit solutions for two related non-convex information extremization problems due to Gray and Wyner in the Gaussian case. The first problem is the Gray-Wyner network subject to a sum-rate constraint on the two private links. Here, ou ...

Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable physical assu ...

In this thesis we propose and analyze algorithms for some numerical linear algebra tasks: finding low-rank approximations of matrices, computing matrix functions, and estimating the trace of matrices. In the first part, we consider algorithms for building ...

Consider the family of bounded degree graphs in any minor-closed family (such as planar graphs). Let d be the degree bound and n be the number of vertices of such a graph. Graphs in these classes have hyperfinite decompositions, where, one removes a small ...

We study the computational complexity of the optimal transport problem that evaluates the Wasser- stein distance between the distributions of two K-dimensional discrete random vectors. The best known algorithms for this problem run in polynomial time in th ...

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

In this paper we study the moments of polynomials from the Askey scheme, and we focus on Askey-Wilson polynomials. More precisely, we give a combinatorial proof for the case where d = 0. Their values have already been computed by Kim and Stanton in 2015, h ...

A PCP Theorem for Interactive Proofs and Applications

Chat with Graph Search

Orthologic with Axioms

The multivariate Serre conjecture ring

Explicit representations for Banach subspaces of Lizorkin distributions

Approximation Algorithms for Allocation and Network Design

Linear Complexity Self-Attention With 3rd Order Polynomials

Decision support for the design of integrated biorefineries

Certification of Bottleneck Task Assignment With Shortest Path Criteria

Finite free convolutions of polynomials

The spectral bias of polynomial neural networks

Social Learning with Disparate Hypotheses

A Toolbox for Barriers on Interactive Oracle Proofs

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

On Succinct Non-interactive Arguments in Relativized Worlds

The Gray-Wyner Network and Wyner's Common Information for Gaussian Sources

Spatial Isolation Implies Zero Knowledge Even in a Quantum World

Fast deterministic and randomized algorithms for low-rank approximation, matrix functions, and trace estimation

Random walks and forbidden minors III: poly(d epsilon(-1))-time partition oracles for minor-free graph classes

Discrete Optimal Transport with Independent Marginals is #P-Hard

On Semi-Algebraic Proofs and Algorithms

Computation of Al-Salam Carlitz and Askey-Wilson moments using Motzkin paths