Bounded-depth circuits cannot sample good codes.
With Shachar Lovett.
Manuscript, 2010.
Paper [PDF].
The complexity of distributions.
To appear in 51st IEEE Symposium on Foundations of Computer Science (FOCS), 2010.
Paper [PDF].
Subsumes the manuscript ``Are all distributions easy?'' manuscript [PDF]
Is it real, or is it randomized?: A financial
Turing test.
With Jasmina Hasanhodzic and Andrew W. Lo.
Manuscript, 2010.
Paper [PDF]
On the power of small-depth computation.
Foundations and Trends in Theoretical Computer Science (FnT-TCS),
Vol. 5: No 1, pp 1-72, 2009. (Invited survey, subsumes SIGACT 2009 survey)
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), 2010.
Paper [PDF]
A related Paper [PDF]
Slides from seminar talk on lower bounds for succinct data structures
Slides [PDF]
Slides [ODP]
Bounded independence fools halfspaces.
With Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, and Rocco Servedio.
SIAM Journal on Computing, 39(8): 3441-3462, 2010.
In 50th 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.
To appear in 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.
Transactions on Computation Theory
Vol. 1: No 2, pp 1--20, 2009.
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.
SIAM Journal on Computing
SIAM J. Comput. Vol. 39, Issue 7, pp 3122-3154, 2010.
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.
Combinatorica, Vol. 29, No 6, pp 719-743, 2009. Invited to FOCS Special Issue.
In 48th 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.
SIAM Journal on Computing,
Vol. 39, Issue 6, pp 2464-2486, 2010; FOCS Special Issue.
In 48th 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.
Journal Computational Complexity, 18(3):337-375, 2009.
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.