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
- 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
- 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
In 2013
The reading group took place basically every 2-3 weeks.
Kickoff meeting
The official kickoff meeting will be on April 2nd, 9h30-13h30 at LIAFA