All reports by Author Guy Rothblum:

__
TR18-069
| 14th April 2018
__

Oded Goldreich, Guy Rothblum#### Constant-round interactive proof systems for AC0[2] and NC1

Revisions: 1

__
TR18-046
| 9th March 2018
__

Oded Goldreich, Guy Rothblum#### Counting $t$-cliques: Worst-case to average-case reductions and Direct interactive proof systems

Revisions: 2

__
TR18-022
| 1st February 2018
__

Omer Reingold, Guy Rothblum, Ron Rothblum#### Efficient Batch Verification for UP

__
TR17-130
| 30th August 2017
__

Oded Goldreich, Guy Rothblum#### Worst-case to Average-case reductions for subclasses of P

Revisions: 3

__
TR17-108
| 19th June 2017
__

Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai#### Delegating Computation: Interactive Proofs for Muggles

Revisions: 1

__
TR17-018
| 6th February 2017
__

Oded Goldreich, Guy Rothblum#### Simple doubly-efficient interactive proof systems for locally-characterizable sets

Revisions: 3

__
TR16-061
| 17th April 2016
__

Omer Reingold, Ron Rothblum, Guy Rothblum#### Constant-Round Interactive Proofs for Delegating Computation

Revisions: 1

__
TR16-049
| 28th March 2016
__

Cynthia Dwork, Moni Naor, Guy Rothblum#### Spooky Interaction and its Discontents: Compilers for Succinct Two-Message Argument Systems

__
TR12-010
| 5th February 2012
__

Shafi Goldwasser, Guy Rothblum#### How to Compute in the Presence of Leakage

__
TR10-160
| 28th October 2010
__

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan#### On Approximating the Entropy of Polynomial Mappings

__
TR09-089
| 26th September 2009
__

Guy Rothblum, Salil Vadhan#### Are PCPs Inherent in Efficient Arguments?

__
TR08-034
| 19th January 2008
__

Dan Gutfreund, Guy Rothblum#### The Complexity of Local List Decoding

Revisions: 1

__
TR07-047
| 15th May 2007
__

Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy Rothblum#### A (De)constructive Approach to Program Checking

__
TR06-034
| 9th March 2006
__

Moni Naor, Guy Rothblum#### The Complexity of Online Memory Checking

__
TR04-085
| 3rd October 2004
__

Erez Petrank, Guy Rothblum#### Selection from Structured Data Sets

Oded Goldreich, Guy Rothblum

We present constant-round interactive proof systems for sufficiently uniform versions of AC0[2] and NC1.

Both proof systems are doubly-efficient, and offer a better trade-off between the round complexity and the total communication than

the work of Reingold, Rothblum, and Rothblum (STOC, 2016).

Our proof system for AC0[2] supports a more ...
more >>>

Oded Goldreich, Guy Rothblum

We present two main results regarding the complexity of counting the number of $t$-cliques in a graph.

\begin{enumerate}

\item{\em A worst-case to average-case reduction}:

We reduce counting $t$-cliques in any $n$-vertex graph to counting $t$-cliques in typical $n$-vertex graphs that are drawn from a simple distribution of min-entropy ${\widetilde\Omega}(n^2)$. For ...
more >>>

Omer Reingold, Guy Rothblum, Ron Rothblum

Consider a setting in which a prover wants to convince a verifier of the correctness of k NP statements. For example, the prover wants to convince the verifier that k given integers N_1,...,N_k are all RSA moduli (i.e., products of equal length primes). Clearly this problem can be solved by ... more >>>

Oded Goldreich, Guy Rothblum

For every polynomial $q$, we present worst-case to average-case (almost-linear-time) reductions for a class of problems in $\cal P$ that are widely conjectured not to be solvable in time $q$.

These classes contain, for example, the problems of counting the number of $k$-cliques in a graph, for any fixed $k\geq3$.

more >>>

Shafi Goldwasser, Guy Rothblum, Yael Tauman Kalai

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

Oded Goldreich, Guy Rothblum

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

Omer Reingold, Ron Rothblum, Guy Rothblum

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

Cynthia Dwork, Moni Naor, Guy Rothblum

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

Shafi Goldwasser, Guy Rothblum

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

Zeev Dvir, Dan Gutfreund, Guy Rothblum, Salil Vadhan

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.

Guy Rothblum, Salil Vadhan

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

Dan Gutfreund, Guy Rothblum

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

Dan Gutfreund, Alexander Healy, Tali Kaufman, Guy Rothblum

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

Moni Naor, Guy Rothblum

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

Erez Petrank, Guy Rothblum

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