All reports by Author Alexander Healy:

__
TR07-047
| 15th May 2007
__

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

__
TR06-058
| 25th April 2006
__

Alexander Healy#### Randomness-Efficient Sampling within NC^1

Revisions: 1

__
TR05-087
| 9th August 2005
__

Alexander Healy, Emanuele Viola#### Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two

__
TR04-087
| 13th October 2004
__

Alexander Healy, Salil Vadhan, Emanuele Viola#### Using Nondeterminism to Amplify Hardness

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

Alexander Healy

We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in AC^0[mod 2]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC^1. For example, we obtain the following results:

... more >>>Alexander Healy, Emanuele Viola

We study the complexity of arithmetic in finite fields of characteristic two, $\F_{2^n}$.

We concentrate on the following two problems:

Iterated Multiplication: Given $\alpha_1, \alpha_2,..., \alpha_t \in \F_{2^n}$, compute $\alpha_1 \cdot \alpha_2 \cdots \alpha_t \in \F_{2^n}$.

Exponentiation: Given $\alpha \in \F_{2^n}$ and a $t$-bit integer $k$, compute $\alpha^k \in \F_{2^n}$.

... more >>>Alexander Healy, Salil Vadhan, Emanuele Viola

We revisit the problem of hardness amplification in $\NP$, as

recently studied by O'Donnell (STOC `02). We prove that if $\NP$

has a balanced function $f$ such that any circuit of size $s(n)$

fails to compute $f$ on a $1/\poly(n)$ fraction of inputs, then

$\NP$ has a function $f'$ such ...
more >>>