In’Tro Emanuele Natale

Emanuele Natale

  • Title: “On the Random Subset Sum Problem and Neural Networks”
  • When: May 30, 2023 — 13:30
  • Where: online seminar In’Tro
  • Abstract: The Random Subset Sum Problem (RSSP) is a fundamental problem in mathematical optimization, especially in understanding the statistical behavior of integer linear programs.
    Recently, the theory related to this problem has also found applications in theoretical machine learning, providing key tools for proving the Strong Lottery Ticket Hypothesis (SLTH) for dense neural network architectures. In this talk, I will give a brief overview of this research direction and present my recent joint work that pushes the application of RSSP further by providing a proof of the SLTH for convolutional neural networks.

In'Tro Emanuele Natale

On Computer Science Conferences and their Temporal Evolution

Pierluigi Crescenzi

  • Speaker: Pierluigi Crescenzi, GSSI, University of L’Aquila
  • Title: On Computer Science Conferences and their Temporal Evolution — (watch the video)
  • When: October 6, 2022 — 14:00
  • Where: Campus SophiaTech, Forum F201, and online
  • Abstract: In this talk we will present the evolution of computer science conferences over the past 50 years, by analysing data from the DBLP database.

    Our goal was to try and understand the evolution of each conference throughout its history, the ebb and flow in the popularity of its research areas, and the centrality of its authors, as measured by several metrics from network science, amongst other topics. In particular we tried to answer several different questions.
    How did the conference evolve in terms of its number of authors, number of papers, and number of collaboration sizes? How much the conference was open to new entries? Did the percentage of female authors change over time? Were different topics more popular in different periods? If the conference covers a broad spectrum of research areas, did the percentage of each area change over time? Did the conference present the small-world phenomenon? What are the most influential authors of the conference?

    The tentative answer to these questions was given by either analysing only one conference at a time or by performing a comparative analysis between a specific set of conferences. We will also briefly present the web-based resources that accompany this talk. It goes without saying that our analysis has to be taken with a huge pinch of salt and is only meant to be food for thought for the community.

  • Short Bio: Pierluigi Crescenzi is a professor at the Gran Sasso Science Institute. Before joining GSSI, he has been researcher at the University of L’Aquila, and professor at the University of Rome, Florence, and Paris. He has taught in basically every field of computer science. He is the author of more than 130 scientific publications in the field of algorithm theory and its applications. He is co-author of 5 university textbooks, including 2 in English, and a popular Italian book. He is member of the editorial board of JCSS. He is co-author of the NP optimisation compendium, which is still widely cited. He is co-inventor of a US Patent on an IP address lookup algorithm and he has been a member of the steering committee of the COST 295 DYNAMO action. His current research is mostly focus on the analysis of complex networks and, more specifically, of temporal networks.

C@fé-in par Nicolas Nisse: Jouons un peu sur un échiquier (sans jouer aux échecs)

C@fé-in Nicolas Nisse

  • Quand: 8 juillet 2021 à 13h, en replay sur https://www.youtube.com/watch?v=uOW3HpsTuGY.
  • Intrigue: Dans ce Café-in, vous allez apprendre deux jeux/énigmes amusant(e)s (j’espère) auxquels vous pourrez jouer avec vos familles et amis.
    1. Etant donné un échiquier, sauriez vous couvrir toutes ses cases à l’aide de dominos, exceptées celles de deux coins opposés ?
    2. Considérons un échiquier classique (8 cases par 8) dont chaque case peut être soit saine soit infectée. Supposez que, si au moins 2 des 4 voisins d’une case infectée sont saines, alors la case infectée devient saine. Quel est le nombre minimum de cases qui doivent être saines initialement pour éradiquer complètement l’infection de l’échiquier ? Vous pouvez tester ce jeu ici : https://scratch.mit.edu/projects/517390361/

    A travers ces jeux, nous discuterons de questions importantes dans le travail des chercheurs comme « y a t-il une solution ? », « combien y a-t-il de solutions ? », « est-ce que cette solution est optimale ? » … Précisément, je répondrai à ces questions dans le cas des deux jeux proposés en présentant de très belles preuves de la littérature (oui, des preuves peuvent être « belles »: élégantes et simples). Pour finir, je présenterai une généralisation du second problème et montrerai brièvement ses relations avec le jeu de la vie de John Conway qui, malgré des règles très simples, permet de simuler n’importe quel ordinateur.

  • Biographie: Nicolas Nisse est CR Inria dans l’équipe COATI. Ses sujets de recherche portent sur l’algorithmique des graphes avec des applications dans les réseaux de télécommunication, routiers, sociaux… En particulier, son travail s’appuie sur la théorie des jeux combinatoires dans les graphes. Nicolas Nisse est ingénieur Supélec, a effectué sa thèse à l’université Paris-Sud 11 puis un postdoc à l’université du Chili (Santiago, Chili) et un postdoc dans l’équipe Mascotte (devenue COATI). Il est également membre de Terra Numerica.
  • En savoir plus sur MASTIC et C@fé-in.

