Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Guy Rothblum:

TR17-108 | 19th June 2017
Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai

Delegating Computation: Interactive Proofs for Muggles

In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time, or in other words a ``muggle'' (Muggle: ``In the fiction of J.K. Rowling: a person who possesses no magical powers''; from the Oxford English Dictionary). The verifier should be ... more >>>

TR17-018 | 6th February 2017
Oded Goldreich, Guy Rothblum

Simple doubly-efficient interactive proof systems for locally-characterizable sets

Revisions: 2

A proof system is called doubly-efficient if the prescribed prover strategy can be implemented in polynomial-time and the verifier's strategy can be implemented in almost-linear-time.

We present direct constructions of doubly-efficient interactive proof systems for problems in $\cal P$ that are believed to have relatively high complexity.
Specifically, such ... more >>>

TR16-061 | 17th April 2016
Omer Reingold, Ron Rothblum, Guy Rothblum

Constant-Round Interactive Proofs for Delegating Computation

Revisions: 1

The celebrated IP=PSPACE Theorem [LFKN92,Shamir92] allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an ... more >>>

TR16-049 | 28th March 2016
Cynthia Dwork, Moni Naor, Guy Rothblum

Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems

We are interested in constructing short two-message arguments for various languages, where the complexity of the verifier is small (e.g. linear in the input size, or even sublinear if the input is coded appropriately).

In 2000 Aiello et al. suggested the tantalizing possibility of obtaining such arguments for all of ... more >>>

TR12-010 | 5th February 2012
Shafi Goldwasser, Guy Rothblum

How to Compute in the Presence of Leakage

We address the following problem: how to execute any algorithm P, for an unbounded number of executions, in the presence of an adversary who observes partial information on the internal state of the computation during executions. The security guarantee is that the adversary learns nothing, beyond P's input/output behavior.

This ... more >>>

TR10-160 | 28th October 2010
Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

On Approximating the Entropy of Polynomial Mappings

We investigate the complexity of the following computational problem:

Polynomial Entropy Approximation (PEA):
Given a low-degree polynomial mapping
$p : F^n\rightarrow F^m$, where $F$ is a finite field, approximate the output entropy
$H(p(U_n))$, where $U_n$ is the uniform distribution on $F^n$ and $H$ may be any of several entropy measures.

... more >>>

TR09-089 | 26th September 2009
Guy Rothblum, Salil Vadhan

Are PCPs Inherent in Efficient Arguments?

Starting with Kilian (STOC `92), several works have shown how to use probabilistically checkable proofs (PCPs) and cryptographic primitives such as collision-resistant hashing to construct very efficient argument systems (a.k.a. computationally sound proofs), for example with polylogarithmic communication complexity. Ishai et al. (CCC `07) raised the question of whether PCPs ... more >>>

TR08-034 | 19th January 2008
Dan Gutfreund, Guy Rothblum

The Complexity of Local List Decoding

Revisions: 1

We study the complexity of locally list-decoding binary error correcting codes with good parameters (that are polynomially related to information theoretic bounds). We show that computing majority over $\Theta(1/\eps)$ bits is essentially equivalent to locally list-decoding binary codes from relative distance $1/2-\eps$ with list size $\poly(1/\eps)$. That is, a local-decoder ... more >>>

TR07-047 | 15th May 2007
Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy Rothblum

A (De)constructive Approach to Program Checking

Program checking, program self-correcting and program self-testing
were pioneered by [Blum and Kannan] and [Blum, Luby and Rubinfeld] in
the mid eighties as a new way to gain confidence in software, by
considering program correctness on an input by input basis rather than
full program verification. Work in ... more >>>

TR06-034 | 9th March 2006
Moni Naor, Guy Rothblum

The Complexity of Online Memory Checking

Suppose you want to store a large file on a remote and unreliable server. You would like to verify that your file has not been corrupted, so you store a small private (randomized)``fingerprint'' of the file on your own computer. This is the setting for the well-studied authentication problem, and ... more >>>

TR04-085 | 3rd October 2004
Erez Petrank, Guy Rothblum

Selection from Structured Data Sets

A large body of work studies the complexity of selecting the
$j$-th largest element in an arbitrary set of $n$ elements (a.k.a.
the select$(j)$ operation). In this work, we study the
complexity of select in data that is partially structured by
an initial preprocessing stage and in a data structure ... more >>>

ISSN 1433-8092 | Imprint