Groupe de lecture - Informatique théorique
Groupe de lecture animé par Damien Vergnaud. (Salle R, le mercredi de 14h30 à 16h30)
L'évaluation du groupe de lecture se fait par une participation régulière et active aux séances et la présentation d'au moins un article pendant le semestre. Une liste non exhaustive des articles pouvant donner lieu à une présentation est donnée ci-dessous.
topPlanning
-
1 février
- Présentation du groupe de lecture (organisation)
-
15 février
-
Homomorphic Computation of Edit Distance
Luc CHABASSIER
-
Homomorphic Computation of Edit Distance
-
22 février
- Compressed String Dictionary Search with Edit Distance One
Camille GOBERT
- Compressed String Dictionary Search with Edit Distance One
-
1 mars
-
8 mars
-
22 mars
-
19 avril
-
Edit Distance for Pushdown Automata.
Clément Lalanne
-
Edit Distance for Pushdown Automata.
-
17 mai
-
The Dyck Language Edit Distance Problem in Near-Linear Time.
Hector Dang-Nhu
-
The Dyck Language Edit Distance Problem in Near-Linear Time.
Articles
Algorithmique
-
Edit Distance: Sketching, Streaming, and Document Exchange
FOCS 2016: IEEE 57th Annual Symposium on Foundations of Computer Science
Djamal Belazzougui, Qin Zhang - Streaming algorithms for embedding and computing edit distance in
the low distance regime.
STOC 2016: 48th Annual ACM SIGACT Symposium on Theory of Computing
Diptarka Chakraborty, Elazar Goldenberg, Michal Koucky -
Compressed String Dictionary Search with Edit Distance One
Algorithmica 74(3): 1099-1122 (2016)
Djamal Belazzougui, Rossano Venturini -
Homomorphic fingerprints under misalignments: sketching edit and shift distances.
STOC 2013: 45th Annual ACM SIGACT Symposium on Theory of Computing
Alexandr Andoni, Assaf Goldberger, Andrew McGregor, Ely Porat -
The smoothed complexity of edit distance.
ACM Trans. Algorithms 8(4): 44:1-44:25 (2012)
Alexandr Andoni, Robert Krauthgamer
Complexité
- Truly Sub-cubic Algorithms for Language Edit Distance and
RNA-Folding via Fast Bounded-Difference Min-Plus Product
FOCS 2016: IEEE 57th Annual Symposium on Foundations of Computer Science
Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams -
Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH
is false).
STOC 2015: 47th Annual ACM SIGACT Symposium on Theory of Computing
Arturs Backurs, Piotr Indyk
Complexité de communication
-
The Computational Hardness of Estimating Edit Distance.
SIAM J. Comput. 39(6): 2398-2429 (2010)
Alexandr Andoni, Robert Krauthgamer -
Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type
Inequalities.
SODA 2010: Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms
Alexandr Andoni, T. S. Jayram, Mihai Patrascu
Cryptographie
-
Edit Distance Based Encryption and Its Application.
ACISP 2016: Australasian Conference on Information Security and Privacy
Tran Viet Xuan Phuong, Guomin Yang, Willy Susilo, Kaitai Liang -
Locally Decodable Codes for Edit Distance.
ICITS 2015: International Conference on Information Theoretic Security
Rafail Ostrovsky, Anat Paskin-Cherniavsky -
Homomorphic Computation of Edit Distance.
FC 2015: Financial Cryptography and Data Security pp 194-212
Jung Hee Cheon, Miran Kim, Kristin E. Lauter
Langages formels
- Simulating branching programs with edit distance and friends: or:
a polylog shaved is a lower bound made.
STOC 2016: 48th
Annual ACM SIGACT Symposium on Theory of Computing
Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Ryan Williams: - Language Edit Distance and Maximum Likelihood Parsing of Stochastic
Grammars: Faster Algorithms and Connection to Fundamental Graph
Problems.
FOCS 2015: IEEE 56th Annual Symposium on Foundations of Computer Science
Barna Saha -
Edit Distance for Pushdown Automata.
ICALP 2015: Automata, Languages, and Programming - 42nd International Colloquium
Krishnendu Chatterjee, Thomas A. Henzinger, Rasmus Ibsen-Jensen, Jan Otop -
The Dyck Language Edit Distance Problem in Near-Linear Time.
FOCS 2014: IEEE 55th Annual Symposium on Foundations of Computer Science
Barna Saha