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
Address: 440 Huntington Ave, #246WVH, Boston, MA 02115 map

Curriculum vitae [PDF] (version of November 2009).

Scroll down to: Classes, Papers, Surveys, Other.


Action items

Play ARORA.

Classes

Theory of Computation (undergraduate), CS 3800, Fall 2010.
Theory of Computation (graduate), CS 7805, Spring 2010.
Advanced Algorithms, CS G7800, Fall 2009.
Gems of Theoretical Computer Science, CS G399, Spring 2009.
Advanced Algorithms, CS G713, Fall 2008.

Papers

Bounded-depth circuits cannot sample good codes.
With Shachar Lovett.
Manuscript, 2010.
Paper [PDF].

The complexity of distributions.
To appear in 51st IEEE Symposium on Foundations of Computer Science (FOCS), 2010.
Paper [PDF].
Subsumes the manuscript ``Are all distributions easy?'' manuscript [PDF]

Is it real, or is it randomized?: A financial Turing test.
With Jasmina Hasanhodzic and Andrew W. Lo.
Manuscript, 2010.
Paper [PDF]

On the power of small-depth computation.
Foundations and Trends in Theoretical Computer Science (FnT-TCS), Vol. 5: No 1, pp 1-72, 2009. (Invited survey, subsumes SIGACT 2009 survey)
Survey [PDF]

A computational view of market efficiency.
With Jasmina Hasanhodzic and Andrew W. Lo.
Manuscript, 2009.
Paper [PDF]

Cell-probe lower bounds for succinct partial sums.
With Mihai Patrascu.
In ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010.
Paper [PDF]
A related Paper [PDF]
Slides from seminar talk on lower bounds for succinct data structures Slides [PDF] Slides [ODP]

Bounded independence fools halfspaces.
With Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, and Rocco Servedio.
SIAM Journal on Computing, 39(8): 3441-3462, 2010.
In 50th IEEE Symposium on Foundations of Computer Science (FOCS), 2009.
Paper [PDF]
Slides from seminar talk Slides [PDF] Slides [ODP] Slides [PPT]

Bit-probe lower bounds for succinct data structures.
To appear in SIAM Journal on Computing, STOC special issue.
In 41st ACM Symposium on Theory of Computing (STOC), 2009.
Paper [PDF]
Slides from conference talk Slides [PDF] Slides [ODP].

Improved separations between nondeterministic and randomized multiparty communication.
With Matei David and Toniann Pitassi.
Transactions on Computation Theory Vol. 1: No 2, pp 1--20, 2009.
In International Workshop on Randomization and Computation (RANDOM), 2008.
Paper [PDF]

The sum of d small-bias generators fools polynomials of degree d.
Computational Complexity, 18(2): 209-217, 2009, CCC special issue.
In 23th IEEE Conference on Computational Complexity (CCC), 2008. Best Paper Award.
Paper [PDF]
Slides from talk given at Theory Day Slides [PDF] Slides [PPT]

Hardness amplification proofs require majority.
With Ronen Shaltiel.
SIAM Journal on Computing SIAM J. Comput. Vol. 39, Issue 7, pp 3122-3154, 2010.
In 40th ACM Symposium on Theory of Computing (STOC), 2008.
Paper [PDF]
Slides from conference talk Slides [PDF] Slides [PPT]; from seminar talk Slides [PDF] Slides [PPT]

One-way multi-party communication lower bound for pointer jumping with applications.
With Avi Wigderson.
Combinatorica, Vol. 29, No 6, pp 719-743, 2009. Invited to FOCS Special Issue.
In 48th IEEE Symposium on Foundations of Computer Science (FOCS), 2007.
Paper [PDF] Paper [DVI]
Slides from conference talk Slides [PDF] Slides [PPT]

Pseudorandom bits for polynomials.
With Andrej Bogdanov.
SIAM Journal on Computing, Vol. 39, Issue 6, pp 2464-2486, 2010; FOCS Special Issue.
In 48th IEEE Symposium on Foundations of Computer Science (FOCS), 2007.
Paper [PDF]

