Emanuele Viola
Assistant Professor
College of Computer and Information Science
Northeastern University
Theory of
computation at Northeastern University.
| Email: | (my five-letter last name)@ccs.neu.edu |
| Tel: | 617-373-8298 |
Office: | 440 Huntington Av., #246 West Village H (WVH), Boston, MA 02115 map |
| Mail: | 360 Huntington Av., #202 WVH, Boston, MA 02115 |
Curriculum vitae.
Research statement (version of September 2010).
The communication complexity of addition
Manuscript, 2011
Document
Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates
With Anna Gal and Kristoffer Arnsfelt Hansen and Michal Koucky and Pavel Pudlak
Manuscript, 2011
Document
Block ciphers, pseudorandom functions, and natural proofs
With Eric Miles
Manuscript, 2011
Document
Do humans perceive temporal order in asset returns?
With Jasmina Hasanhodzic and Andrew Lo
Manuscript, 2011
Play the game
Press coverage: Financial Times (link), MIT Technology Review
Document
In Brute-Force Search of Correlation Bounds for Polynomials
With Frederic Green and Daniel Kreymer
Manuscript, 2011
Document Code
Extractors for circuit sources
In IEEE Symp. on Foundations of Computer Science (FOCS), 2011
Invited and submitted to FOCS Special Issue
Document Slides
On beating the hybrid argument
With Bill Fefferman and Ronen Shaltiel and Christopher Umans
In ACM Innovations in Theoretical Computer Science conf. (ITCS), 2012
Document
Randomness buys depth for approximate counting
In IEEE Symp. on Foundations of Computer Science (FOCS), 2011
Document Slides
On the Complexity of Non-adaptively Increasing the Stretch of Pseudorandom Generators
With Eric Miles
In Theory of Cryptography Conf. (TCC), 2011
Document
A Computational View of Market Efficiency
With Jasmina Hasanhodzic and Andrew W. Lo
Quantitative Finance, vol. 11, num. 7, 2011
Document
Bounded-depth circuits cannot sample good codes
With Shachar Lovett
In IEEE Conf. on Computational Complexity (CCC), 2011
Invited and submitted to special issue of Computational Complexity
Document
The complexity of distributions
To appear in SIAM J. on Computing
Preliminary version in 51th IEEE Symp. on Foundations of Computer Science (FOCS), 2010
Subsumes the manuscript ``Are all distributions easy?''
Document Slides Video
Cell-probe lower bounds for succinct partial sums
With Mihai Patrascu
In 21th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2010
A related Paper
Document Slides
Bounded Independence Fools Halfspaces
With Ilias Diakonikolas and Parikshit Gopalan and Ragesh Jaiswal and Rocco A. Servedio
SIAM J. on Computing, vol. 39, num. 8, pp. 3441-3462, 2010
Preliminary version in 50th IEEE Symp. on Foundations of Computer Science (FOCS), 2009
This paper in particular shows that the central-limit theorem holds even for variables that are only k-wise independent.
Document Slides
Bit-probe lower bounds for succinct data structures
To appear in SIAM J. on Computing
Preliminary version in 41th ACM Symp. on the Theory of Computing (STOC), 2009
STOC Special Issue
Document Slides
Improved separations between nondeterministic and randomized multiparty communication
With Matei David and Toniann Pitassi
ACM Trans. Computation Theory, vol. 1, num. 2, pp. 1--20, 2009
Preliminary version in 12th Workshop on Randomization and Computation (RANDOM), 2008
Document
The sum of d small-bias generators fools polynomials of degree d
Computational Complexity, vol. 18, num. 2, pp. 209-217, 2009
Preliminary version in IEEE Conf. on Computational Complexity (CCC), 2008
Best paper award
Document Slides
Hardness amplification proofs require majority
With Ronen Shaltiel
SIAM J. on Computing, vol. 39, num. 7, pp. 3122-3154, 2010
Preliminary version in 40th ACM Symp. on the Theory of Computing (STOC), 2008
Document Slides
One-way multiparty communication lower bound for pointer jumping with applications
With Avi Wigderson
Combinatorica, vol. 29, num. 6, pp. 719-743, 2009
Preliminary version in 48th IEEE Symp. on Foundations of Computer Science (FOCS), 2007
Invited to FOCS Special Issue
Document Slides
Pseudorandom bits for polynomials
With Andrej Bogdanov
SIAM J. on Computing, vol. 39, num. 6, pp. 2464-2486, 2010
Preliminary version in IEEE Symp. on Foundations of Computer Science (FOCS), 2007
FOCS Special Issue
Document Slides
Norms, XOR lemmas, and lower bounds for GF(2) polynomials and multiparty protocols
With Avi Wigderson
Theory of Computing, vol. 4, pp. 137-168, 2008
Preliminary version in IEEE Conf. on Computational Complexity (CCC), 2007
The results on polynomials appeared also in the 2006 Report "New correlation bounds for GF(2) polynomials using Gowers uniformity"
Document Slides
On approximate majority and probabilistic time
Computational Complexity, vol. 18, num. 3, pp. 337-375, 2009
Preliminary version in IEEE Conf. on Computational Complexity (CCC), 2007
Document Slides
Pseudorandom Bits for Constant-Depth Circuits with Few Arbitrary Symmetric Gates
SIAM J. on Computing, vol. 36, num. 5, pp. 1387-1403, 2007
Preliminary version in 20th IEEE Conf. on Computational Complexity (CCC), 2005
SIAM Student Paper Prize
Document Slides
On Constructing Parallel Pseudorandom Generators from One-Way Functions
In 20th IEEE Conf. on Computational Complexity (CCC), 2005
Document Slides
Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
With Alexander Healy
In 23rd Symp. on Theoretical Aspects of Computer Science (STACS), 2006
Document
Fooling Parity Tests with Parity Gates
With Dan Gutfreund
In 8thWorkshop on Randomization and Computation (RANDOM), 2004
Document Slides
Using Nondeterminism to Amplify Hardness
With Alexander Healy and Salil P. Vadhan
SIAM J. on Computing, vol. 35, num. 4, pp. 903-931, 2006
Preliminary version in ACM Symp. on the Theory of Computing (STOC), 2004
STOC Special Issue
Document Slides
The Complexity of Constructing Pseudorandom Generators from Hard Functions
Computational Complexity, vol. 13, num. 3-4, pp. 147--188, 2004
Preliminary version in IEEE Conf. on Computational Complexity (CCC), 2003
Document Slides
E-unifiability via Narrowing
In 7th Italian Conference on Theoretical Computer Science (ICTCS), 2001
Document Slides
Selected Results in Additive Combinatorics: An Exposition
Theory of Computing Library, Graduate Surveys series, num. 3, pp. 1-15, 2011
Document
On the power of small-depth computation
Foundations and Trends in Theoretical Computer Science, vol. 5, num. 1, pp. 1--72, 2009
Invited survey, subsumes SIGACT 2009 survey
Document
Correlation bounds for polynomials over {0,1}
SIGACT News, Complexity Theory Column, vol. 40, num. 1, 2009
Invited survey
Document
The Complexity of Hardness Amplification and Derandomization
Ph.D. thesis, Harvard University, 2006
Document Slides
Think like the pros
Manuscript, 2011
Lecture notes aimed towards students lacking mathematical maturity
Document
Reducing 3XOR to listing triangles, an exposition
Manuscript, 2011
Document
Gems of Theoretical Computer Science
Manuscript, 2009
Lecture notes of the class taught at Northeastern University
Document
| Postdoc: | Chinmoy Dutta (partial funding, Spring 2011-present) |
|
|
|
| Ph.D.: | Eric Miles (Fall 2008-present) |
| Hamid Jahanjou (Fall 2011-present) |
| Zahra Jafargholi (Fall 2011-present) |
|
|
|
|
| MS: | Dolphy Fernandes (Summer 2009) |
|
|
|
| Undergraduate: | Sky O'Mara (Summer 2009) |
| Daniel Kreymer (2009-2010) |
16th International Workshop on Randomization and Computation (RANDOM
2012).
25th IEEE Conference on Computational Complexity (CCC
2010).
13th International Workshop on Randomization and Computation (RANDOM
2009).
49th IEEE Symposium on Foundations of Computer Science (FOCS 2008).
11th International Workshop on Randomization and Computation (RANDOM
2007).
LaTeX resources
The bibliographies in this page and in my cv are both generated from a bib file (sample) using
Bibtex to LaTeX and HTML (blah), a Perl script I wrote. Blah supports several features that I could not find in the other 127 solutions available online, see the documentation at the beginning of the script.
Awesome LaTeX code that redefines \[ \] to automatically switch between equation, multline*, etc.
LaTeX package to restate theorems.
From the Nineties
Black Viper
Produced and distributed throughout Europe by NEO Software Productions GmbH, Germany, 1996.
Longplay.
Compressione dei suoni
Amigamagazine, Anno 7, Ottobre 1994
Paper (in Italian)
Nathan Never
Produced by GENIAS and distributed in Italy by Softel, Rome,
Italy, 1992
Longplay Level 1,
Level 2, and
Level 3. (The puzzle level is missing.)
Note: I coded up the game in assembly when I was 14.
The Northeastern Computer Science building towers over the adjacent Back Bay Fens.
Some pictures of my wedding.
I write tales in Italian with my mother. Some information is available here.