Links to online seminars

Several websites are currently collecting online talks. You can find a list of some of them below.

You can also have a look to formerly recorded seminars

Seminar by Robert E. Tarjan: Zip Trees

Robert E. Tarjan

  • Speaker: Robert E. Tarjan, Department of Computer Science, Princeton University and Intertrust Technologies
  • Title: Zip Trees
  • When: June 29, 2018 — 14:00
  • Where: I3S, Salle de conférence 007
  • Abstract: This talk will present the zip tree, a simple and efficient type of binary search tree. Zip trees use randomization to achieve balance. A zip tree can be viewed as a binary-tree representation of a skip list or as a variant of a treap. Insertion and deletion avoid the multiplicity of cases that arise in standard balanced trees. Zip trees can be adapted to exploit biased access distributions. Their simplicity makes them promising for concurrent use.

  • Short Bio: Since 1985, Robert E. Tarjan has been the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He previously held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, Intertrust Technologies, HP, and Microsoft. Among other honors, he received the Nevanlina Prize in Informatics, given by the International Mathematical Union, in 1982, and the A.C.M. Turing Award in 1986. He is a member of the National Academy of Sciences and the National Academy of Engineering, and a Fellow of the American Philosophical Society and the American Academy of Arts and Sciences. He has published over 250 papers, mostly in the areas of the design and analysis of data structures and graph and network algorithms.

  • See the thread on Twitter

Concurrent Disjoint Set Union

Robert E. Tarjan

  • Speaker: Robert E. Tarjan, Department of Computer Science, Princeton University and Intertrust Technologies
  • Title: Concurrent Disjoint Set Union — (watch the video)
  • When: December 9, 2016 — 10:30
  • Where: Inria Sophia Antipolis, amphi Kahn
  • Abstract: The disjoint set union problem is a classical problem in data structures with a simple and efficient sequential solution that has a notoriously complicated analysis. One application is to find strongly connected components in huge, implicitly defined graphs arising in model checking. In this application, the use of multiprocessors has the potential to produce significant speedups. We explore this possibility. We devise and analyze concurrent versions of standard sequential algorithms that use single and double compare-and-swap primitives for synchronization, making them wait-free. We obtain work bounds that grow logarithmically with the number of processors, suggesting the possibility of significant speedup in practice. This is ongoing joint work with Siddhartha Jayanti, an undergraduate at Princeton.

  • Short Bio: Since 1985, Robert E. Tarjan has been the James S. McDonnell Distinguished University Professor of Computer Science at Princeton University. He previously held academic positions at Cornell, Berkeley, Stanford, and NYU, and industrial research positions at Bell Labs, NEC, Intertrust Technologies, HP, and Microsoft. Among other honors, he received the Nevanlina Prize in Informatics, given by the International Mathematical Union, in 1982, and the A.C.M. Turing Award in 1986. He is a member of the National Academy of Sciences and the National Academy of Engineering, and a Fellow of the American Philosophical Society and the American Academy of Arts and Sciences. He has published over 250 papers, mostly in the areas of the design and analysis of data structures and graph and network algorithms.