Norms, XOR lemmas, and lower bounds for GF(2) polynomials and multiparty protocols.
With Avi Wigderson.
Theory of Computing 4:137-168, 2008.
In 22th IEEE Conference on Computational Complexity (CCC), 2007.
Paper [PDF]
Slides from conference talk Slides [PDF] Slides [PPT]
The results on polynomials appeared also in the report
"New correlation bounds for GF(2) polynomials using Gowers uniformity"
Electronic Colloquium on Computational Complexity, TR06-097, 2006.
Report [PS] Report [PDF]

The complexity of hardness amplification and derandomization.
Ph.D. Thesis, Harvard University, 2006.
Thesis [PS] Thesis [PDF]
Slides from defense talk Slides [PPT] Slides [PDF]

On approximate majority and probabilistic time.
Journal Computational Complexity, 18(3):337-375, 2009.
In 22th IEEE Conference on Computational Complexity (CCC), 2007.
Paper [PS] Paper [PDF]
Slides from conference talk Slides [PDF] Slides [PPT]; from seminar talk Slides [PPT] Slides [PDF]

Pseudorandom bits for constant-depth circuits with few arbitrary symmetric gates.
SIAM Journal on Computing, 36(5):1387-1403, 2007. SIAM Student Paper Prize. Link.
In 20th IEEE Conference on Computational Complexity (CCC), 2005.
Paper [PS] Paper [PDF]
Slides from conference talk Slides [PPT]; from seminar talk Slides [PPT]

On constructing parallel pseudorandom generators from one-way functions.
In 20th IEEE Conference on Computational Complexity (CCC), 2005.
Paper [PS] Paper [PDF]
Slides from conference talk Slides [PPT]

Constant-depth circuits for arithmetic in finite fields of characteristic two.
With Alex Healy.
In 23rd International Symposium on Theoretical Aspects of Computer Science (STACS), 2006.
Paper [PS] Paper [PDF] ©Springer-Verlag

Using nondeterminism to amplify hardness.
With Alex Healy and Salil Vadhan.
SIAM Journal on Computing , 34(4):903-931, 2006, STOC Special Issue.
In 36th ACM Symposium on Theory of Computing (STOC), 2004.
Paper [PS] Paper [PDF]
Conference version [PS] Conference version [PDF]
Slides from conference talk Slides [PPS]; from seminar talk Slides [PPS]

The complexity of constructing pseudorandom generators from hard functions.
Journal Computational Complexity, 13(3-4):147-188, 2004.
In 18th IEEE Conference on Computational Complexity (CCC), 2003.
Paper [PS] Paper [PDF]
Conference version [PS] Conference version [PDF]
Slides from conference talk Slides [PDF]

Fooling parity tests with parity gates.
With Dan Gutfreund.
In 8th International Workshop on Randomization and Computation (RANDOM), 2004.
Paper [PS] Paper [PDF]
Slides from conference talk Slides [PPT]

E-unifiability via narrowing.
In 7th Italian Conference on Theoretical Computer Science (ICTCS), 2001.
Paper [PS] Paper [PDF] ©Springer-Verlag
 

Surveys

Correlation bounds for polynomials over {0,1}.
ACM SIGACT news 40(1), 2009. (Invited survey.)
Paper [PDF]

Selected results in additive combinatorics: an exposition.
To appear in Theory of Computing , graduate surveys
Electronic Colloquium on Computational Complexity, Report TR07-103, 2007.
Paper [DVI] Paper [PDF]

Program committees

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

Commercial video games

Black Viper, produced and distributed throughout Europe by NEO Software Productions GmbH, Germany, 1996.
Some images and a video of the game.

Nathan Never, produced by GENIAS and distributed in Italy by Softel, Rome, Italy, 1992.
Some images and a video of the game.



Some pictures of my wedding.

A book of tales written with my mother.