Closing workshop

In collaboration with a CNRS bilateral collaboration (PICS), a 2-day workshop will be organized December 7-8, 2017 at IRIF, Turing amphitheater. The program will be available soon.

  • 12/07, Day 1: Closing workshop on ANR project on algorithmic techniques for Restricted Data Access Models
  • 12/08, Day 2: 1st IQC-IRIF Workshop on Quantum Information Processing

Lectures at Collège de France

Claire Mathieu will give a sequence of lectures on Algorithms overlapping RDAM topics at Collège de France from November 28, 2017 to January 30, followed by a seminar every Tuesday morning, 10am-12am.

Reading group (2017)

A new reading group for Randomized Algorithms and Models with Biological Applications (RAMBA) takes place regularly at DIENS,

List of talks

  • 02/23, 2pm: Tatiana Starikovskaya, Sub-cubic algorithm for RNA folding
  • 02/17, 10am: Gregory Kucherov, Locality sensitive hashing
  • 01/27, 1pm: Laurent Bulteau, FPT and Streaming
  • 01/27, 2pm: Alice Heliou, Minimal absent word
  • 01/12, 2pm: Tatiana Starikovskaya, Communication and streaming complexity ofapproximate pattern matching
  • 01/12, 3pm: Yann Ponty, Selected combinatorial problems in RNA Bioinformatics and some solutions

Reading group (2016)

A new reading group on recent algorithmic progress takes place every weeks, Wednesday 9:45am-11:15am alternatively at IRIF and DIENS from October to December. If you are interested in joining, please contact Claire Mathieu.

List of papers to present

Workshops (2015-16)

From November 2015 to March 2016, members of RDAM project have been involved in the following workshops related to the project.

February 2016 - March 2016

IHP trimester on Nexus of Information and Computation theories: January to March 2016 Two workshops are hightly related to the RDAM project:

  • Workshop on Fundamental Inequalities and Lower Bounds (February 15 – 26), co-organized by Iordanis Kerenidis
  • Workshops on Inference Problems (March 7 - 18), including talks on Property Testing and Streaming algorithms

November 2015 - January 2016

FSMP Chair course on the Mathematics and Algorithms of Social Networks, organized by Zvi Lotker: from November 2015 to January 2016

Reading groups (2013-15)

There has been a meeting/reading group animating the project from 2013, usually at LIAFA (and at ENS when explicitely mentioned). It has been suspended for the period November 2015 - March 2016, because of local workshops/courses organized by RDAM members. It will start again after that period.

September - November 2015

A thematic reading group on machine learning takes place every weeks, Thursday 3:15pm-5:15pm at LIAFA, room 358. It is based on Ryan O-Donnell's book on Analysis of Boolean Functions, with an extra emphasis on the connections to Learning.

May - June 2015

A thematic reading group on machine learning takes place basically every 2 weeks, usually Thursday morning at LIAFA, room 4068.

  • 07/09, 10:45am, room 4068: Lucas Boczkowski, Learning k-Modal Distributions via Testing (continued)
  • 06/25, 10:45am, room 4068: Lucas Boczkowski, Learning k-Modal Distributions via Testing
  • 06/11, 10:45am, room 4068: Alex Bredariol-Grilo, On Learning and Testing Dynamic Environments
  • 05/21, 10:00am, room 4068: Varun Kanade, Computational Learning Theory (tutorial)

September 2014 - April 2015

Two thematic reading groups alternated each Thursday morning, one on information theory and complexity, one on social networks (based in part on the Easley-Kleinberg book "Networks, Crowds, and Markets: Reasoning about a Highly Connected World"):

