All reports by Author Dan Gutfreund:

__
TR12-086
| 4th July 2012
__

Shlomi Dolev, Nova Fandina, Dan Gutfreund#### Succinct Permanent is NEXP-hard with Many Hard Instances

__
TR10-160
| 28th October 2010
__

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

__
TR09-146
| 29th December 2009
__

Dan Gutfreund, Akinori Kawachi#### Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds

__
TR08-034
| 19th January 2008
__

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

Revisions: 1

__
TR08-007
| 6th February 2008
__

Dan Gutfreund, Salil Vadhan#### Limitations of Hardness vs. Randomness under Uniform Reductions

__
TR07-047
| 15th May 2007
__

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

__
TR06-108
| 24th August 2006
__

Dan Gutfreund, Amnon Ta-Shma#### New connections between derandomization, worst-case complexity and average-case complexity

__
TR04-088
| 12th October 2004
__

Emanuele Viola, Dan Gutfreund#### Fooling Parity Tests with Parity Gates

Shlomi Dolev, Nova Fandina, Dan Gutfreund

Finding a problem that is both hard to solve and hard to solve on many instances is a long standing issue

in theoretical computer science.

In this work, we prove that the Succinct Permanent $\bmod \; p$ is $NEXP$

time hard in the worst case (via randomized polynomial time ...
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.

Dan Gutfreund, Akinori Kawachi

We show that if Arthur-Merlin protocols can be derandomized, then there is a Boolean function computable in deterministic exponential-time with access to an NP oracle, that cannot be computed by Boolean circuits of exponential size. More formally, if $\mathrm{prAM}\subseteq \mathrm{P}^{\mathrm{NP}}$ then there is a Boolean function in $\mathrm{E}^{\mathrm{NP}}$ that requires ... 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, Salil Vadhan

We consider (uniform) reductions from computing a function f to the task of distinguishing the output of some pseudorandom generator G from uniform. Impagliazzo and Wigderson (FOCS `98, JCSS `01) and Trevisan and Vadhan (CCC `02, CC `07) exhibited such reductions for every function f in PSPACE. Moreover, their reductions ... 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 >>>

Dan Gutfreund, Amnon Ta-Shma

We show that a mild derandomization assumption together with the

worst-case hardness of NP implies the average-case hardness of a

language in non-deterministic quasi-polynomial time. Previously such

connections were only known for high classes such as EXP and

PSPACE.

There has been a long line of research trying to explain ... more >>>

Emanuele Viola, Dan Gutfreund

We study the complexity of computing $k$-wise independent and

$\epsilon$-biased generators $G : \{0,1\}^n \to \{0,1\}^m$.

Specifically, we refer to the complexity of computing $G$ \emph{explicitly}, i.e.

given $x \in \{0,1\}^n$ and $i \in \{0,1\}^{\log m}$, computing the $i$-th output bit of $G(x)$.

Mansour, Nisan and Tiwari (1990) show that ...
more >>>