Combinatorial Pattern Matching
26th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29 -- July 1, 2015, Proceedings
Page
%P
-
Article
Open AccessIteration-Free quantum approximate optimization algorithm using neural networks
The quantum approximate optimization algorithm (QAOA) is a leading iterative variational quantum algorithm for heuristically solving combinatorial optimization problems. A large portion of the computational ef...
-
Chapter and Conference Paper
Support Optimality and Adaptive Cuckoo Filters
Filters (such as Bloom Filters) are a fundamental data structure that speed up network routing and measurement operations by storing a compressed representation of a set. Filters are very space efficient, but ...
-
Article
Mind the Gap!
We examine the complexity of the online Dictionary Matching with One Gap Problem (DMOG) which is the following. Preprocess a dictionary D of d patterns, where each pattern contains a special gap symbol that can m...
-
Article
Streaming Pattern Matching with d Wildcards
In the pattern matching with d wildcards problem one is given a text T of length n and a pattern P of length m that contains d wildcard characters, each denoted by a special symbol ‘?’. A wildcard character match...
-
Chapter and Conference Paper
Dynamic Dictionary Matching in the Online Model
In the classic dictionary matching problem, the input is a dictiona...
-
Article
Erratum to: A Grou** Approach for Succinct Dynamic Dictionary Matching
-
Chapter and Conference Paper
Conditional Lower Bounds for Space/Time Tradeoffs
In recent years much effort has been concentrated towards achieving polynomial time lower bounds on algorithms for solving various well-known problems. A useful technique for showing such lower bounds is to pr...
-
Article
A Grou** Approach for Succinct Dynamic Dictionary Matching
In this work, we focus on building an efficient succinct dynamic dictionary that significantly improves the query time of the current best known results. The algorithm that we propose suffers from only a ...
-
Book and Conference Proceedings
-
Chapter and Conference Paper
Dictionary Matching in a Stream
We consider the problem of dictionary matching in a stream. Given a set of strings, known as a dictionary, and a stream of characters arriving one at a time, the task is to report each time some string in our ...
-
Chapter and Conference Paper
Dynamic Set Intersection
Consider the problem of maintaining a family F of dynamic sets subject to insertions, deletions, and set-intersection reporting queries: given ...
-
Chapter and Conference Paper
Dictionary Matching with One Gap
The dictionary matching with gaps problem is to preprocess a dictionary D of d gapped patterns P 1,…,P d over alphabet Σ, where each gapped pattern P ...
-
Chapter and Conference Paper
An Improved Query Time for Succinct Dynamic Dictionary Matching
In this work, we focus on building an efficient succinct dynamic dictionary that significantly improves the query time of the current best known results. The algorithm that we propose suffers from only a O((loglo...
-
Chapter and Conference Paper
Orienting Fully Dynamic Graphs with Worst-Case Time Bounds
In edge orientations, the goal is usually to orient (direct) the edges of an undirected network (modeled by a graph) such that all out-degrees are bounded. When the network is fully dynamic, i.e., admits edge ...
-
Chapter and Conference Paper
For-All Sparse Recovery in Near-Optimal Time
An approximate sparse recovery system in ℓ1 norm consists of parameters k, ε, N, an m-by-N measurement Φ, and a recovery algorithm, $\...
-
Article
Preprocess, Set, Query!
Thorup and Zwick (J. ACM 52(1):1–24, 2005 and STOC’01) in their seminal work introduced the notion of distance oracles. Given an n-vertex weighted undirected graph with m edges, they show that for any integer ...
-
Article
Guest Editorial for “Group Testing: models and applications”
-
Book and Conference Proceedings
String Processing and Information Retrieval
20th International Symposium, SPIRE 2013, Jerusalem, Israel, October 7-9, 2013, Proceedings
-
Chapter and Conference Paper
Erratum to: String Processing and Information Retrieval
Erratum to: O. Kurland, M. Lewenstein, and E. Porat (Eds.) String Processing and Information Retrieval DOI: 10.1007/978-3-319-02432-5
-
Chapter and Conference Paper
ℓ2/ℓ2-Foreach Sparse Recovery with Low Risk
In this paper, we consider the “foreach” sparse recovery problem with failure probability p. The goal of the problem is to design a distribution over m ×N matrices Φ and a decoding algorithm A such that for every...