Information theory and complexity Social networks
2015
04/23, 10:45am, room 4068: Zvi Lotker, Social networks and Julius Caesar
04/16, 10:00am, room 1009: Hervé Fournier, Tutorial on Complexity Theory 04/02, 10:30am, room 1009: Rida Laraki, Majority Judgement
03/26, 10:45am, room 4068: Lila Fontes, A Stable Marriage Requires Communication 03/19, 10:45am, room 4068: Claire Mathieu, Homophily and the Glass Ceiling Effect in Social Networks
02/19, 10:45am, room 4068: Florent Urrutia, Toward Better Formula Lower Bounds 02/12, 10:45am, room 4068: Paolo Penna, Diffusion of Innovations with probabilistic rule
01/29, 10:45am, room 4068: Nikos Leonardos, The Communication Complexity of Number-In-Hand Set Disjointness with No Promise 01/22, 10:45am, room 4068: Moti Medina, Cascading behavior in networks
2014
12/09 (Tuesday), 10:45am, room 1007 (unusual day and room): Florent Urrutia, An Interactive Information Odometer with Applications 12/11, 10:45am, room 4068: Reut Levi, Affiliation networks
11/20, 10:45am, room 4068: Nikos Leonardos, Topology matters in communication 11/27, 10:45am, room 4068: Zvi Lotker, Core-Periphery in Networks: An Axiomatic Approach
11/06, 10:45am, room 4068: Paolo Penna, Algorithms, game, and evolution 11/13, 10:45am, room 4068: Francis Bach, Machine learning in the context of graphs or networks
10/23, 10:45am, room 4068: Varun Kanade, Satisfiability and Evolution 10/30, 10:45am, room 4068: Pierre Fraigniaud, Small-world networks
10/09, 10:45am, room 4068: Nathanaël François and Mathieu Lauriere, Exponential separation of information and communication for Boolean functions (continued) 10/16, 10:45am, room 4068: Varun Kanade, Chapter 4 in Easley-Kleinberg book
09/25, 10:45am, room 4068: Lila Fontes, Exponential separation of information and communication for Boolean functions 10/02, 10:45am, ENS: Zvi Lotker, Chapter 3 in Easley-Kleinberg book plus the paper by Mark Granovetter "The strength of weak ties"

January - June 2014

The reading group took place basically every 2-3 weeks.

  • Tuesday, June 27th, 10am, room 4068: Mathieu Lauriere, Exponential Separation of Information and Communication
  • Friday, June 6th, 10am, room 4068: Nathanaël François, Turnstile Streaming Algorithms Might as Well Be Linear Sketches
  • Friday, May 23rd, 10am, ENS (45 rue d'Ulm), salle des Hauts du DI (Staircase A, 3rd floor, Dpt Informatique, at the very end of the corridor): Valerie King (U. Victoria), Byzantine agreement with a Strong Adversary in Polynomial Expected Time
  • Friday, March 28th, 11am, room 4068: Eric Colin de Verdière and Frédéric Magniez, Parallel Algorithms for Geometric Graph Problems
  • Tuesday, January 28th, 11am, room 1007: Mathieu Lauriere, A Second Look at Counting Triangles in Graph Streams
  • In 2013

    The reading group took place basically every 2-3 weeks.

    • Tuesday, November 26th, 11am, room 1007: Holger Dell, Fast algorithms for Hamiltonicity
    • Friday, November 8th, 11am, room 4068: Eric Colin de Verdière, The Approximate Rank of a Matrix and its Algorithmic Applications
    • Tuesday, October 1st, 11am, room 1007: Arnaud de Mesmay, Testing Surface Area
    • Thursday, June 27th, 10:30am, room 4068: Michel de Rougemont, Graph Isomorphism via Relaxations
    • Wednesday, June 12th, 11am, room 4068: Christian Konrad, Faster Dynamic Matchings and Vertex Connectivity
    • Wednesday, June 5th, 10:30am, room 4068: Hang Zhou, Dynamic Graph Connectivity in Polylogarithmic Worst Case Time
    • Tuesday, May 21st, 3:15pm, room 4068: Claire Mathieu and Nathanaël François, Improving Christofides' Algorithm for the s-t Path TSP
    • Thursday, May 2, 10am, room 4067: Claire Mathieu, Improving Christofides' Algorithm for the s-t Path TSP
    • Wednesday, April 17, 10:30am, room 4067: Frédéric Magniez, Dynamic Maximal Matching
    • Tuesday, April 2, 11am, room 1007: Claire Mathieu, The Lasserre polynomial hierarchy for the knapsack problem

    Kickoff meeting

    The official kickoff meeting will be on April 2nd, 9h30-13h30 at LIAFA

    • 9h30-10h45: general discussion with permanent members of the project
    • 11h-12h: reading group by Claire Mathieu on "The Lasserre polynomial hierarchy for the knapsack problem"
    • 12h30-13h30: lunch