This is a past event
  • Open to the Public
Sampling Binary Matrices with Hard Constraints: Algorithms and Impossibility Results

Given an observed binary matrix, generating other matrices that share some properties with the observed one is a key step for performing statistical hypothesis tests on results obtained from the observed matrix. The set of properties to be maintained defines a sample space of matrices, and the key computational question is how to draw samples from this space according to a user-specified distribution. We show that, for some sets of properties, there are efficient Markov-chain-Monte-Carlo algorithms to generate these samples, while in other cases such algorithms cannot exist. This talk is based on joint works with Giulia Preti and Gianmarco De Francisci Morales from the CentAI Institute.

Bio: Matteo Riondato is an associate professor of computer science at Amherst College, and a visiting faculty at Brown University. Previously, he was a research scientist at Two Sigma. His research focuses on algorithms for data mining and machine learning. He received a NSF CAREER award to work on statistically-sound knowledge discovery from data. His works were recognized with best-of-conference awards at many data mining conferences.

  • 4:15 p.m.: Refreshments in Seeley Mudd 206
  • 4:30 p.m.: Talk in Seeley Mudd 206 
  • Masks are welcomed but not required.

Contact Info

Nicholas Horton
(413) 542-5655
Please call the college operator at 413-542-2000 or e-mail if you require contact info


The Seeley Mudd Building is located at 31 Quadrangle Drive on the Amherst College campus.