Communication and Streaming Complexity of Approximate Pattern Matching

DOI10.4230/LIPICS.CPM.2017.13MaRDI QIDQ5110877zbMATH OpenOpenAlexFDO

Authors Tatiana Starikovskaya

Publication date 25 May 2020

Full work available at URL https://hal.science/hal-03942927

zbMATH Keywords

edit distancecommunication complexityapproximate pattern matchingstreaming algorithmsrandomised algorithms

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Randomized algorithms (68W20) Algorithms on strings (68W32) Communication complexity, information complexity (68Q11)

Recommendations

• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• Approximating Approximate Pattern Matching
• Communication complexity of approximate matching in distributed graphs
• Streaming and communication complexity of clique approximation
• scientific article; zbMATH DE number 7651042
• scientific article; zbMATH DE number 7053293
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Communication complexity of approximate maximum matching in the message-passing model

Cited in

(8)

• Approximate Hamming distance in a stream
• Optimal Lower Bounds on Regular Expression Size Using Communication Complexity
• Regular languages in the sliding window model
• The streaming \(k\)-mismatch problem
• Towards optimal approximate streaming pattern matching by matching multiple patterns in multiple streams
• String Matching: Communication, Circuits, and Learning.
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Differentially private approximate pattern matching

This page was built for publication: Communication and Streaming Complexity of Approximate Pattern Matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5110877)