Emanuele “Manu” Viola

Professor

Khoury College of Computer Sciences
Northeastern University
Theory of computation at Northeastern University.

Email:	mathematicsoftheimpossible@gmail.com
Office:	440 Huntington Av., #338 West Village H (WVH)
Mail:	360 Huntington Av., #202 WVH
	Boston, MA 02115

Curriculum vitae.

Mathematics of the Impossible

The Complexity of Computation

Click to download

An iconoclastic book that overhauls computational complexity theory, featuring recent breakthroughs, neglected gems, and simpler expositions of the classics.

Blog: Thoughts

Pseudorandom post:

Is the computer ever slow?

I want to know why.

But I am not interested in explanations grounded in human choice.

I want to know if there is an intrinsic, mathematical reason why some tasks take longer than others.

Below:

teaching, including videos and slides,

papers, including surveys and preprints,

research team, including students,

some posts about my research,

and more, including from the Nineties and fiction.

Teaching

Slides

These slides are released under Creative Commons License Attribution-Noncommercial-No Derivative Works 3.0 United States. Also, let me know if you use them.

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; big Oh; bubble and counting sort, annotated.
	divide and conquer, annotated.
	dynamic programming and greedy algorithms.
	data structures.
	graph algorithms.
	linear programming.
	flow.
	NP-hardness reductions.
	approximation algorithms.

More slides can be found in this directory.

Videos

Videos for an online course on algorithms.

Videos for an online course on theory of computation.

On my Youtube channel you can find the videos above and others.

Select classes

Complexity theory, Spring 2023, Textbook.

Special topics in complexity theory Fall 2017.

Gems of Theoretical Computer Science Spring 2009.

Online class on theory of computation

Online class on algorithms

Research

Papers

Communication complexity of pointer chasing via the fixed-set lemma
To appear in Theory of Computing
Document

Pseudorandom bits for non-commutative programs
With Chin Ho Lee
In Conf. on Computational Complexity (CCC), 2025
Document

Boosting uniformity in quasirandom groups: fast and simple
With Harm Derksen and Chin Ho Lee
In IEEE Symp. on Foundations of Computer Science (FOCS), 2024
Document

Pseudorandomness, symmetry, smoothing: I
With Harm Derksen and Peter Ivanov and Chin Ho Lee
In Conf. on Computational Complexity (CCC), 2024
Document

Quasirandom groups enjoy interleaved mixing
With Harm Derksen
Discrete Analysis, 2023
Document

On correlation bounds against polynomials
With Peter Ivanov and Liam Pavlovic
In Conf. on Computational Complexity (CCC), 2023
Document

New sampling lower bounds via the separator
In Conf. on Computational Complexity (CCC), 2023
Document  Slides

Efficient resilient functions
With Peter Ivanov and Raghu Meka
In ACM-SIAM Symp. on Discrete Algorithms (SODA), 2023
Document

Fooling polynomials using invariant theory
With Harm Derksen
In IEEE Symp. on Foundations of Computer Science (FOCS), 2022
Document

Affine extractors and AC0-Parity
With Xuangui Huang and Peter Ivanov
In Workshop on Randomization and Computation (RANDOM), 2022
Document

Pseudorandom bits and lower bounds for randomized Turing machines
Theory of Computing, vol. 18, num. 10, pp. 1--12, 2022
Document

On Hardness Assumptions Needed for ``Extreme High-End'' PRGs and Fast Derandomization
With Ronen Shaltiel
In ACM Innovations in Theoretical Computer Science conf. (ITCS), 2022
Document

Mixing in non-quasirandom groups
With W. T. Gowers
In ACM Innovations in Theoretical Computer Science conf. (ITCS), 2022
Document  Video

Approximate Degree-Weight and Indistinguishability
With Xuangui Huang
To appear in ACM Trans. Computation Theory
Document

Fourier growth of structured F2-polynomials and applications
With Jaroslaw Blasiok and Peter Ivanov and Yaonan Jin and Chin Ho Lee and Rocco A. Servedio
In Workshop on Randomization and Computation (RANDOM), 2021
Document

