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 |

Below: | teaching, including slides, |

papers, including surveys and preprints, | |

research team, including students, | |

some posts about my research, | |

more, including from the Nineties, LaTeX resources, etc. |

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

More slides can be found in this directory.

In ACM Symp. on the Theory of Computing (STOC), 2015

Video of talk given at the FOCS 2014 workshop on higher-order Fourier analysis

In IEEE Conf. on Computational Complexity (CCC), 2015

Document

Algorithmica, pp. 1-18, 2014

Document

In Coll. on Automata, Languages and Programming (ICALP), 2014

Document

ACM Trans. Computation Theory, vol. 5, num. 4, pp. 17, 2013

Document

In ACM Symp. on the Theory of Computing (STOC), 2013

Document

In ACM-SIAM Symp. on Discrete Algorithms (SODA), 2013

Document

Preliminary version in ACM-SIAM Symp. on Discrete Algorithms (SODA), 2013

Document Slides

Document Slides

In Int. Cryptology Conf. (CRYPTO), 2012

Document

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

Preliminary version in IEEE Symp. on Foundations of Computer Science (FOCS), 2011

FOCS Special Issue

Document Slides

Theory of Computing, vol. 9, pp. 809-843, 2013

Preliminary version in ACM Innovations in Theoretical Computer Science conf. (ITCS), 2012

Document

Preliminary version in IEEE Symp. on Foundations of Computer Science (FOCS), 2011

Document Slides

J. of Cryptology, pp. 1-24, 2013

Preliminary version in Theory of Cryptography Conf. (TCC), 2011

Document

Quantitative Finance, vol. 11, num. 7, 2011

Document

Computational Complexity, vol. 21, num. 2, pp. 245-266, 2012

Preliminary version in IEEE Conf. on Computational Complexity (CCC), 2011

CCC Special issue

Document

Preliminary version in 51th IEEE Symp. on Foundations of Computer Science (FOCS), 2010

Subsumes the manuscript ``Are all distributions easy?''

Document Slides Video

In 21th ACM-SIAM Symp. on Discrete Algorithms (SODA), 2010

A related Paper

Document Slides

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

Preliminary version in 41th ACM Symp. on the Theory of Computing (STOC), 2009

STOC Special Issue

Document Slides

ACM Trans. Computation Theory, vol. 1, num. 2, pp. 1--20, 2009

Preliminary version in 12th Workshop on Randomization and Computation (RANDOM), 2008

Document

Preliminary version in IEEE Conf. on Computational Complexity (CCC), 2008

Best paper award

Document Slides

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

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

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

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

Preliminary version in IEEE Conf. on Computational Complexity (CCC), 2007

Document Slides

Preliminary version in 20th IEEE Conf. on Computational Complexity (CCC), 2005

SIAM Student Paper Prize

Document Slides

Document Slides

In 23rd Symp. on Theoretical Aspects of Computer Science (STACS), 2006

Document

In 8thWorkshop on Randomization and Computation (RANDOM), 2004

Document Slides

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

Preliminary version in IEEE Conf. on Computational Complexity (CCC), 2003

Document Slides

Document Slides

Document

Invited survey, subsumes SIGACT 2009 survey

Document

Invited survey

Document

Document Slides

Manuscript, 2015

Document

Manuscript, 2014

Document

Document

Manuscript, 2013

Document Slides

Manuscript, 2012

Document Slides Code

Manuscript, 2012

Document

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

Manuscript, 2012

Document

Lecture notes aimed towards students lacking mathematical maturity

Document

Document

Lecture notes of the class taught at Northeastern University

Document

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 |

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 |

Flexiblemathdisplay redefines \[ \] to automatically switch between equation, multline*, etc.

Theomac, to restate theorems.

Bibspacing, to remove spaces between bibliographic entries.

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

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

I coded up the game in assembly when I was 14.

**Bonus**

How I looked back then.

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.