String Matching: Communication, Circuits, and Learning.

DOI10.4230/LIPIcs.APPROX-RANDOM.2019.56OpenAlexW2977350080MaRDI QIDQ5875515

Daniel Reichman, Alexander Golovnev, Mika Göös, Igor Shinkar

Publication date: 3 February 2023

Full work available at URL: https://arxiv.org/abs/1709.02034

zbMATH Keywords

string matchingcircuit complexityPAC learningcommunication complexity

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Approximation algorithms (68W25) Randomized algorithms (68W20)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Parallel computation with threshold functions
• On the distributional complexity of disjointness
• Neural circuits for pattern recognition with small total wire length.
• Top-down lower bounds for depth-three circuits
• On learning visual concepts and DNF formulae
• Threshold circuits of bounded depth
• Lower Bounds in Communication Complexity
• On Graph Complexity
• The Probabilistic Communication Complexity of Set Intersection
• On the Worst-Case Behavior of String-Searching Algorithms
• Fast Pattern Matching in Strings
• Communication Complexity
• On small depth threshold circuits
• Exact and Approximate Pattern Matching in the Streaming Model
• Super-linear gate and super-quadratic wire lower bounds for depth-two and depth-three threshold circuits

This page was built for publication: String Matching: Communication, Circuits, and Learning.