Emanuele Viola
Associate Professor
College of Computer and Information Science
Northeastern University
Theory of
computation at Northeastern University.
Email:  (my fiveletter last name)@ccs.neu.edu 
Tel:  6173738298 
Office:  440 Huntington Av., #338 West Village H (WVH) 
Mail:  360 Huntington Av., #202 WVH, 
 Boston, MA 02115 


Curriculum vitae.
These slides are released under
Creative Commons License AttributionNoncommercialNo Derivative Works 3.0 United States. Also, let me know if you use them.
More slides can be found in
this directory.
I am currently recording my algorithms and theory of computation lectures. You can watch the videos on this Youtube channel.
Special topics in complexity theory Fall 2017.


M.S. Algorithms
Fall 2012, Summer 2015, Spring 2016, Spring 2017, sections 1 and 2.

Theory of
Computation
Fall 2010,
Fall 2011 ,
Spring 2012 ,
Fall 2012,
Spring 2014, Fall 2016.

Ph.D. (core) Theory of
Computation
Spring 2010,
Spring 2011,
Spring 2012,
Spring 2013,
Spring 2014.

Ph.D. (core) Advanced Algorithms
Fall 2008, Fall 2009, Fall 20013. 
Gems of Theoretical Computer Science Spring 2009. 
Papers
The coin problem for product tests
With Chin Ho Lee
To appear in ACM Trans. Computation Theory
Document
Local Expanders
With Avi Wigderson
To appear in Computational Complexity
Document
Bounded independence plus noise fools products
With Elad Haramaty and Chin Ho Lee
To appear in SIAM J. on Computing
Preliminary version in Conf. on Computational Complexity (CCC), 2017
Document
Blocksymmetric polynomials correlate with parity better than symmetric
With Frederic Green and Daniel Kreymer
Computational Complexity, vol. 26, num. 2, pp. 323364, 2017
Document Slides Code
Some limitations of the sum of smallbias distributions
With Chin Ho Lee
Theory of Computing, vol. 13, 2017
Document
The multiparty communication complexity of interleaved group products
With W. T. Gowers
To appear in SIAM J. on Computing
Preliminary version in IEEE Symp. on Foundations of Computer Science (FOCS), 2016
FOCS Special Issue
Slides of talk given at a 2017 workshop on additive combinatorics
Document Slides
Bounded independence vs. moduli
With Ravi Boppana and Johan Hastad and Chin Ho Lee
In Workshop on Randomization and Computation (RANDOM), 2016
Document
Bounded indistinguishability and the complexity of recovering secrets
With Andrej Bogdanov and Yuval Ishai and Christopher Williamson
In Int. Cryptology Conf. (CRYPTO), 2016
Document
Quadratic maps are hard to sample
ACM Trans. Computation Theory, vol. 8, num. 4, 2016
Document
Local reductions
With Hamid Jahanjou and Eric Miles
To appear in Information and Computation
Preliminary version in Coll. on Automata, Languages and Programming (ICALP), 2015
ICALP Special issue
Video of talk given at the Simons institute in 2015
Document Slides
The communication complexity of interleaved group products
With W. T. Gowers
In ACM Symp. on the Theory of Computing (STOC), 2015
Video of talk given at the FOCS 2014 workshop on higherorder Fourier analysis
Document
On Randomness Extraction in AC0
With Oded Goldreich and Avi Wigderson
In IEEE Conf. on Computational Complexity (CCC), 2015
Document Slides
3SUM, 3XOR, Triangles
With Zahra Jafargholi
Algorithmica, pp. 118, 2014
Video of talk given at the Simons institute in 2015
Document
Short PCPs with projection queries
With Eli BenSasson
In Coll. on Automata, Languages and Programming (ICALP), 2014
Document
Real advantage
With Alexander Razborov
ACM Trans. Computation Theory, vol. 5, num. 4, pp. 17, 2013
Document
Shielding circuits with groups
With Eric Miles
In ACM Symp. on the Theory of Computing (STOC), 2013
Document
On the complexity of information spreading in dynamic networks
With Chinmoy Dutta and Gopal Pandurangan and Rajmohan Rajaraman and Zhifeng Sun
In ACMSIAM Symp. on Discrete Algorithms (SODA), 2013
Document
The communication complexity of addition
Combinatorica, pp. 145, 2014
Preliminary version in ACMSIAM Symp. on Discrete Algorithms (SODA), 2013
Document Slides
Extractors for Turingmachine sources
In Workshop on Randomization and Computation (RANDOM), 2012
Document Slides
Substitutionpermutation networks, pseudorandom functions, and natural proofs
With Eric Miles
J. of the ACM, vol. 62, num. 6, 2015
Preliminary version in Int. Cryptology Conf. (CRYPTO), 2012
Document
Tight bounds on computing errorcorrecting codes by boundeddepth circuits with arbitrary gates
With Anna Gal and Kristoffer Arnsfelt Hansen and Michal Koucky and Pavel Pudlak
IEEE Transactions on Information Theory, vol. 59, num. 10, pp. 66116627, 2013
Preliminary version in ACM Symp. on the Theory of Computing (STOC), 2012
Document Slides
Extractors for circuit sources
SIAM J. on Computing, vol. 43, num. 2, pp. 355972, 2014
Preliminary version in IEEE Symp. on Foundations of Computer Science (FOCS), 2011
FOCS Special Issue
Document Slides
On beating the hybrid argument
With Bill Fefferman and Ronen Shaltiel and Christopher Umans
Theory of Computing, vol. 9, pp. 809843, 2013
Preliminary version in ACM Innovations in Theoretical Computer Science conf. (ITCS), 2012
Document
Randomness buys depth for approximate counting
Computational Complexity, vol. 23, num. 3, pp. 479508, 2014
Preliminary version in IEEE Symp. on Foundations of Computer Science (FOCS), 2011
Document Slides
On the complexity of constructing pseudorandom functions (especially when they don't exist)
With Eric Miles
J. of Cryptology, pp. 124, 2013
Preliminary version 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
Boundeddepth circuits cannot sample good codes
With Shachar Lovett
Computational Complexity, vol. 21, num. 2, pp. 245266, 2012
Preliminary version in IEEE Conf. on Computational Complexity (CCC), 2011
CCC Special issue
Document
The complexity of distributions
SIAM J. on Computing, vol. 41, num. 1, pp. 191218, 2012
Preliminary version in 51th IEEE Symp. on Foundations of Computer Science (FOCS), 2010
Subsumes the manuscript ``Are all distributions easy?''
Document Slides Video
Cellprobe lower bounds for succinct partial sums
With Mihai Patrascu
In 21th ACMSIAM 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. 34413462, 2010
Preliminary version in 50th IEEE Symp. on Foundations of Computer Science (FOCS), 2009
This paper in particular shows that the centrallimit theorem holds even for variables that are only kwise independent.
Document Slides
Bitprobe lower bounds for succinct data structures
SIAM J. on Computing, vol. 41, num. 6, pp. 1593?1604, 2012
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. 120, 2009
Preliminary version in 12th Workshop on Randomization and Computation (RANDOM), 2008
Document
The sum of d smallbias generators fools polynomials of degree d
Computational Complexity, vol. 18, num. 2, pp. 209217, 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. 31223154, 2010
Preliminary version in 40th ACM Symp. on the Theory of Computing (STOC), 2008
Document Slides
Oneway multiparty communication lower bound for pointer jumping with applications
With Avi Wigderson
Combinatorica, vol. 29, num. 6, pp. 719743, 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. 24642486, 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 polynomials and protocols
With Avi Wigderson
Theory of Computing, vol. 4, pp. 137168, 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. 337375, 2009
Preliminary version in IEEE Conf. on Computational Complexity (CCC), 2007
Document Slides
Pseudorandom Bits for ConstantDepth Circuits with Few Arbitrary Symmetric Gates
SIAM J. on Computing, vol. 36, num. 5, pp. 13871403, 2007
Preliminary version in 20th IEEE Conf. on Computational Complexity (CCC), 2005
SIAM Student Paper Prize
Document Slides
On Constructing Parallel Pseudorandom Generators from OneWay Functions
In 20th IEEE Conf. on Computational Complexity (CCC), 2005
Document Slides
ConstantDepth 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. 903931, 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. 34, pp. 147188, 2004
Preliminary version in IEEE Conf. on Computational Complexity (CCC), 2003
Document Slides
Eunifiability via Narrowing
In 7th Italian Conference on Theoretical Computer Science (ICTCS), 2001
Document Slides
Challenges in computational lower bounds
SIGACT News, Open Problems Column, vol. 48, num. 1, 2017
Document
Selected Results in Additive Combinatorics: An Exposition
Theory of Computing Library, Graduate Surveys series, vol. 3, pp. 115, 2011
Document
On the power of smalldepth computation
Foundations and Trends in Theoretical Computer Science, vol. 5, num. 1, pp. 172, 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
Special topics in complexity theory
Manuscript, 2017
Lecture notes of the class taught at Northeastern University
Document
More on bounded independence plus noise: Pseudorandom generators for readonce polynomials
With Chin Ho Lee
Manuscript, 2017
Document
A sampling lower bound for permutations
Manuscript, 2017
Document
Succinct and explicit circuits for sorting and connectivity
With Hamid Jahanjou and Eric Miles
Manuscript, 2014
Document
On a special case of rigidity
With Rocco A. Servedio
Manuscript, 2012
Document
What do humans perceive in asset returns?
With Jasmina Hasanhodzic and Andrew Lo
Manuscript, 2011
Play the game
Press coverage: Financial Times (link), MIT Technology Review
In Northern Finance Association (NFA), 2012
In Southern Economic Association (SEA), 2012
Document
From RAM to SAT
With NEU
Manuscript, 2012
Document
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
Visitor:  Yevgeniy Dodis (Spring and Summer 2013) 



Postdoc:  Elad Haramaty (Fall 2014  Summer 2016). First job: Postdoc at Harvard. 
 Chinmoy Dutta (partial mentoring, January 2011  January 2013). First job: Twitter Engineering. 



Ph. D.: 
Xuangui Huang (Fall 2017present) 
 Chin Ho Lee (Fall 2013present) 

Tanay Mehta (Summer 2016Summer 2017)


Hamid Jahanjou (Fall 2011Summer 2014), then worked with Rajmohan Rajaraman

 Zahra Jafargholi (Fall 2011Summer 2013), then worked with Daniel Wichs. First job: Postdoc at Aarhus University. 

Eric Miles (Fall 2008Spring 2014). First job: Postdoc at UCLA.





M. S.:  Dolphy Fernandes (Summer 2009) 



B. S.:  Sky O'Mara (Summer 2009) 
 Daniel Kreymer (various intervals during 20092012). First job: Amazon 
Blah (Bibtex to LaTeX and HTML).
The bibliographies in this page and in my cv are both generated from a bib file (sample) using
this 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.
Flexiblemathdisplay redefines \[ \] to automatically switch between equation, multline*, etc.
Theomac, to restate theorems.
Bibspacing, to remove spaces between bibliographic entries.
58th Annual IEEE Symposium on
Foundations of Computer Science
(FOCS 2017).
ACMSIAM Symposium on Discrete Algorithms (SODA
2014).
28th IEEE Conference on Computational Complexity (CCC
2013).
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).
Black Viper
Videogame produced and distributed throughout Europe by NEO Software Productions GmbH, Germany, 1996.
Longplay
Press coverage
Compressione dei suoni
Amigamagazine, Anno 7, Ottobre 1994
Paper (in Italian)
Nathan Never
Videogame produced by GENIAS and distributed in Italy by Softel, Rome, Italy, 1992
Longplay
Press coverage
I coded up the game in assembly when I was 14.
Bonus
How I looked back then.
My mother and I write fiction together. Our works have a philosophical/mathematical bent,
and touch on topics such as cryptography, paradoxes, randomness, and the P vs. NP problem. We write in Italian, but we are slowly translating some works into English. As of now, only one tale is available for download in English:
The Tournament
Tale
Next are some of our works in Italian, with something more available for download. More information on our writing process is here.
Libro
Racconti
The Northeastern Computer Science building towers over the adjacent Back Bay Fens.
Some pictures of my wedding.