Correlation bounds for polynomials over {0,1}.
DRAFT: COMMENTS WELCOME. Due to the editor by January 15, 2009.
Paper [PDF]
Bit-probe lower bounds for succinct data structures.
Manuscript, 2008.
Paper [PDF]
Improved separations between nondeterministic and randomized multiparty communication.
With Matei David and Toniann Pitassi.
In International Workshop on Randomization and Computation (RANDOM), 2008.
Paper [PDF]
The sum of d small-bias generators fools polynomials of degree d.
Best Paper Award.
In Proceedings of the 23th IEEE Conference
on Computational Complexity (CCC), 2008.
Paper [PDF]
Slides from talk given at Theory Day Slides [PDF]
Slides [PPT]
Hardness amplification proofs require majority.
With Ronen Shaltiel.
In Proceedings of the 40th ACM Symposium on Theory
of Computing (STOC), 2008.
Paper [PDF]
Slides from conference talk
Slides [PDF]
Slides [PPT]
Slides from seminar talk
Slides [PDF]
Slides [PPT]
One-way multi-party communication lower bound for pointer
jumping with applications.
With Avi Wigderson.
Submitted to Combinatorica; invited to FOCS Special Issue.
In Proceedings of the
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2007.
Paper [PDF]
Paper [DVI]
Slides from conference talk
Slides [PDF]
Slides [PPT]
Pseudorandom bits for polynomials.
With Andrej Bogdanov.
Submitted to SIAM Journal on Computing, FOCS Special Issue.
In Proceedings of the
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2007.
Paper [PDF]
Paper [DVI]
Norms, XOR lemmas, and lower bounds for GF(2) polynomials and
multiparty protocols.
With Avi Wigderson.
Theory of Computing 4:137-168, 2008.
In Proceedings of the 22th IEEE Conference
on Computational Complexity (CCC), 2007.
Paper [PDF]
Slides from conference talk
Slides [PDF]
Slides [PPT]
The complexity of hardness amplification and
derandomization.
Ph.D. Thesis, Harvard University, 2006.
Thesis [PS]
Thesis [PDF]
Slides from defense talk
Slides [PPT]
Slides [PDF]
On approximate majority and probabilistic time.
To appear in the journal Computational Complexity.
In Proceedings of the 22th IEEE Conference
on Computational Complexity (CCC), 2007.
Paper [PS]
Paper [PDF]
Slides from conference talk
Slides [PDF]
Slides [PPT]
Slides from seminar talk
Slides [PPT]
Slides [PDF]
Pseudorandom bits for constant-depth
circuits with few arbitrary
symmetric gates.
SIAM Student Paper Prize. Link.
SIAM Journal on Computing
, 36(5):1387-1403, 2007.
In Proceedings of the 20th IEEE Conference
on Computational Complexity (CCC), 2005.
Paper [PS]
Paper
[PDF]
Slides from conference talk Slides [PPT]
Slides from seminar talk Slides [PPT]
On constructing parallel pseudorandom generators
from one-way functions.
In Proceedings of the 20th IEEE Conference on Computational Complexity (CCC), 2005.
Paper [PS]
Paper [PDF]
Slides from conference talk Slides [PPT]
Constant-depth circuits for arithmetic in finite fields of
characteristic two.
With Alex Healy.
In Proceedings of the 23rd International
Symposium on Theoretical Aspects of Computer Science
(STACS), 2006.
Paper [PS]
Paper [PDF] ©Springer-Verlag
Using nondeterminism to amplify hardness.
With
Alex Healy and Salil Vadhan.
SIAM Journal on Computing
, 34(4):903-931, 2006, STOC Special Issue.
Conference
version in Proceedings of the 36th ACM Symposium on Theory
of Computing (STOC), 2004.
Paper [PS] Paper [PDF]
Conference version [PS] Conference version [PDF]
Slides from conference talk Slides [PPS]
Slides from seminar
talk Slides [PPS]
The complexity of constructing
pseudorandom generators from hard functions.
Journal Computational Complexity, 13(3-4):147-188, 2004.
In Proceedings of the 18th IEEE Conference on Computational
Complexity (CCC), 2003.
Paper [PS]
Paper [PDF]
Conference version [PS]
Conference version [PDF]
Slides from conference talk Slides [PDF]
Fooling parity tests with parity gates.
With Dan Gutfreund.
In Proceedings of the 8th International Workshop on
Randomization and Computation (RANDOM), 2004.
Paper [PS]
Paper [PDF]
Slides from conference talk
Slides [PPT]
E-unifiability via narrowing.
In Proceedings of the 7th Italian Conference on
Theoretical Computer Science (ICTCS), 2001. Lecture Notes in Computer Science (LNCS) 2202.
Paper [PS]
Paper [PDF]
©Springer-Verlag
Selected Results in Additive Combinatorics: An Exposition.
Electronic Colloquium on Computational Complexity, Report TR07-103, 2007.
Notes [DVI]
Notes [PDF]
New correlation bounds for GF(2) polynomials
using Gowers uniformity.
Electronic Colloquium on Computational Complexity, Report TR06-097, 2006.
Report [PS]
Report [PDF]
Programmer of the video game Black
Viper, produced and distributed throughout Europe by NEO Software
Productions GmbH, Germany, 1996.
Some
images and a
video of the game.
Programmer of the video game Nathan Never,
produced by GENIAS and distributed in Italy by Softel, Rome,
Italy, 1992.
Some
images and a
video of the game.
Programmer of database applications (C++, SQL). Sogetel Ltd., Rome, Italy, 1996.
Consultant. PRAXI Joint-Stock Company,
Rome, Italy, 1999.