Electronic Colloquium on Computational Complexity
Login | Register | Classic Style

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

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

TR09-146 | 29th December 2009
Dan Gutfreund, Akinori Kawachi

Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds

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

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

TR08-007 | 6th February 2008
Dan Gutfreund, Salil Vadhan

Limitations of Hardness vs. Randomness under Uniform Reductions

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

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-108 | 24th August 2006
Dan Gutfreund, Amnon Ta-Shma

New connections between derandomization, worst-case complexity and average-case complexity

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

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

TR04-088 | 12th October 2004
Emanuele Viola, Dan Gutfreund

Fooling Parity Tests with Parity Gates

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

ISSN 1433-8092 | Imprint