Bounded independence fools halfspaces I Diakonikolas, P Gopalan, R Jaiswal, RA Servedio, E Viola SIAM Journal on Computing 39 (8), 3441-3462, 2010 | 160 | 2010 |
Pseudorandom bits for polynomials A Bogdanov, E Viola SIAM Journal on Computing 39 (6), 2464-2486, 2010 | 157 | 2010 |
Norms, XOR lemmas, and lower bounds for polynomials and protocols E Viola, A Wigderson Theory of Computing 4 (1), 137-168, 2008 | 144* | 2008 |
The sum of d small-bias generators fools polynomials of degree d E Viola Computational Complexity 18 (2), 209-217, 2009 | 132 | 2009 |
Hardness amplification proofs require majority R Shaltiel, E Viola Proceedings of the fortieth annual ACM symposium on Theory of computing, 589-598, 2008 | 104 | 2008 |
The complexity of constructing pseudorandom generators from hard functions E Viola computational complexity 13 (3), 147-188, 2005 | 102 | 2005 |
Using nondeterminism to amplify hardness A Healy, S Vadhan, E Viola Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing …, 2004 | 92 | 2004 |
On the complexity of information spreading in dynamic networks C Dutta, G Pandurangan, R Rajaraman, Z Sun, E Viola Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete …, 2013 | 86 | 2013 |
Extractors for circuit sources E Viola SIAM Journal on Computing 43 (2), 655-672, 2014 | 83 | 2014 |
Pseudorandom bits for constant depth circuits with few arbitrary symmetric gates E Viola 20th Annual IEEE Conference on Computational Complexity (CCC'05), 198-209, 2005 | 72 | 2005 |
The complexity of distributions E Viola SIAM Journal on Computing 41 (1), 191-218, 2012 | 69 | 2012 |
On the power of small-depth computation E Viola Foundations and Trends® in Theoretical Computer Science 5 (1), 1-72, 2009 | 68 | 2009 |
Local reductions H Jahanjou, E Miles, E Viola Automata, Languages, and Programming: 42nd International Colloquium, ICALP …, 2015 | 66 | 2015 |
Cell-probe lower bounds for succinct partial sums M Pătraşcu, E Viola Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete …, 2010 | 66 | 2010 |
On constructing parallel pseudorandom generators from one-way functions E Viola 20th Annual IEEE Conference on Computational Complexity (CCC'05), 183-197, 2005 | 63 | 2005 |
The communication complexity of addition E Viola Combinatorica 35, 703-747, 2015 | 62 | 2015 |
Constant-depth circuits for arithmetic in finite fields of characteristic two A Healy, E Viola Annual Symposium on Theoretical Aspects of Computer Science, 672-683, 2006 | 61 | 2006 |
Short PCPs with projection queries E Ben-Sasson, E Viola Automata, Languages, and Programming: 41st International Colloquium, ICALP …, 2014 | 60 | 2014 |
Substitution-permutation networks, pseudorandom functions, and natural proofs E Miles, E Viola Journal of the ACM (JACM) 62 (6), 1-29, 2015 | 59 | 2015 |
On approximate majority and probabilistic time E Viola Computational Complexity 18 (3), 337, 2009 | 58 | 2009 |