On the power of small-depth computation.
To appear in Foundations and Trends in Theoretical Computer Science (FnT-TCS), 2009. (Invited survey, subsumes SIGACT 2009 survey)
Comments still welcome!
Survey [PDF]
A computational view of market efficiency.
With Jasmina Hasanhodzic and Andrew W. Lo.
Manuscript, 2009.
Paper [PDF]
Cell-Probe Lower Bounds for Succinct Partial Sums.
With Mihai Patrascu.
In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009.
Paper [PDF]
A related Paper [PDF]
Bounded independence fools halfspaces.
With Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, and Rocco Servedio.
In 50th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2009.
Paper [PDF]
Slides from seminar talk
Slides [PDF]
Slides [ODP]
Slides [PPT]
Bit-probe lower bounds for succinct data structures.
Submitted to SIAM Journal on Computing, STOC special issue.
In 41st ACM Symposium on Theory of Computing (STOC), 2009.
Paper [PDF]
Slides from conference talk
Slides [PDF]
Slides [ODP].
Improved separations between nondeterministic and randomized multiparty communication.
With Matei David and Toniann Pitassi.
To appear in Transactions on Computation Theory.
In International Workshop on Randomization and Computation (RANDOM), 2008.
Paper [PDF]
The sum of d small-bias generators fools polynomials of degree d.
Computational Complexity, 18(2): 209-217, 2009, CCC special issue.
In 23th IEEE Conference
on Computational Complexity (CCC), 2008. Best Paper Award.
Paper [PDF]
Slides from talk given at Theory Day Slides [PDF]
Slides [PPT]
Hardness amplification proofs require majority.
With Ronen Shaltiel.
Submitted to SIAM Journal on Computing.
In 40th ACM Symposium on Theory
of Computing (STOC), 2008.
Paper [PDF]
Slides from conference talk
Slides [PDF]
Slides [PPT]; from seminar talk
Slides [PDF]
Slides [PPT]
One-way multi-party communication lower bound for pointer
jumping with applications.
With Avi Wigderson.
To appear in Combinatorica; invited to FOCS Special Issue.
In 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.
To appear in SIAM Journal on Computing, FOCS Special Issue.
In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2007.
Paper [PDF]
Norms, XOR lemmas, and lower bounds for GF(2) polynomials and
multiparty protocols.
With Avi Wigderson.
Theory of Computing 4:137-168, 2008.
In 22th IEEE Conference
on Computational Complexity (CCC), 2007.
Paper [PDF]
Slides from conference talk
Slides [PDF]
Slides [PPT]
The results on polynomials appeared also in the report
"New correlation bounds for GF(2) polynomials
using Gowers uniformity"
Electronic Colloquium on Computational Complexity, TR06-097, 2006.
Report [PS]
Report [PDF]
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 22th IEEE Conference
on Computational Complexity (CCC), 2007.
Paper [PS]
Paper [PDF]
Slides from conference talk
Slides [PDF]
Slides [PPT]; from seminar talk
Slides [PPT]
Slides [PDF]
Pseudorandom bits for constant-depth
circuits with few arbitrary
symmetric gates.
SIAM Journal on Computing, 36(5):1387-1403, 2007.
SIAM Student Paper Prize. Link.
In 20th IEEE Conference
on Computational Complexity (CCC), 2005.
Paper [PS]
Paper
[PDF]
Slides from conference talk Slides [PPT]; from seminar talk Slides [PPT]
On constructing parallel pseudorandom generators
from one-way functions.
In 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 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.
In 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]; from seminar talk Slides [PPS]
The complexity of constructing
pseudorandom generators from hard functions.
Journal Computational Complexity, 13(3-4):147-188, 2004.
In 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 8th International Workshop on
Randomization and Computation (RANDOM), 2004.
Paper [PS]
Paper [PDF]
Slides from conference talk
Slides [PPT]
E-unifiability via narrowing.
In 7th Italian Conference on
Theoretical Computer Science (ICTCS), 2001.
Paper [PS]
Paper [PDF]
©Springer-Verlag
Correlation bounds for polynomials over {0,1}.
ACM SIGACT news 40(1), 2009. (Invited survey.)
Paper [PDF]
Selected results in additive combinatorics: an exposition.
To appear in Theory of Computing , graduate surveys
Electronic Colloquium on Computational Complexity, Report TR07-103, 2007.
Paper [DVI]
Paper [PDF]
Black Viper, produced and distributed throughout Europe by NEO Software
Productions GmbH, Germany, 1996.
Some
images and a
video of the game.
Nathan Never,
produced by GENIAS and distributed in Italy by Softel, Rome,
Italy, 1992.
Some
images and a
video of the game.