Closing workshop: Dec. 7, 2017

In collaboration with a CNRS bilateral collaboration (PICS), a 2-day joint workshop will be organized December 7-8, 2017 at IRIF, room 3052.

12/07, Day 1: Closing workshop of ANR project on algorithmic techniques for Restricted Data Access Models
- 10:00-10:30 Vincent Cohen Addad (LIP6), On the Local Structure of Stable Clustering Instances
- 10:40-11:10 Lucas Boczkowski (IRIF), Searching a tree with permanently noisy advice
- 11:20-11:50 Ami Paz (IRIF), Distributed and non-distributed computational models
- 13:30-14:00 Nicolas Schabanel (IRIF & LIP), Proving the Turing universality of Oritatami co-transcriptional molecular folding
- 14:10-14:40 Pierre Fraigniaud (IRIF), Distributed Property Testing
- 14:50-15:20 Tatiana Starikovskaya (DIENS), Ultra-efficient algorithms for testing well-parenthesised expressions
12/08, Day 2: 1st IRIF-IQC 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

CACM Survey: Exact Exponential Algorithms, 2013 https://cseweb.ucsd.edu/~russell/FGCA/fomin.pdf
Invitation to algorithmic uses of inclusion-exclusion https://arxiv.org/pdf/1105.2942v2.pdf
Determinant Sums for Undirected Hamiltonicity https://web.stanford.edu/~rrwill/presentations/bjorklund-hamcycle.pdf
Dynamic programming meets the principle of inclusion and exclusion http://www.sciencedirect.com/science/article/pii/016763778290044X
Space-time tradeoff for DP
Saving space by algebraization https://web.stanford.edu/~rrwill/presentations/saving-space.pdf
Saving space by Dynamic Algebraization http://link.springer.com/chapter/10.1007/978-3-319-06686-8_29#page-1
Counting perfect matchings as fast as Ryser http://dl.acm.org/citation.cfm?id=2095189

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