Emanuele Viola

Associate 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

During 2014/2015 I am on sabbatical at Harvard University, in Maxwell Dworkin room 353.

Curriculum vitae.




Blog: Eliminate all formatting requirements (+ survival tip)


Communication Complexity in Banff


The sandwich revolution: Behind the paper

Local reductions: Behind the paper

Only papers on the arXiv can be submitted for publication

Theory out of despair




Below: teaching, including slides,

papers, including surveys,

research team, including students,

some posts about my research,

more, including from the Nineties, LaTeX resources, Etc.


Teaching

Classes

M.S. Algorithms Fall 2012.
Theory of Computation Fall 2010, Fall 2011 , Spring 2012 , Fall 2012, Spring 2014.
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.
Ph.D. Gems of Theoretical Computer Science Spring 2009.

Slides

Theory of computation: introduction.
mathematical background.
regular languages and finite automata.
context-free languages.
computability and Turing machines.
Kolmogorov complexity.
complexity, P and NP.
Algorithms: introduction and background.
big Oh; bubble and counting sort.
divide and conquer.
dynamic programming and greedy algorithms.
data structures.
graph algorithms.


More slides can be found in this directory.

Research

Preprints

Succinct and explicit circuits for sorting and connectivity
With Hamid Jahanjou and Eric Miles
Manuscript, 2014
Document  

Challenges in computational lower bounds
Manuscript, 2013
Document  

Local reductions
With Hamid Jahanjou and Eric Miles
Manuscript, 2013
Document  Slides  

Block-symmetric polynomials correlate with parity better than symmetric
With Frederic Green and Daniel Kreymer
Manuscript, 2012
Document  Slides  Code  

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  

Papers

3SUM, 3XOR, Triangles
With Zahra Jafargholi
To appear in Algorithmica
Document  

Short PCPs with projection queries
With Eli Ben-Sasson
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 ACM-SIAM Symp. on Discrete Algorithms (SODA), 2013
Document  

The communication complexity of addition
To appear in Combinatorica
Preliminary version in ACM-SIAM Symp. on Discrete Algorithms (SODA), 2013
Document  Slides  

Extractors for Turing-machine sources
In Workshop on Randomization and Computation (RANDOM), 2012
Document  Slides  

Substitution-permutation networks, pseudorandom functions, and natural proofs
With Eric Miles
In Int. Cryptology Conf. (CRYPTO), 2012
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
IEEE Transactions on Information Theory, vol. 59, num. 10, pp. 6611-6627, 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. 355-972, 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. 809-843, 2013
Preliminary version in ACM Innovations in Theoretical Computer Science conf. (ITCS), 2012
Document  

Randomness buys depth for approximate counting
To appear in Computational Complexity
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
To appear in J. of Cryptology
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  

Bounded-depth circuits cannot sample good codes
With Shachar Lovett
Computational Complexity, vol. 21, num. 2, pp. 245-266, 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. 191-218, 2012
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
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. 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  

Surveys and my Ph.D. thesis

Selected Results in Additive Combinatorics: An Exposition
Theory of Computing Library, Graduate Surveys series, vol. 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  

Notes

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  

Research team

Visitor: Yevgeniy Dodis (Spring and Summer 2013)
Postdoc:Elad Haramaty (Fall 2014 - )
Chinmoy Dutta (partial mentoring, January 2011 - January 2013)
Ph. D.:Eric Miles (Fall 2008-Spring 2014). First job: postdoc at UCLA.
Hamid Jahanjou (Fall 2011-present)
Zahra Jafargholi (Fall 2011-present)
Chin Ho Lee (Fall 2013-present)
M. S.:Dolphy Fernandes (Summer 2009)
Undergrad:Sky O'Mara (Summer 2009)
Daniel Kreymer (various intervals during 2009-2012). First job: Amazon

Some posts about my research

Lance Fortnow here here here
Oded Goldreich here
Timothy Gowers here
Noam Nisan here
Ryan O'Donnell here
Mihai Patrascu here
Terence Tao here
Luca Trevisan here
Suresh Venkatasubramanian here
Financial Times here (link)
MIT Technology Review here

More

LaTeX resources

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.

Program committees

ACM-SIAM 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).

From the Nineties

Black Viper
Videogame 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
Videogame 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.)
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.