Alex Healy
Home Papers Music Anagrams

S. Gortler, A. Healy, D. Thurston
Characterizing Generic Global Rigidity
Available at

Applications of Unconditional Pseudorandomness in Complexity Theory (pdf, ps)
Ph.D. Thesis, May 2007.

S. Goldwasser, D. Gutfreund, A. Healy, T. Kaufman, G. Rothblum
Verifying and Decoding in Constant Depth (pdf)
In Proceedings of the 39th ACM Symposium on Theory of Computing (STOC 2007).

S. Goldwasser, D. Gutfreund, A. Healy, T. Kaufman, G. Rothblum
A (De)constructive Approach to Program Checking
ECCC Technical Report TR07-047.

Randomness-Efficient Sampling within NC1 (pdf, ps)
ECCC Technical Report TR06-058.
In Proceedings of the 10th International Workshop on Randomization and Computation (Random 2006).
Invited to Computational Complexity, RANDOM 2006 Special Issue. To appear.

A. Healy, E. Viola
Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two (pdf, ps)
ECCC Technical Report TR05-087.
In Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS 2006).

M. Chase, A. Healy, A. Lysyanskaya, T. Malkin, L. Reyzin
Mercurial Commitments with Applications to Zero-Knowledge Sets (pdf)
In Proceedings of the 24th IACR Eurocrypt Conference (EUROCRYPT 2005).

A. Healy, S. Vadhan, E. Viola
Using Nondeterminism to Amplify Hardness (pdf, ps. Full version: pdf, ps.)
In Proceedings of the 36th ACM Symposium on Theory of Computing (STOC 2004).
Invited to SIAM Journal on Computing, STOC 2004 Special Issue, vol. 35, no. 4, pp. 903-931, 2006.

Unpublished notes and surveys

G. Fink, A. Healy
A Comparison of Wine Preservation Methods (html)
An experiment to test the efficacy of common methods for storing unfinished wine.

Some Connections Between Learning Integer Lattices with Noise and Learning Parity Functions with Noise (pdf, ps)
My final paper for CS 228, Computational Learning Theory, in the spring of 2003.

Finding Anagrams Via Lattice Reduction (pdf, ps)
A note describing an algorithm for finding anagrams due to Noam Elkies. An implementation of the algorithm can be found on the anagram finder page.

Lattice Basis Reduction and Public-Key Cryptography (pdf, ps)
My undergraduate thesis in Math and Computer Science, written in the spring of 2002.

Resultants, Resolvents and the Computation of Galois Groups (pdf, ps)
My final paper for Math 250a, Higher Algebra, in the fall of 2001.

The Combinatorics of the Euro (pdf)
Some interesting combinatorial facts about the euro.
For more about the combinatorics of pocket-change, see János A. Csirik's page.

Copyright © 2017 by Alex Healy