Fourier conjectures, correlation bounds, and Majority
In Coll. on Automata, Languages and Programming (ICALP), 2021
Document  Video

Average-case rigidity lower bounds
With Xuangui Huang
In Computer Science Symp. in Russia (CSR), 2021
Document

New lower bounds for probabilistic degree and AC0 with parity gates
To appear in Theory of Computing
Document

AC0 unpredictability
To appear in ACM Trans. Computation Theory
Document

More on bounded independence plus noise: Pseudorandom generators for read-once polynomials
With Chin Ho Lee
Theory of Computing, vol. 16, pp. 1--50, 2020
Document

Lower bounds for data structures with space close to maximum imply circuit lower bounds
Theory of Computing, vol. 15, pp. 1-9, 2019
Document

Sampling lower bounds: boolean average-case and permutations
SIAM J. on Computing, vol. 49, num. 1, 2020
Document  Slides

How to Store a Random Walk
With Omri Weinstein and Huacheng Yu
In ACM-SIAM Symp. on Discrete Algorithms (SODA), 2020
Document

Constant-error pseudorandomness proofs from hardness require majority
ACM Trans. Computation Theory, vol. 11, num. 4, pp. 19:1--19:11, 2019
Document

What do humans perceive in asset returns?
With Jasmina Hasanhodzic and Andrew Lo
Journal of Portfolio Management, vol. 45, num. 4, pp. 49-60, 2019
Press coverage: Financial Times (link), MIT Technology Review
In Northern Finance Association (NFA), 2012
In Southern Economic Association (SEA), 2012
Ten years after its deployment, the game was taken out of commission in 2018 due to repeated attacks to the server
Document

Indistinguishability by adaptive procedures with advice, and lower bounds on hardness amplification proofs
With Aryeh Grinberg and Ronen Shaltiel
In IEEE Symp. on Foundations of Computer Science (FOCS), 2018
Document

Revisiting Frequency Moment Estimation in Random Order Streams
With Vladimir Braverman and David P. Woodruff and Lin F. Yang
In Coll. on Automata, Languages and Programming (ICALP), 2018
Document

The coin problem for product tests
With Chin Ho Lee
ACM Trans. Computation Theory, vol. 10, num. 3, 2018
Document

Local Expanders
With Avi Wigderson
Computational Complexity, vol. 27, num. 2, pp. 225-244, 2018
Document

Bounded independence plus noise fools products
With Elad Haramaty and Chin Ho Lee
SIAM J. on Computing, vol. 47, num. 2, pp. 295-615, 2018
Preliminary version in Conf. on Computational Complexity (CCC), 2017
Document

Block-symmetric polynomials correlate with parity better than symmetric
With Frederic Green and Daniel Kreymer
Computational Complexity, vol. 26, num. 2, pp. 323-364, 2017
Document  Slides  Code

Some limitations of the sum of small-bias distributions
With Chin Ho Lee
Theory of Computing, vol. 13, 2017
Document

Interleaved group products
With W. T. Gowers
SIAM J. on Computing, vol. 48, num. 3, pp. 554--580, 2019
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
The journal version includes the results appearing in the STOC 2015 (below) and FOCS 2016 (doc, slides) conference versions
Document

Bounded Independence versus Symmetric Tests
With Ravi Boppana and Johan Hastad and Chin Ho Lee
ACM Trans. Computation Theory, vol. 11, num. 4, pp. 21:1--21:27, 2019
Preliminary version 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
Information and Computation, vol. 261, num. 2, 2018
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 higher-order 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. 1-18, 2014
Video of talk given at the Simons institute in 2015
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
Combinatorica, pp. 1-45, 2014
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
J. of the ACM, vol. 62, num. 6, 2015
Preliminary version 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
Computational Complexity, vol. 23, num. 3, pp. 479-508, 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. 1-24, 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

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 polynomials and 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

Non-abelian combinatorics and communication complexity
SIGACT News, Complexity Theory Column, vol. 50, num. 3, 2019
Invited survey
Document

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. 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

Preprints and notes

Mathematics of the impossible: The complexity of computation
Manuscript, 2023
Document

