Author name cluster

Alexander Healy

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

3 papers

1 author row

STOC Conference 2008 Conference Paper

A (de)constructive approach to program checking

Shafi Goldwasser
Dan Gutfreund
Alexander Healy
Tali Kaufman
Guy N. 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 the field of program checking focused on designing, for specific functions, checkers, testers and correctors which are more efficient than the best program known for the function. These were designed utilizing specific algebraic, combinatorial or completeness properties of the function at hand. In this work we introduce a novel composition methodology for improving the efficiency of program checkers. We use this approach to design a variety of program checkers that are provably more efficient, in terms of circuit depth, than the optimal program for computing the function being checked. Extensions of this methodology for the cases of program testers and correctors are also presented. In particular, we show: For all i ≥ 1, every language in RNC i (that is NCO-hard under NCZ-reductions) has a program checker in RNC i-1 . In addition, for all i ≥ 1, every language in RNC i (that is NCO-hard under ACZ-reductions) has a program corrector, tester and checker in RAC i-1 . This is the first time checkers are designed for a wide class of functions characterized only by its complexity , rather than by algebraic or combinatorial properties. This characterization immediately yields new and efficient checkers for languages such as graph connectivity, perfect matching and bounded-degree graph isomorphism. Constant-depth checkers, testers and correctors for matrix multiplication, inversion, determinant and rank. All previous program checkers, testers and correctors for these problems run in nearly logarithmic depth. Moreover, except for matrix multiplication, they all require the use of the library notion of [Blum-Luby-Rubinfeld], in which checkers have access to a library of programs for various matrix functions, rather than only having access to a program for the function being checked. Furthermore, we provide conditions under which program libraries can be eliminated. Important ingredients in these results are new and very efficient checkers for complete languages in low complexity classes (e.g. NCO). These constructions are based on techniques that were developed in the field of cryptography.

Details

STOC Conference 2007 Conference Paper

Verifying and decoding in constant depth

Shafi Goldwasser
Dan Gutfreund
Alexander Healy
Tali Kaufman
Guy N. Rothblum

We develop a general approach for improving the efficiency of a computationally bounded receiver interacting with a powerful and possibly malicious sender. The key idea we use is that of delegating some of the receiver's computation to the (potentially malicious) sender. This idea was recently introduced by Goldwasser et al. [14] in the area of program checking. A classic example of such a sender-receiver setting is interactive proof systems. By taking the sender to be a (potentially malicious) prover and the receiver to be a verifier, we show that ( p -prover) interactive proofs with k rounds of interaction are equivalent to ( p -prover) interactive proofs with k+O(1) rounds, where the verifier is in NC 0 . That is, each round of the verifier's computation can be implemented in constant parallel time. As a corollary, we obtain interactive proof systems, with (optimally) constant soundness, for languages in AM and NEXP, where the verifier runs in constant parallel-time. Another, less immediate sender-receiver setting arises in considering error correcting codes. By taking the sender to be a (potentially corrupted) codeword and the receiver to be a decoder, we obtain explicit families of codes that are locally (list-)decodable by constant-depth circuits of size polylogarithmic in the length of the codeword. Using the tight connection between locally list-decodable codes and average-case complexity, we obtain a new, more efficient, worst-case to average-case reduction for languages in EXP.

Details

STOC Conference 2004 Conference Paper

Using nondeterminism to amplify hardness

Alexander Healy
Salil P. 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 that any circuit of size s ′( n )= s (√ n ) Ω(1) fails to compute f ′ on a 1/2 - 1/ s ′( n ) fraction of inputs. In particular, 1. If s ( n )= n ω(1) , we amplify to hardness 1/2-1/n ω(1) . 2. If s ( n )=2 n ω(1) , we amplify to hardness 1/2-1/2 n Ω(1) . 3. If s ( n )=2 ( n ) , we amplify to hardness 1/2-1/2 Ω(sqrt n ) .These improve the results of O'Donnell, which only amplified to 1/2-1/√ n . O'Donnell also proved that no construction of a certain general form could amplify beyond 1/2-1/ n . We bypass this barrier by using both derandomization and nondeterminism in the construction of f ′.We also prove impossibility results demonstrating that both our use of nondeterminism and the hypothesis that f is balanced are necessary for "black-box" hardness amplification procedures (such as ours).

Details