An argument system for NP is a proof system that allows efficient verification of NP
statements, given proofs produced by an untrusted yet computationally-bounded prover …

Non-interactive zero-knowledge proofs of knowledge for general NP statements are a
powerful cryptographic primitive, both in theory and in practical applications. Recently, much …

One of the more significant achievements of twentieth century mathematics, especially from
the viewpoints of logic and computer science, was the work of Church, Gödel and Turing in …

Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower
complexity than required for classical NP verification. Traditionally, the focus has been on …

In the last fifteen years there has been an explosive growth in the field of combinatorial
algorithms. Although much of the recent work is theoretical in nature, many newly …

The polynomial-time hierarchy is that subrecursive analog of the Kleene arithmetical
hierarchy in which deterministic (nondeterministic) polynomial time plays the role of …

We present a new strongly polynomial algorithm for the minimum cost flow problem, based
on a refinement of the Edmonds-Karp scaling technique. Our algorithm solves the …

Recommender systems typically require users to reveal their ratings to a recommender
service, which subsequently uses them to provide relevant recommendations. Revealing …

This paper studies the consumption decisions of agents who face costs of acquiring,
absorbing and processing information. These consumers rationally choose to only …

Succinct non-interactive arguments of knowledge (SNARKs) enable verifying NP statements
with complexity that is essentially independent of that required for classical NP verification …