Resilient functions: Optimized, simplified, and generalized
With Peter Ivanov
Manuscript, 2024
Document

Pseudorandomness, symmetry, smoothing: II
With Harm Derksen and Peter Ivanov and Chin Ho Lee
Manuscript, 2024
Document

Correlation bounds against polynomials, a survey
Manuscript, 2022
Document

Special topics in complexity theory
Manuscript, 2017
Lecture notes of the class taught at Northeastern University
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

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:	Elena Grigorescu (Spring 2020)
	Yevgeniy Dodis (Spring and Summer 2013)



Postdoc:	Jad Silbak (Fall 2023 - )
	Elad Haramaty (Fall 2014 - Summer 2016) → Postdoc at Harvard.
	Chinmoy Dutta (partial mentoring, January 2011 - January 2013) → Twitter Engineering.



Ph. D.:	Dustin Lin (Fall 2023-)
	Peter Ivanov (Summer 2019-)
	Xuangui Huang (Fall 2017-Spring 2023)
	Chin Ho Lee (Fall 2013-Summer 2019) → Postdoc at Columbia → Postdoc at Harvard → Professor at North Carolina State University
	Tanay Mehta (partial advising)
	Hamid Jahanjou (partial advising)
	Zahra Jafargholi (partial advising) → Postdoc at Aarhus University.
	Eric Miles (Fall 2008-Spring 2014) → Postdoc at UCLA → Google.




M. S.:	Dolphy Fernandes (Summer 2009)



B. S.:	Liam Pavlovic (Summer 2020 -- Fall 2020) → Ph.D. at Northeastern University
	Daniel Kreymer (various intervals during 2009-2012). → Amazon
	Sky O'Mara (Summer 2009)

Some posts about my research

Lance Fortnow	here	here	here
Oded Goldreich	here	here
Timothy Gowers	here
Noam Nisan	here
Ryan O'Donnell	here
Mihai Patrascu	here
Property Testing Review	here
Terence Tao	here
Luca Trevisan	here
Suresh Venkatasubramanian	here
Il fatto quotidiano	in italiano (in English)
Financial Times	here (link)
MIT Technology Review	here

Talks

Correlation bounds and all that.
Mixing in groups.
Why do lower bounds stop just before proving "major results?".
Video of 2018 talk on the complexity of distributions here.
More slides of my talks are here.

LaTeX resources

L2w (A Latex/Lyx to Wordpress converter). See the blog post.

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.

Editorial boards and program committees

Editorial board, SIAM Journal on Computing (SICOMP) 2019 -- .
Editorial board, ACM Transactions on Computation Theory (TOCT) 2015 -- 2023.
Scientific board, Electronic Colloquium on Computational Complexity (ECCC) 2009 -- .

ICALP 2025
RANDOM 2024
IEEE Symposium on Foundations of Computer Science (FOCS) 2022.
International Colloquium on Automata, Languages and Programming (ICALP) 2022.
Conference on Computational Complexity (CCC) 2021.
58th Annual IEEE Symposium on Foundations of Computer Science (FOCS) 2017.
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
All-tracks longplay!
Another longplay
Press coverage
Recent post
Another recent post
On my blog

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.

Fiction

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. More information on our writing process is here, also here. A 2024 interview is here. 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.

Libro

Codice Yetzirah Vincitore premio Altri Mondi 2008 Clicca qui per l'indice
	Montag Edizioni

Racconti

Manipura Premio Esescifi 2013
La ragazza che non sapeva contare Secondo classificato Trofeo RiLL 2012 Clicca qui per leggere!			Video della premiazione
Lo utilizzi come cane addestrato Clicca qui per leggere!	Regolamento
Il richiamo di Lilith Tra i vincitori di SFIDA 2010		Un video basato sul racconto.
Cielo stellato Tra i vincitori di SFIDA 2009
Codice Yetzirah Vincitore Trofeo RiLL 2007
Il torneo Vincitore Premio Alien 2001

The Northeastern Computer Science building towers over the adjacent Back Bay Fens.

Juggling small, big.

Ripface small, big.

Some pictures of my wedding.